## Seminars and Colloquia by Series

Friday, November 1, 2013 - 15:00 , Location: Skiles 005 , Hiep Han , Emory University and University of Sao Paulo , Organizer:
The problem of extending results in extremal combinatorics to sparse random and pseudorandom structures has attracted the attention of many researchers in the last decades. The breakthroughs due to several groups in the last few years have led to a better understanding of the subject, however, many questions remain unsolved. After a short introduction into this field we shall focus on some results in extremal (hyper)graph theory and additive combinatorics. Along the way some open problems will be given.
Friday, October 25, 2013 - 15:00 , Location: Skiles 005 , Elad Horev , University of Hamburg , Organizer:
An open problem of interest in combinatorial number theory is that of providing a non-ergodic proof to the so called polynomial Szemeredi theorem. So far, the landmark result in this venue is that of Green who considered the emergence of 3-term arithmetic progressions whose gap is a sum of two squares (not both zero) in dense sets of integers. In view of this we consider the following problem. Given two dense subsets A and S of a finite abelian group G, what is the weakest "pseudorandomness assumption" once put on S implies that A contains a 3-term arithmetic progressions whose gap is in S?  We answer this question for G=Z_n and G = F_p^n. To quantify pseudorandomness we use Gowers norms.
Friday, October 4, 2013 - 15:05 , Location: Skiles 005 , Alfredo Hubard , École Normale Supérieure , Organizer:
The Erdos-Szekeres (happy ending) theorem claims that among any N points in general position in the plane there are at least log_4(n) of them that are the vertices of a convex polygon. I will explain generalizations of this result that were discovered in the last 30 years involving pseudoline arrangements and families of convex bodies. After surveying some previous work I will present the following results: 1) We improve the upper bound of the analogue Ramsey function for families of disjoint and noncrossing convex bodies. In fact this follows as a corollary of the equivalence between a conjecture of Goodman and Pollack about psudoline arrangements and a conjecture of Bisztrinsky and Fejes Toth about families of disjoint convex bodies. I will say a few words about how we show this equivalence. 2) We confirm a conjecture of Pach and Toth that generalizes the previous result. More precisely we give suffcient and necesary conditions for the existence of the analogue Ramsey function in the more general case in which each pair of bodies share less than k common tangents (for every fixed k). These results are joint work with Andreas Holmsen and Michael Dobbins.
Friday, September 27, 2013 - 15:05 , Location: Skiles 005 , Jan Volec , University of Warwick , Organizer: Robin Thomas
Graphons are limit objects that are associated with convergent sequences of graphs. Problems from extremal combinatorics and theoretical computer science led to a study of graphons determined by finitely many subgraph densities, which are referred to as finitely forcible graphons. In 2011, Lovasz and Szegedy asked several questions about the complexity of the topological space of so-called typical vertices of a finitely forcible graphon can be. In particular, they conjectured that the space is always compact. We disprove the conjecture by constructing a finitely forcible graphon such that the associated space of typical vertices is not compact. In fact, our construction actually provides an example of a finitely forcible graphon with the space which is even not locally compact. This is joint work with Roman Glebov and Dan Kral.
Friday, September 13, 2013 - 15:05 , Location: Skiles 005 , Mohammad Ghomi , School of Mathematics, Georgia Tech , Organizer:
A well-known problem in geometry, which may be traced back to the Renaissance artist Albrecht Durer, is concerned with cutting a convex polyhedral surface along some spanning tree of its edges so that it may be isometrically embedded, or developed without overlaps, into the plane. We show that this is always possible after an affine transformation of the surface. In particular, unfoldability of a convex polyhedron does not depend on its combinatorial structure, which settles a problem of Croft, Falconer, and Guy. Among other techniques, the proof employs a topological characterization for embeddings among immersed planar disks.
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