Seminars and Colloquia by Series

Friday, March 1, 2013 - 15:00 , Location: Skiles 005 , Prof. Andrzej Rucinski , Poznan and Emory , Organizer: Ernie Croot
For two graphs, G and F, we write G\longrightarrow F if every 2-coloring of the edges of G results in a monochromatic copy of F. A graph G is k-Folkman if G\longrightarrow K_k and G\not\supset K_{k+1}. We show that there is a constant c > 0 such that for every k \ge 2 there exists a k-Folkman graph on at most 2^{k^{ck^2}} vertices. Our probabilistic proof is based on a careful analysis of the growth of constants in a modified proof of the result by Rodl and the speaker from 1995 establishing a threshold for the Ramsey property of a binomial random graph G(n,p). Thus, at the same time, we provide a new proof of that result (for two colors) which avoids the use of regularity lemma. This is joint work with Vojta Rodl and Mathias Schacht.
Friday, February 22, 2013 - 15:00 , Location: Skiles 005 , Choongbum Lee , M.I.T. , Organizer: Ernie Croot
For a given finite graph G of minimum degree at least k, let G_{p} be a random subgraph of G obtained by taking each edge independently with probability p. We prove that (i) if p \ge \omega/k for a function \omega=\omega(k) that tends to infinity as k does, then G_p asymptotically almost surely contains a cycle (and thus a path) of length at least (1-o(1))k, and (ii) if p \ge (1+o(1))\ln k/k, then G_p asymptotically almost surely contains a path of length at least k. Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking G to be the complete graph on k+1 vertices. Joint w/ Michael Krivelevich (Tel Aviv), Benny Sudakov (UCLA).
Friday, February 15, 2013 - 15:05 , Location: Skiles 005 , David Goldberg , ISyE, Georgia Tech , Organizer: Prasad Tetali
We consider higher order Markov random fields to study independent sets in regular graphs of large girth (i.e. Bethe lattice, Cayley tree). We give sufficient conditions for a second-order homogenous isotropic Markov random field to exhibit long-range boundary independence (i.e. decay of correlations, unique infinite-volume Gibbs measure), and give both necessary and sufficient conditions when the relevant clique potentials of the corresponding Gibbs measure satisfy a log-convexity assumption. We gain further insight into this characterization by interpreting our model as a multi-dimensional perturbation of the hardcore model, and (under a convexity assumption) give a simple polyhedral characterization for those perturbations (around the well-studied critical activity of the hardcore model) which maintain long-range boundary independence. After identifying several features of this polyhedron, we also characterize (again as a polyhedral set) how one can change the occupancy probabilities through such a perturbation. We then use linear programming to analyze the properties of this set of attainable probabilities, showing that although one cannot acheive denser independent sets, it is possible to optimize the number of excluded nodes which are adjacent to no included nodes.
Friday, February 1, 2013 - 15:00 , Location: Skiles 005 , Huseyin Acan , Ohio State University , Organizer: Ernie Croot
A permutation of the set {1,2,...,n} is connected if there is no k < n such that the set of the first k numbers is invariant as a set under the permutation. For each permutation, there is a corresponding graph whose vertices are the letters of the permutation and whose edges correspond to the inversions in the permutation. In this way, connected permutations correspond to connected permutation graphs. We find a growth process of a random permutation in which we start with the identity permutation on a fixed set of letters and increase the number of inversions one at a time. After the m-th step of the process, we obtain a random permutation s(n,m) that is uniformly distributed over all permutations of {1,2,...,n} with m inversions. We will discuss the evolution process, the connectedness threshold for the number of inversions of s(n,m), and the sizes of the components when m is near the threshold value. This study fits into the wider framework of random graphs since it is analogous to studying phase transitions in random graphs. It is a joint work with my adviser Boris Pittel.
Friday, January 25, 2013 - 15:00 , Location: Skiles 005 , Prof. Ernie Croot , Georgia Tech , Organizer: Ernie Croot
This talk will be on an algebraic proof of theSzemeredi-Trotter theorem, as given by Kaplan, Matousek and Sharir.The lecture assumes no prior knowledge of advanced algebra.
Friday, January 18, 2013 - 15:00 , Location: Skiles 005 , Albert Bush , Georgia Tech , Organizer: Ernie Croot
The additive energy of a set of integers gives key information on the additive structure of the set. In this talk, we discuss a new, closely related statistic called the indexed additive energy. We will investigate the relationship between the indexed additive energy, the regular additive energy, and the size of the sumset.
Friday, January 11, 2013 - 15:00 , Location: Skiles 005 , Thai Hoang Le , U. Texas , Organizer: Ernie Croot
The Green-Tao theorem says that the primes contain arithmetic progressions of arbitrary length. Tao and Ziegler extended it to polynomial progressions, showing that congurations {a+P_1(d), ..., a+P_k(d)} exist in the primes, where P_1, ..., P_k are polynomials in \mathbf{Z}[x] without constant terms (thus the Green-Tao theorem corresponds to the case where all the P_i are linear). We extend this result further, showing that we can add the extra requirement that d be of the form p-1 (or p + 1) where p is prime. This is joint work with Julia Wolf.
Friday, December 7, 2012 - 15:05 , Location: Skiles 005 , Omar Abuzzahab , University of Pennsylvania, Philadelphia , Organizer: Prasad Tetali
The k-core of a (hyper)graph is the unique subgraph where all vertices have degree at least k and which is the maximal induced subgraph with this property.  It provides one measure of how dense a graph is; a sparse graph will tend to have a k-core which is smaller in size compared to a dense graph.  Likewise a sparse graph will have an empty k-core for more values of k.   I will survey the results on the random k-core of various random graph models.  A common feature is how the size of the k-core undergoes a phase transition as the density parameter passes a critical threshold.     I will also describe how these results are related to a class of related problems that initially don't appear to involve random graphs.  Among these is an interesting problem arising from probabilistic number theory where the random hypergraph model has vertex degrees that are "non-homogeneous"---some vertices have larger  expected degree than others.
Friday, November 30, 2012 - 15:00 , Location: Skiles 005 , Yi Zhao , Georgia State University , Organizer: Ernie Croot
Given integers k\ge 3 and d with k/2 \leq d \leq k-1, we give a minimum d-degree condition that ensures a perfect matching in a k-uniform hypergraph. This condition is best possible and extends the results of Pikhurko, R\"odl, Ruci\'{n}ski and Szemer\'edi. Our approach makes use of the absorbing method. This is a joint work with Andrew Treglown.
Friday, November 16, 2012 - 15:05 , Location: Skiles 005 , Dmitry Shabanov , Moscow State University and Yandex Corporate , Organizer: Prasad Tetali
The talk is devoted to the classical problem of estimating the Van der Waerden number W(n,k). The famous Van der Waerden theorem states that, for any integers n\ge 3, k\ge 2, there exists the smallest integer W(n,k) such that in any k-coloring of the set {1,2,...,W(n,k)}, there exists a monochromatic arithmetic progression of length n.  Our talk is focused on the lower bounds for the van der Waerden number. We shall show that estimating W(n,k) from below is closely connected with extremal problems concerning colorings of uniform hypergraphs with large girth. We present a new lower bound for W(n,k), whose proof is based  on a continuous-time random recoloring process.