Seminars and Colloquia by Series

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.
Friday, January 29, 2010 - 15:05 , Location: Skiles 255 , Blair Dowling Sullivan , Oak Ridge National Labs , Organizer: Prasad Tetali
One of the biggest hurdles in high performance computing today is the analysis of massive quantities of data. As the size of the datasets grows to petascale (and beyond), new techniques are needed to efficiently compute meaningful information from the raw data. Graph-based data (which is ubiquitous in social networks, biological interaction networks, etc) poses additional challenges due to the difficulty of parallelizing many common graph algorithms. A key component in success is the generation of "realistic" random data sets for testing and benchmarking new algorithms. The R-MAT graph generator introduced by Chakrabarti, Faloutsos, and Zhan (2004) offers a simple, fast method for generating very large directed graphs. One commonly held belief regarding graphs produced by R-MAT is that they are "scale free"; in other words, their degree distribution follows a power law as is observed in many real world networks. These properties have made R-MAT a popular choice for generating graphs for use in a variety of research disciplines including graph theoretic benchmarks, social network analysis, computational biology, and network monitoring. However, despite its wide usage and elegant, parsimonius design, our recent work provides the first rigorous mathematical analysis of the degree distributions of the generated graphs. Applying results from occupancy problems in probability theory, we derive exact expressions for the degree distributions and other parameters. We also prove that in the limit (as the number of vertices tends to infinity), graphs generated with R-MAT have degree distributions that can be expressed as a mixture of normal distributions. This talk will focus on the techniques used in solving this applied problem in terms of classical "ball and urn" results, including a minor extension of Chistyakov's theorem.
Friday, January 22, 2010 - 15:05 , Location: Skiles 255 , Keni-chi Kawarabayashi , National Institute of Informatics , Organizer: Prasad Tetali
Hajos' conjecture is false, and it seems that graphs without a subdivision of a big complete graph do not behave as well as those without a minor of a big complete graph. In fact, the graph minor theorem (a proof of Wagner's conjecture) is not true if we replace the minor relation by the subdivision relation. I.e, For every infinite sequence G_1,G_2, ... of graphs, there exist distinct integers i < j such that G_i is a minor of G_j, but if we replace ''minor" by ''subdivision", this is no longer true. This is partially because we do not really know what the graphs without a subdivision of a big complete graph look like. In this talk, we shall discuss this issue. In particular, assuming some moderate connectivity condition, we can say something, which we will present in this talk. Topics also include coloring graphs without a subdivision of a large complete graph, and some algorithmic aspects. Some of the results are joint work with Theo Muller.
Friday, November 20, 2009 - 15:05 , Location: Skiles 255 , Mark Ellingham , Vanderbilt University , Organizer: Xingxing Yu

Linkage involves finding a set of internally disjoint paths in a graph with specified endpoints. Given graphs G and H, we say G is H-linked if for every injective mapping f:V(H) -> V(G) we can find a subgraph H' of G which is a subdivision of H, with f(v) being the vertex of H' corresponding to each vertex v of H. We describe two results on H-linkage for small graphs H.

(1) Goddard showed that 4-connected planar triangulations are 4-ordered, or in other words C_4-linked. We strengthen this by showing that 4-connected planar triangulations are (K_4-e)-linked.

(2) Xingxing Yu characterized certain graphs related to P_4-linkage. We use his characterization to show that every 7-connected graph is P_4-linked, and to construct 6-connected graphs that are not P_4-linked.

This is joint work with Michael D. Plummer and Gexin Yu.