# All Seminars

Show:
Title: Extending Partial Geometric Representations of Graphs
Seminar: Combinatorics
Speaker: Jan Kratochvil of Charles University, Prague
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2015-04-17 at 4:00PM
Venue: W303
Abstract:
Intersection-defined classes of graphs are intensively studied for their applications and interesting properties. Many of them allow polynomial-time algorithms for otherwise computationally hard problems such as independent set, clique or coloring problems. And many of them can be recognized in polynomial time. In fact the polynomial-time algorithms often need a representation to be given or constructed as the initial step. The rather natural question of extending a partial representation has been studied only recently. It falls into the more general paradigm of extending a partial solution of a problem. Sometimes a global solution can be reached by incremental steps from a partial one in polynomial-time, but in many cases an otherwise easy problem may become hard. Examples of such behavior can be found for instance in graph colorings (e.g., deciding if a partial edge-coloring of a cubic bipartite graph can be extended to a full 3-coloring of it is NP-complete, though it is well known that every cubic bipartite graph is 3-edge-colorable and such a coloring can be found in polynomial time). In this talk we survey the known results about the computational complexity of extending partial geometric representations of graphs.
Title: A relative Szemeredi theorem
Colloquium: Department
Speaker: David Conlon of The University of Oxford
Contact: Dwight Duffus, Dwight@mathcs.emory.edu
Date: 2015-04-13 at 4:00PM
Venue: W303
Abstract:
The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. The proof has two parts. The first part is a relative Szemeredi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions, where a set is pseudorandom if it satisfies two conditions, the linear forms condition and the correlation condition. The second part is in finding a pseudorandom set in which the primes have positive relative density. In this talk, we will discuss a simple proof for a strengthening of the relative Szemeredi theorem, showing that a weak linear forms condition is sufficient for the theorem to hold. By removing the correlation condition, our strengthened version can be applied to give a relative Szemeredi theorem for $k$-term arithmetic progressions in pseudorandom subsets of $\mathbb{Z}_N$ of density $N^{-c_k}$. It also simplifies the deduction of the Green-Tao theorem by removing the need for certain number theoretic estimates in the second part of their proof. Joint work with Jacob Fox and Yufei Zhao.
Title: Music Information Retrieval
Colloquium: Department
Speaker: Davide Fossati of Carnegie Mellon University in Qatar
Contact: Ken Mandelberg, km@mathcs.emory.edu
Date: 2015-04-10 at 3:00PM
Venue: W303
Abstract:
What does it take to build a search engine for sound and music? How can computers "listen" to music and understand what you are playing? Currently, the most successful and widespread technologies for organizing and searching for information are based on text. Instead, the emerging field of Music Information Retrieval focuses on technology that operates directly on audio signals without relying on textual annotation. In this presentation I will give a brief overview of Music Information Retrieval: foundational ideas, methodology, and applications. We will see how sound can be represented, segmented, converted into a set of features, and classified.
Title: Knots and Brauer groups of curves
Seminar: Algebra
Speaker: Ted Chinburg of Penn
Contact: David Zureick-Brown, dzb@mathcs.emory.edu
Date: 2015-04-10 at 4:00PM
Venue: W302
Abstract:
There has been a great deal of research over the last 20 years on invariants of knots on one hand and on Brauer groups of curves on the other. The goal of this talk is to link these two subjects. This is joint work with Alan Reid and Matt Stover.
Title: Athens-Atlants joint number theory seminar
Seminar: Algebra
Speaker: Dick Gross and Ted Chinburg of Harvard and Penn
Contact: TBA
Date: 2015-04-09 at 4:00PM
Venue: At UGA
Abstract:
TBA
Title: An epsilon improvement to the asymptotic density of k-critical graphs
Defense: Dissertation
Speaker: Victor Larsen of Emory University
Contact: Victor Larsen, vlarsen@emory.edu
Date: 2015-04-08 at 4:30PM
Venue: W303
Abstract:
Given a graph $G$ the \emph{chromatic number}, denoted $\chi(G)$, is smallest number of colors necessary to color $V(G)$ such that no adjacent vertices receive the same color. A graph $G$ is $k$-critical if $\chi(G)=k$ but every proper subgraph has chromatic number less than $k$. As $k$-critical graphs can be viewed as minimal examples of graphs with chromatic number $k$, it is natural to ask how small such a graph can be. Let $f_k(n)$ denote the minimum number of edges in a $k$-critical graph on $n$ vertices. The Ore construction, used to build larger $k$-critical graphs, implies that $f_k(n+k-1)\leq f_k(n)+(k-1)\left(\frac{k}{2}-\frac{1}{k-1}\right).$ A recent paper by Kostochka and Yancey provides a lower bound for $f_k(n)$ which implies that the asymptotic density $\phi_k:=\lim_{n\to\infty}f_k(n)/n = \frac{k}{2}-\frac{1}{k-1}$. In this work, we use the method of discharging to prove a lower bound on the number of edges which includes structural information about the graph. This lower bound shows that the asymptotic density of a $k$-critical graph can be increased by $\epsilon>0$ by restricting to $(K_{k-2})$-free $k$-critical graphs.\\ \\ We also prove that the graphs constructible from the Ore construction and $K_k$, called \emph{$k$-Ore} graphs, are precisely the graphs which attain Kostochka and Yancey's bound. Moreover, we also provide results regarding subgraphs which must exist in $k$-Ore graphs. For the discharging argument, carried out in two stages, we also prove results regarding the density of nearly-bipartite subgraphs in $k$-critical graphs.
Title: Cloud Computing: Just a buzzword or already a reality?
Colloquium: DEPARTMENT
Speaker: Gongbing Hong of William and Mary
Contact: Ken Mandelberg, KM@mathcs.emory.edu
Date: 2015-04-03 at 3:00PM
Venue: W303
Abstract:
In this talk, we will give a brief introduction to Cloud Computing. First, we will provide a few definitions for cloud computing and discuss the big ideas of this new computing paradigm. Then we will talk about the services provided by cloud computing as seen today along with examples as offered by big players in the industry. We will also talk about how clouds are being deployed and the future of the clouds. At the end, we will discuss the impacts, issues, and the challenges of cloud computing.
Title: A Stochastic Model for Networks at Arise from Conference Scheduling Problems
Defense: Master's Thesis
Speaker: Andres Celis of Emory University
Contact: Andres Celis, acelis@emory.edu
Date: 2015-04-02 at 1:00PM
Venue: E408
Abstract:
A conference scheduling problem may be viewed as an undirected graph whose vertices correspond to the events of the conference, and whose edges correspond to constraints that prohibit two events from being scheduled at the same time. In this thesis we propose and analyze a new random graph model inspired by a series of experimental observations on datasets from the industry, as well as conversations with a conference scheduler.\\ \\ Our models differs from existing random graph models in the following: \begin{enumerate} \item We find that graph models with independently chosen edges do not result in degree distributions found in conference scheduling problems. Thus our model's edges are statistically dependent on each other. \item Our model introduces new vertices into the graph as time evolves. The existing models that do this have small, bounded clique and chromatic numbers and are trivial to color, which is not an accurate representation of scheduling problems. We show that the expected clique number of our model has a lower bound of $\Omega(T^{1/4}/(\log T)^{3/4})$. We also argue that the expected clique and chromatic numbers of our model are upper bounded by $O(T^{1/4})$ and $O(T^{2/5})$, respectively. \end{enumerate}
Title: On Chorded Cycles
Defense: Dissertation
Speaker: Megan Cream of Emory University
Contact: Megan Cream, mcream@emory.edu
Date: 2015-04-02 at 4:00PM
Venue: W303
Abstract:
Historically, there have been many results concerning sufficient conditions for implying certain sets of cycles in graphs. My thesis aims to extend many of these well known results to similar results on sets of {\it chorded} (and sometimes even {\it doubly chorded}) cycles. In particular, we consider the minimum degree, $\delta(G)$ and a Ore-type degree sum condition, $\sigma_2(G)$ of a graph $G$, sufficient to guarantee the existence of $k$ vertex disjoint chorded cycles, often containing specified elements of the graph, such as certain vertices or edges. Further, we extend a result on vertex disjoint cycles and chorded cycles to an analogous result on vertex disjoint cycles and {\it doubly} chorded cycles. We define a new graph property called chorded pancyclicity, and investigate a density condition and forbidden subgraphs in claw-free graphs that imply this new property. Specifically, we forbid certain paths and triangles with pendant paths. This is joint work with Dongqin Cheng, Ralph Faudree, Ron Gould, and Kazuhide Hirohata.
Title: Approximating spectral densities of large matrices: old and new
Seminar: Numerical Analysis and Scientific Computing
Speaker: Lin Lin of UC Berkeley
Contact: Michele Benzi, benzi@mathcs.emory.edu
Date: 2015-04-01 at 12:00AM
Venue: W306
Abstract:
In physics, it is sometimes desirable to compute the so-called Density Of States (DOS), also known as the spectral density, of a Hermitian matrix A. The spectral density can be viewed as a probability density distribution that measures the likelihood of finding eigenvalues near some point on the real line. The most straightforward way to obtain this density is to compute all eigenvalues. But this approach is generally costly and wasteful, especially for matrices of large dimension. In many cases, the only affordable operation is matrix-vector multiplication. In this talk I will define the problem of estimating the spectral density carefully, and discuss a few known algorithms based on stochastic sampling, in particular, those using the kernel polynomial method and the Lanczos method, for estimating the spectral density. The accuracy of stochastic algorithms converge as $O(1\sqrt{N_v})$, where $N_v$ is the number of stochastic vectors. I will also talk about recent progresses of stochastic estimation of spectral densities with convergence rate much faster than $O(1\sqrt{N_v})$ using a relatively high degree of polynomials and modest choice of $N_v$. (Joint work with Yousef Saad and Chao Yang)