Seminars and Colloquia by Series

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.

Friday, November 13, 2009 - 15:05 , Location: Skiles 255 , Miklos Simonovits , Alfred Renyi Institute, Budapest, Hungary , Organizer: Robin Thomas

Stability methods are often used in extremal graph theory, Ramsey theory and similar areas, where an extremal problem is to be solved and

  1. we have a conjecture about the structure of the conjectured extremal configurations and according to our conjecture, it has some given property \mathcal P;
  2. we can prove that all the almost extremal structures are near to the property \mathcal P, in some sense;
  3. if we knew that if a structure is near to the property \mathcal P and is extremal, then it is already the conjectured structure.

Of course, stability methods can also be used in other cases, but we restrict ourselves to the above two areas.

In my lecture I will give an introduction to the applications of the stability methods in extremal graph theory, describe cases in extremal graph theory, extremal hypergraph theory, in the Erdos-Frankl-Rold (= generalized Erdos-Kleitman-Rothschild theory) ...

In the second part of my lecture I shall describe the application of this method to the Erdos-Sos conjecture. This is part of our work with Ajtai, Komlos and Szemeredi.

Friday, November 6, 2009 - 15:05 , Location: Skiles 255 , Albert Bush , School of Mathematics, Georgia Tech , Organizer: Xingxing Yu

This is joint work with Dr. Yi Zhao.

Graph tiling problems can be summarized as follows: given a graph H, what conditions do we need to find a spanning subgraph of some larger graph G that consists entirely of disjoint copies of H. The most familiar example of a graph tiling problem is finding a matching in a graph. With the Regularity Lemma and the Blow-up Lemma as our main tools, we prove a degree condition that guarantees an arbitrary bipartite graph G will be tiled by an arbitrary bipartite graph H. We also prove this degree condition is best possible up to a constant. This answers a question of Zhao and proves an asymptotic version of a result of Kuhn and Osthus for bipartite graphs.