Seminars and Colloquia by Series

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.
Friday, August 31, 2012 - 15:05 , Location: Skiles 005 , Jeong Han Kim , Professor, Yonsei University, South Korea , Organizer: Prasad Tetali
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.
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.