Monday, April 19, 2010
Freie Universität Berlin
Institut für Informatik
Takustr. 9,
14195 Berlin
room 005
Lecture - 14:15
Abstract:
About a year ago, Larry Guth and Nets Hawk Katz have obtained the
tight upper bound $O(n^{3/2})$ on the number of joints in a set of $n$
lines in 3-space, where a joint is a point incident to at least three
non-coplanar lines, thus closing the lid on a problem that has been
open for nearly 20 years. While this in itself is a significant
development, the groundbreaking nature of their work is the proof
technique, which uses fairly simple tools from algebraic geometry, a
totally new approach to combinatorial problems of this kind in
discrete geometry.
In this talk I will present a simplified version of the new machinery,
and the further results that we have so far obtained, by adapting and
exploiting the algebraic machinery.
The first main new result is: Given a set $L$ of $n$ lines in
$d$-dimensional space, the maximum number of joints in $L$ (points
incident to at least $d$ lines, not all in a common hyperplane) is
$\Theta(n^{d/(d-1)})$. The proof is almost ``trivial''.
The second main new result is: Given a set $L$ of $n$ lines in 3-space,
and a subset of $m$ joints of $L$, the number of incidences between these
joints and the lines of $L$ is $O(m^{1/3}n)$, which is worst-case tight
for $m\ge n$. In fact, this holds for any sets of $m$ points and $n$
lines, provided that each point is incident to at least three lines,
and no plane contains more than $O(n)$ points.
The third set of results is strongly related to the celebrated
problem of Erd{\H o}s on distinct distances in the plane. We reduce
this problem to a problem involving incidences between points and
helices (or parabolas) in 3-space, and formulate some conjectures
concerning the incidence bound. Settling these conjectures in the
affirmative would have almost solved Erd{\H o}s's problem. So far we
have several partial positive related results, which will be
presented in the talk.
Joint work with Haim Kaplan, Eugenii Shustin, and (the late) Gy\"orgy Elekes.
Colloquium - 16:00
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.
Our motivation is the interplay between the combinatorics of the
hypergraph/
simplicial complex and its topological properties, such as
embeddability into
Euclidean spaces of various dimension.
QUESTION 1. What is the maximum number of faces of a hypergraph on n
vertices that embeds topologically into R^4?
The conjectural answer, O(n^2), would have a number of interesting
consequences
(including a higher-dimensional "crossing lemma").
We propose an approach to this problem using a new notion of minors,
HOMOLOGICAL MINORS, which reduces the problem to the following
conjectural generalization of a result
of Mader for graphs:
CONJECTURE 2. A 2-dimensional simplicial complex (3-uniform
hypergraph) with
#triangles / #edges > C(t) contains a complete 2-dimensional minor on
t vertices, where
C(t) is a constant depending only on t.
Here, prove this conjecture for a large class complexes that satisfy a
certain quasirandomness 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.