Seminars and Colloquia by Series

Tree-width and Dimension - Part 1

Series
Combinatorics Seminar
Time
Friday, October 19, 2012 - 15:00 for 1 hour (actually 50 minutes)
Location
Siles 005
Speaker
Tom Trotter – Georgia Tech
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.

Divisors on graphs, connected flags, and syzygies

Series
Combinatorics Seminar
Time
Friday, October 12, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Farbod Shokrieh – Georgia Tech
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.

Some coloring problems on random graphs

Series
Combinatorics Seminar
Time
Thursday, September 27, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Alan Frieze – Math, Carnegie Mellon University
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 **)

Minimum linear ordering problems under submodular costs

Series
Combinatorics Seminar
Time
Friday, September 21, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Prasad Tetali – Georgia Tech –
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.

Random k-SAT and the Power of Two Choices

Series
Combinatorics Seminar
Time
Friday, September 7, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Will Perkins – School of Mathematics, Georgia Tech
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.

How to find counterfeit coins? An algorithmic version

Series
Combinatorics Seminar
Time
Friday, August 31, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jeong Han Kim – Professor, Yonsei University, South Korea
In this talk, we consider a well-known combinatorial search problem. Suppose that there are n identical looking coins and some of them are counterfeit. The weights of all authentic coins are the same and known a priori. The weights of counterfeit coins vary but different from the weight of an authentic coin. Without loss of generality, we may assume the weight of authentic coins is 0. The problem is to find all counterfeit coins by weighing (queries) sets of coins on a spring scale. Finding the optimal number of queries is difficult even when there are only 2 counterfeit coins. We introduce a polynomial time randomized algorithm to find all counterfeit coins when the number of them is known to be at most m \geq 2 and the weight w(c) of each counterfeit coin c satisfies \alpha \leq |w(c)| \leq \beta for fixed constants \alpha, \beta > 0. The query complexity of the algorithm is O(\frac{m \log n }{\log m}), which is optimal up to a constant factor. The algorithm uses, in part, random walks. The algorithm may be generalized to find all edges of a hidden weighted graph using a similar type of queries. This graph finding algorithm has various applications including DNA sequencing.

Towards Sarkozy's Problem

Series
Combinatorics Seminar
Time
Friday, April 27, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ernie Croot – School of Math, Ga Tech –
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.

Matchings in hypergraphs

Series
Combinatorics Seminar
Time
Friday, April 20, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Tomasz Luczak – Emory University and Adam Mickiewicz University, Poznan –
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.

The size of a hypergraph and its matching number

Series
Combinatorics Seminar
Time
Friday, April 13, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Huang Hao – Math, UCLA
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

The interaction of diagonal defect clusters in a dimer system on the square lattice

Series
Combinatorics Seminar
Time
Friday, March 16, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Mihai Ciucu – Mathematics, Indiana University, Bloomington, IN
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.

Pages