## Seminars and Colloquia by Series

Wednesday, October 20, 2010 - 15:05 , Location: Skiles 269 , Jacob Fox , Math, MIT , Organizer: Prasad Tetali
Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n^h) copies of H can be made H-free by removing o(n^2) edges. We give a new proof which avoids Szemeredi’s regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.
Thursday, October 14, 2010 - 11:05 , Location: Skiles 114 , Kevin Milans , University of South Carolina , Organizer: Xingxing Yu
A rooted tree is _k-ary_ if all non-leaves have k children; it is_complete_ if all leaves have the same distance from the root.  Let T bethe complete ternary tree of depth n.  If each edge in T is labeled 0 or1, then the labels along the edges of a path from the root to a leafform a "path label" in {0,1}^n.  Let f(n) be the maximum, over all{0,1}-edge-labeled complete ternary trees T with depth n, of the minimumnumber of distinct path labels on a complete binary subtree of depth nin T.The problem of bounding f(n) arose in studying a problem incomputability theory, where it was hoped that f(n)/2^n tends to 0 as ngrows.  This is true; we show that f(n)/2^n  is O(2^{-c \sqrt(n)}) forsome positive constant c.  From below, we show that f(n) >= (1.548)^nfor sufficiently large n.  This is joint work with Rod Downey, NoamGreenberg, and Carl Jockusch.
Friday, October 8, 2010 - 15:05 , Location: Skiles 255 , Guantao Chen , Department of Mathematics and Statistics, Georgia State University , Organizer: Xingxing Yu
In 1993 Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degree d \ge 4 then G has a cycle of length \Omega(n^{\log_{d-1} 2}). In this talk, I will report progresses on this conjecture and related problems.
Friday, September 24, 2010 - 15:05 , Location: Skiles 255 , Svetlana Poznanovikj , SoM, Georgia Tech , Organizer: Prasad Tetali
A set partition of [n] can be represented graphically by drawing n dots on a horizontal line and connecting the points in a same block by arcs. Crossings and nestings are then pairs of arcs that cross or nest. Let G be an abelian group, and \alpha, \beta \in G. In this talk I will look at the distribution of the statistic s_{\alpha, \beta} = \alpha * cr + \beta * ne on subtrees of the tree of all set partitions and present a result which says that the distribution of s_{\alpha, \beta} on a subtree is determined by its distribution on the first two levels.
Friday, September 17, 2010 - 15:05 , Location: Skiles 255 , Jerry Griggs, Carolina Distinguished Professor and Chair , Mathematics, University of South Carolina , Organizer: Prasad Tetali
Given a finite poset $P$, we consider the largest size ${\rm La}(n,P)$ of a family of subsets of $[n]:=\{1,\ldots,n\}$ that contains no  subposet $HP. Sperner's Theorem (1928) gives that${\rm La}(n,P_2)= {n\choose{\lfloor n/2\rfloor}}$, where$P_2$is the two-element chain. This problem has been studied intensively in recent years, and it is conjectured that$\pi(P):=  \lim_{n\rightarrow\infty} {\rm La}(n,P)/{n\choose{\lfloor n/2\rfloor}}$exists for general posets$P$, and, moreover, it is an integer. For$k\ge2$let$D_k$denote the$k$-diamond poset$\{A< B_1,\ldots,B_k < C\}$. We study the average number of times a random full chain meets a$P$-free family, called the Lubell function, and use it for$P=D_k$to determine$\pi(D_k)$for infinitely many values$k$. A stubborn open problem is to show that$\pi(D_2)=2$; here we prove$\pi(D_2)<2.273$(if it exists). This is joint work with Wei-Tian Li and Linyuan Lu of University of South Carolina. Friday, September 10, 2010 - 15:05 , Location: Skiles 255 , Kevin Costello , SoM, Georgia Tech , Organizer: Prasad Tetali Many of the simplest and easiest implemented approximation algorithms can be thought of as derandomizations of the naive random algorithm. Here we consider the question of whether performing the algorithm on a random reordering of the variables provides an improvement in the worst case expected performance. (1) For Johnson's algorithm for Maximum Satisfiability, we show this is indeed the case: While in the worst case Johnson's algorithm only provides a 2/3 approximation, the additional randomization step guarantees a 2/3+c approximation for some positive c. (2) For the greedy algorithm for MAX-CUT, we show to the contrary that the randomized version does NOT provide a 1/2+c approximation for any c on general graphs. This is in contrast to a result of Mathieu and Schudy showing it provides a 1-epsilon approximation on dense graphs. Joint with Asaf Shapira and Prasad Tetali. Friday, May 7, 2010 - 15:05 , Location: Skiles 255 , David Howard , School of Math, Georgia Tech , Organizer: Prasad Tetali In the paper "On the Size of Maximal Chains and the Number of Pariwise Disjoint Maximal Antichains" Duffus and Sands proved the following:If P is a poset whose maximal chain lengths lie in the interval [n,n+(n-2)/(k-2)] for some n>=k>=3 then there exist k disjoint maximal antichains in P. Furthermore this interval is tight. At the end of the paper they conjecture whether the dual statement is true (swap the words chain and antichain in the theorem). In this talk I will prove the dual and if time allows I will show a stronger version of both theorems. Friday, April 30, 2010 - 15:05 , Location: Skiles 255 , Edyta Szymanska , Adam Mickiewicz University , Organizer: Xingxing Yu In the talk we will consider the problem of deciding whether agiven$r$-uniform hypergraph$H$with minimum vertex degree atleast$c|V(H)|$, has a vertex 2-coloring. This problem has beenknown also as the Property B of a hypergraph. Motivated by an oldresult of Edwards for graphs, we summarize what can be deducedfrom his method about the complexity of the problem for densehypergraphs. We obtain the optimal dichotomy results for2-colorings of$r$-uniform hypergraphs when$r=3,4,\$ and 5. During the talk we will present the NP-completeness results followed bypolynomial time algorithms for the problems above  the thresholdvalue. The coloring algorithms rely on the known Tur\'{a}n numbersfor graphs and hypergraphs and the hypergraph removal lemma.
Friday, April 23, 2010 - 15:05 , Location: Skiles 255 , Paul Horn , Emory University , Organizer: Xingxing Yu
Erd\H{o}s and R\'enyi observed that a curious phase transition in the size of the largest component in arandom graph G(n,p): If pn < 1, then all components have size O(\log n), while if pn > 1 there exists a uniquecomponent of size \Theta(n).  Similar transitions can be seen to exist when taking random subgraphs of socalled (n,d,\lambda) graphs (Frieze, Krivelevich and Martin), dense graphs (Bollobas et. al) and several otherspecial classes of graphs.  Here we consider the story for graphs which are sparser and irregular.  In thisregime, the answer will depend on our definition of a 'giant component'; but we will show a phase transitionfor graphs satisfying a mild spectral condition.  In particular, we present some results which supersede ourearlier results in that they have weaker hypotheses and (in some sense) prove stronger results.  Additionally,we construct some examples showing  the necessity of our new hypothesis.
Friday, April 16, 2010 - 15:05 , Location: Skiles 255 , Alex Samordnitsky , Professor, Hebrew University (Jerusalem, Israel) , Organizer: Prasad Tetali
The Faber-Krahn problem for the cube deals with understanding the function, Lambda(t) = the maximal eigenvalue of an induced t-vertex subgraph of the cube  (maximum over all such subgraphs).  We will describe bounds on Lambda(t), discuss connections to isoperimetry and coding theory, and present some conjectures.