## Seminars and Colloquia by Series

Friday, August 30, 2013 - 15:05 , Location: Skiles 005 , Rani Hod , School of Mathematics, Georgia Tech , Organizer:
We study the Maker-Breaker component game, played on the edge set of a regular graph. Given a graph G, the s-component (1:b) game is defined as follows: in every round Maker claims one free edge of G and Breaker claims b free edges. Maker wins this game if her graph contains a connected component of size at least s; otherwise, Breaker wins the game. For all values of Breaker's bias b, we determine whether Breaker wins (on any d-regular graph) or Maker wins (on almost every d-regular graph) and provide explicit winning strategies for both players. To this end, we prove an extension of a theorem by Gallai-Hasse-Roy-Vitaver about graph orientations without long directed simple paths. Joint work with Alon Naor.
Wednesday, May 22, 2013 - 15:05 , Location: Skiles 005 , Amanda Streib , National Institute of Standards and Technology , Organizer: Robin Thomas
Studying the ferromagnetic Ising model with zero applied field reduces to sampling even subgraphs X of G with probability proportional to \lambda^{|E(X)|}. In this paper we present a class of Markov chains for sampling even subgraphs, which contains the classical single-site dynamics M_G and generalizes it to nonlocal chains. The idea is based on the fact that even subgraphs form a vector space over F_2 generated by a cycle basis of G. Given any cycle basis C of a graph G, we define a Markov chain M(C) whose transitions are defined by symmetric difference with an element of C. We characterize cycle bases into two types: long and short. We show that for any long cycle basis C of any graph G, M(C) requires exponential time to mix when \lambda is small. All fundamental cycle bases of the grid in 2 and 3 dimensions are of this type. Moreover, on the 2-dimensional grid, short bases appear to behave like M_G. In particular, if G has periodic boundary conditions, all short bases yield Markov chains that require exponential time to mix for small enough \lambda. This is joint work with Isabel Beichl, Noah Streib, and Francis Sullivan.
Friday, April 12, 2013 - 15:05 , Location: Skiles 005 , Arnab Bhattacharyya , MIT , Organizer: Prasad Tetali
Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that all affine-invariant properties having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that there is a test that, given an input function f, makes a constant number of queries to f, always accepts if f satisfies P, and rejects with positive probability if the distance between f and P is nonzero. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of low-degree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of low-degree non-classical polynomials. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degree-structural properties. [Joint work with Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett.]
Friday, April 5, 2013 - 15:05 , Location: Skiles 005 , Dhruv Mubayi , University of Illinois, Chicago , Organizer: Prasad Tetali
I will survey the major results in graph and hypergraph Ramsey theory and present some recent results on hypergraph Ramsey numbers. This includes a hypergraph generalization of  the graph Ramsey number R(3,t) proved recently  with Kostochka and Verstraete. If time permits some proofs will be presented.
Friday, March 29, 2013 - 15:00 , Location: Skiles 005 , Prof. Eugen Ionascu , Columbus State University , Organizer: Ernie Croot
Friday, March 8, 2013 - 15:00 , Location: Skiles 005 , Prof. Derrick Hart , Kansas State University , Organizer: Ernie Croot
Let A be a multiplicative subgroup of Z_p^*. Define the k-fold sumset of A to be kA={x_1+...+x_k:x_1,...,x_k in A}. Recently, Shkredov has shown that |2A| >> |A|^(8/5-\epsilon) for |A| < p^(9/17). In this talk we will discuss extending this result to hold for |A| < p^(5/9). In addition, we will show that 6A contains Z_p^* for |A| > p^(33/71 +\epsilon).
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.