Seminars and Colloquia by Series

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.
Friday, November 9, 2012 - 15:05 , Location: Skiles 005 , Humberto Silva Naves , Math, UCLA , , Organizer: Prasad Tetali
A variety of problems in extremal combinatorics can be stated as: For two given graphs $H_1$ and $H_2$, if the number of induced copies of $H_1$ in a $n$-vertex graph $G$ is known, what is the maximum or minimum number of induced copies of $H_2$ in $G$? Numerous cases of this question were studied by Tur\'an, Erd\H{o}s, Kruskal and Katona, and several others. Tur\'an proved that the maximal edge density in any graph with no cliques of size $r$ is attained by an $r-1$ partite graph. Kruskal and Katona found that cliques, among all graphs, maximize the number of induced copies of $K_s$ when $r
Friday, November 2, 2012 - 15:05 , Location: Skiles 005 , Jed Yang , Math, UCLA , , Organizer: Prasad Tetali

Given a set of tiles on a square grid (think polyominoes) and a region, can we tile the region by copies of the tiles?  In general this decision problem is undecidable for infinite regions and NP-complete for finite regions.  In the case of simply connected finite regions, the problem can be solved in polynomial time for some simple sets of tiles using combinatorial group theory; whereas the NP-completeness proofs rely heavily on the regions having lots of holes.  We construct a fixed set of rectangular tiles whose tileability problem is NP-complete even for simply connected regions.This is joint work with Igor Pak.

Friday, October 26, 2012 - 15:05 , Location: Skiles 005 , Spencer Backman , School of Math, Georgia Tech , , Organizer: Prasad Tetali
A hereditary chip-firing model is a chip-firing game whose dynamics are induced by an abstract simplicial complex \Delta on the vertices of a graph, where \Delta may be interpreted as encoding graph gluing data. These models generalize two classical chip-firing games: The Abelian sandpile model, where \Delta is disjoint collection of points, and the cluster firing model, where \Delta is a single simplex. Two fundamental properties of these classical models extend to arbitrary hereditary chip-firing models: stabilization is independent of firings chosen (the Abelian property) and each chip-firing equivalence class contains a unique recurrent configuration. We will present an explicit bijection between the recurrent configurations of a hereditary chip-firing model on a graph G and the spanning trees of G and, if time permits, we will discuss chip-firing via gluing in the context of binomial ideals and metric graphs.
Friday, October 19, 2012 - 15:00 , Location: Siles 005 , Tom Trotter , Georgia Tech , Organizer: Ernie Croot
Over the past 40 years, researchers have made many connections between the dimension of posets and the issue of planarity for graphs and diagrams, but there appears to be little work connecting dimension to structural graph theory. This situation has changed dramatically in the last several months. At the Robin Thomas birthday conference, Gwenael Joret, made the following striking conjecture, which has now been turned into a theorem: The dimension of a poset is bounded in terms of its height and the tree-width of its cover graph. In this talk, I will outline how Joret was led to this conjecture by the string of results on planarity. I will also sketch how the resolution of his conjecture points to a number of new problems, which should interest researchers in both communities.
Friday, October 12, 2012 - 15:05 , Location: Skiles 005 , Farbod Shokrieh , Georgia Tech , Organizer: Prasad Tetali
Associated to every finite graph G there is a canonical ideal which encodes the linear equivalences of divisors on G. We study this ideal and its associated initial ideal. We give an explicit description of their syzygy modules and the Betti numbers in terms of the "connected flags" of G. This resolves open questions posed by Postnikov-Shapiro, Perkinson-Perlmen-Wilmes, and Manjunath-Sturmfels. No prior knowledge in advanced commutative algebra will be assumed. This is a joint work with Fatemeh Mohammadi.
Thursday, September 27, 2012 - 12:05 , Location: Skiles 005 , Alan Frieze , Math, Carnegie Mellon University , Organizer: Prasad Tetali
We will discuss some problems related to coloring the edges or vertices of a random graph. In particular we will discuss results on (i) the game chromatic number; (ii) existence of rainbow Hamilton cycles; (iii) rainbow connection.                                                        (** Please come a few minutes earlier for a pizza lunch **)
Friday, September 21, 2012 - 15:05 , Location: Skiles 005 , Prasad Tetali , Georgia Tech , , Organizer: Prasad Tetali
 We introduce a general Minimum Linear Ordering Problem (MLOP): Given a nonnegative set function f on a finite set V, find a linear ordering on V such that the sum of the function values for all the suffixes is minimized. This problem generalizes well-known problems such as the Minimum Linear Arrangement, Min Sum Set Cover, and Multiple Intents Ranking. Extending a result of Feige, Lovasz, and Tetali (2004) on Min Sum Set Cover, we show that the greedy algorithm provides a factor 4 approximate optimal solution when the cost function f is supermodular. We also present a factor 2 rounding algorithm for MLOP with a monotone submodular cost function, while the non monotone case remains wide open.  This is joint work with Satoru Iwata and Pushkar Tripathi. 
Friday, September 7, 2012 - 15:05 , Location: Skiles 005 , Will Perkins , School of Mathematics, Georgia Tech , Organizer: Prasad Tetali
We study an Achlioptas-process version of the random k-SAT process: a bounded number of k-CNF clauses are drawn uniformly at random at each step, and exactly one added to the growing formula according to a particular rule. We prove the existence of a rule that shifts the satisfiability threshold. This extends a well-studied area of probabilistic combinatorics and random graphs to random CSP's. In particular, while a rule to delay the 2-SAT threshold was known previously, this is the first proof of a rule to shift the threshold of a CSP that is NP-hard. We then propose a gap decision problem based upon this semi-random model with the aim of investigating the hardness of the random k-SAT decision problem.