Seminars and Colloquia by Series

Friday, April 27, 2012 - 15:05 , Location: Skiles 005 , Ernie Croot , School of Math, Ga Tech , , Organizer: Prasad Tetali
Sarkozy's problem is a classical problem in additive number theory, which asks for the size of the largest subset A of {1,2,...,n} such that the difference set A-A does not contain a (non-zero) square. I will discuss the history of this problem, some recent progress that I and several collaborators have made on it, and our future research plans.
Friday, April 20, 2012 - 15:05 , Location: Skiles 005 , Tomasz Luczak , Emory University and Adam Mickiewicz University, Poznan , , Organizer: Prasad Tetali
Let H_k(n,s) be a k-uniform hypergraphs on n vertices in which the largest matching has s edges. In 1965 Erdos conjectured that the maximum number of edges in H_k(n,s) is attained either when H_k(n,s) is a clique of size ks+k-1, or when the set of edges of H_k(n,s) consists of all k-element sets which intersect some given set S of s elements. In the talk we prove this conjecture for k = 3 and n large enough. This is a joint work with Katarzyna Mieczkowska.
Friday, April 13, 2012 - 15:05 , Location: Skiles 005 , Huang Hao , Math, UCLA , Organizer: Prasad Tetali
 More than 40 years ago, Erdos asked to determine the maximum possible number of edges in a k-uniform hypergraph on n vertices with no matching of size t (i.e., with no t disjoint edges). Although this is one of the most basic problem on hypergraphs, progress on Erdos' question remained elusive. In addition to being important in its own right, this problem has several interesting applications. In this talk we present a solution of Erdos' question for t
Friday, March 16, 2012 - 15:05 , Location: Skiles 005 , Mihai Ciucu , Mathematics, Indiana University, Bloomington, IN , Organizer: Prasad Tetali
The correlation of gaps in dimer systems was introduced in 1963 by Fisher and Stephenson, who looked at the interaction of two monomers generated by the rigid exclusion of dimers on the closely packed square lattice. In previous work we considered the analogous problem on the hexagonal lattice, and we extended the set-up to include the correlation of any finite number of monomer clusters. For fairly general classes of monomer clusters we proved that the asymptotics of their correlation is given, for large separations between the clusters, by a multiplicative version of Coulomb's law for 2D electrostatics. However, our previous results required that the monomer clusters consist (with possibly one exception) of an even number of monomers. In this talk we determine the asymptotics of general defect clusters along a lattice diagonal in the square lattice (involving an arbitrary, even or odd number of monomers), and find that it is given by the same Coulomb law. Of special interest is that one obtains a conceptual interpretation for the multiplicative constant, as the product of the correlations of the individual clusters. In addition, we present several applications of the explicit correlation formulas that we obtain.
Thursday, March 15, 2012 - 12:05 , Location: Skiles 005 , Po-Shen Loh , Carnegie Mellon University , Organizer: Xingxing Yu
Erd\H{o}s and Rothschild asked to estimate the maximum number, denotedby $h(n,c)$, such that every $n$-vertex graph with at least $cn^2$edges, each of which is contained in at least one triangle, mustcontain an edge that is in at least $h(n,c)$ triangles. In particular,Erd\H{o}s asked in 1987 to determine whether for every $c>0$ there is$\epsilon>0$ such that $h(n,c)>n^{\epsilon}$ for all sufficientlylarge $n$. We prove that $h(n,c)=n^{O(1/\log \log n)}$ for every fixed$c<1/4$. This gives a negative answer to the question of Erd\H{o}s,and is best possible in terms of the range for $c$, as it is knownthat every $n$-vertex graph with more than $n^2/4$ edges contains anedge that is in at least $n/6$ triangles.Joint work with Jacob Fox.
Friday, February 3, 2012 - 15:05 , Location: Skiles 005 , Olivier Bernardi , Math, MIT , , Organizer: Prasad Tetali
Planar maps are embeddings of connected planar graphs in the plane considered up to continuous deformation. We will present a ``master bijection'' for planar maps and show that it can be specialized in various ways in order to count several families of maps. More precisely, for each integer d we obtain a bijection between the family of maps of girth d and a family of decorated plane trees. This gives new counting results for maps of girth d counted according to the degree distribution of their faces. Our approach unifies and extends many known bijections. This is joint work with Eric Fusy.
Friday, January 27, 2012 - 15:05 , Location: Skiles 005 , Chris Pryby and Albert Bush , School of Mathematics, Georgia Tech , Organizer: Ernie Croot
A famous theorem of Szemeredi and Trotter established a bound on the maximum number of lines going through k points in the plane. J. Solymosi conjectured that if one requires the lines to be in general position -- no two parallel, no three meet at a point -- then one can get a much tighter bound. Using methods of G. Elekes, we establish Solymosi's conjecture on the maximum size of a set of rich lines in general position.
Friday, January 13, 2012 - 15:00 , Location: Skiles 005 , Prasad Raghavendra , School of Computer Science, Georgia Tech , Organizer: Prasad Tetali
A small set expander is a graph where every set of sufficiently small size has near perfect edge expansion. This talk concerns the computational problem of distinguishing a small set-expander, from a graph containing a small non-expanding set of vertices. This problem henceforth referred to as the Small-Set Expansion problem has proven to be intimately connected to the complexity of large classes of combinatorial optimization problems. More precisely, the small set expansion problem can be shown to be directly related to the well-known Unique Games Conjecture -- a conjecture that has numerous implications in approximation algorithms. In this talk, we motivate the problem, and survey recent work consisting of algorithms and interesting connections within graph expansion, and its relation to Unique Games Conjecture.
Friday, December 9, 2011 - 15:05 , Location: Skiles 005 , SuHo Oh , University of Michigan, Ann Arbor , , Organizer: Prasad Tetali
Wiring diagrams are classical objects of combinatorics. Plabic graphs were defined by Postnikov, to study the total positivity of the Grassmannian. We will show how to generalize several definitions and properties of wiring diagrams to Plabic graphs, proving a conjecture by Leclerc-Zelevinsky and Scott on the way. We will begin with a brief introduction to total positivity and end with connection to cluster algebras. Major part of the talk comes from a joint work with Alexander Postnikov and David Speyer.
Friday, November 18, 2011 - 15:05 , Location: Skiles 005 , Patricia Hersh , North Carolina State University, Raleigh, NC , Organizer: Prasad Tetali
The quotient of a Boolean algebra by a cyclic group is proven to have a symmetric chain decomposition. This generalizes earlier work of Griggs, Killian and Savage on the case of prime order, giving an explicit construction for any order, prime or composite. The combinatorial map specifying how to proceed downward in a symmetric chain is shown to be a natural cyclic analogue of Kashiwara's sl_2 lowering operator in the theory of crystal bases.   The talk will include a survey of related past work on symmetric chain decomposition and unimodality by Greene-Kleitman, Griggs-Killian-Savage, Proctor, Stanley and others as well as a discussion of open questions that still remain.  This is joint work with Anne Schilling.