Combinatorics Seminar
When: Sunday, January 24, 10am
Where: Schreiber 309
Speaker: Uli Wagner, ETH Zurich
Title: Complete Minors in Hypergraphs and Simplicial
Complexes
Abstract:
Given that minors are a truly fundamental concept in graph theory,
it is very natural to wonder how one should define minors of
hypergraphs (or simplicial complexes, depending on your background
and preferences).
One motivation are relations between embeddability problems and
combinatorics, as exemplified by the characterization of planar
graphs in terms of forbidden minors, or the basic fact that the
number of edges of a simple planar graph is at most linear
(in the number of vertices).
There is evidence that there is no higher-dimensional analogue of
the former (at least not in the sense of a "good
characterization").
The latter question is also wide open in higher dimensions. The
first open case is d=4:
QUESTION 1. What is the maximum number of faces of a hypergraph on
n vertices that embeds into R^4?
The conjectural answer, O(n^2), would have a number of interesting
consequences (including a higher-dimensional "crossing lemma").
It is natural to approach this problem via forbidden minors. The
challenge is to define an appropriate notion of minors for
hypergraphs. We survey some existing definitions and outline
the difficulties that arise when trying to apply them to the above
problem. Inspired by recent work of Nevo, we then propose a new
notion of "homological minors" and reduce Question 1 to
the following generalization of results of Mader and others for
graphs:
CONJECTURE 2. A 2-dimensional simplicial complex (3-uniform
hypergraph) with #triangles > C(t) #edges contains a complete
2-dimensional homological minor on t vertices, where C(t) is
a constant depending only on t.
We prove this conjecture for a large class complexes that satisfy
a mild regularity property. In particular, it holds almost surely
for random complexes (in the Linial-Meshulam and similar models).
We also obtain analogous results in higher dimensions.