- You are here:
- GT Home
- Home
- News & Events

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.

Series: Combinatorics Seminar

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.