## Seminars and Colloquia by Series

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. Friday, April 9, 2010 - 15:05 , Location: Skiles 255 , Mihai Ciucu , Professor, Indiana University, Bloomington , Organizer: Prasad Tetali In 1963 Fisher and Stephenson conjectured that the correlation function of two oppositely colored monomers in a sea of dimers on the square lattice is rotationally invariant in the scaling limit. More precisely, the conjecture states that if one of the monomers is fixed and the other recedes to infinity along a fixed ray, the correlation function is asymptotically$C d^(-1/2)$, where$d$is the Euclidean distance between the monomers and$C$is a constant independent of the slope of the ray. Shortly afterward Hartwig rigorously determined$C$when the ray is in a diagonal direction, and this remains the only direction settled in the literature. We generalize Hartwig's result to any finite collection of monomers along a diagonal direction. This can be regarded as a counterpart of a result of Zuber and Itzykson on n-spin correlations in the Ising model. A special case proves that two same-color monomers interact the way physicists predicted. Friday, April 2, 2010 - 15:05 , Location: Skiles 255 , Rodney Canfield , Professor, University of Georgia, Athens, GA , Organizer: Prasad Tetali I will divide the talk between two topics. The first is Stirling numbers of the second kind,$S(n,k)$. For each$n$the maximum$S(n,k)$is achieved either at a unique$k=K_n$, or is achieved twice consecutively at$k=K_n,K_n+1$. Call those$n$of the second kind {\it exceptional}. Is$n=2$the only exceptional integer? The second topic is$m\times n$nonnegative integer matrices all of whose rows sum to$s$and all of whose columns sum to$t$,$ms=nt$. We have an asymptotic formula for the number of these matrices, valid for various ranges of$(m,s;n,t)\$.  Although obtained by a lengthy calculation, the final formula is succinct and has an interesting probabilistic interpretation.  The work presented here is collaborative with Carl Pomerance and Brendan McKay, respectively.
Friday, March 5, 2010 - 15:00 , Location: Skiles 255 , Asaf Shapira , School of Mathematics, Georgia Tech , Organizer: Prasad Tetali
Let a_1,...,a_k satisfy a_1+...+a_k=1 and suppose a k-uniform hypergraph on n vertices satisfies the following property; in any partition of its vertices into k sets A_1,...,A_k of sizes a_1*n,...,a_k*n, the number of edges intersecting A_1,...,A_k is the number one would expect to find in a random k-uniform hypergraph. Can we then infer that H is quasi-random? We show that the answer is negative if and only if a_1=...=a_k=1/k. This resolves an open problem raised in 1991 by Chung and Graham [J. AMS '91]. While hypergraphs satisfying the property corresponding to a_1=...=a_k=1/k are not necessarily quasi-random, we manage to find a characterization of the hypergraphs satisfying this property. Somewhat surprisingly, it turns out that (essentially) there is a unique non quasi-random hypergraph satisfying this property. The proofs combine probabilistic and algebraic arguments with results from the theory of association schemes. Joint work with Raphy Yuster
Friday, February 26, 2010 - 15:05 , Location: Skiles 255 , Rui Xu , Department of Mathematics, University of West Georgia , Organizer: Prasad Tetali
The map coloring problem is one of the major catalysts of the tremendous development of graph theory. It was observed by Tutte that the problem of the face-coloring of an planar graph can be formulated in terms of integer flows of the graph. Since then the topic of integer flow has been one of the most attractive in graph theory. Tutte had three famous fascinating flow conjectures: the 3-flow conjecture, the 4-flow conjecture and the 5-flow conjecture. There are some partial results for these three conjectures. But in general, all these 3 conjectures are open. Group connectivity is a generalization of integer flow of graphs. It provides us with contractible flow configurations which play an important role in reducing the graph size for integer flow problems, it is also related to all generalized Tutte orientations of graphs. In this talk, I will present an introduction and survey on group connectivity of graphs as well as some open problems in this field.