# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, April 19, 2010

Freie Universität Berlin
Institut für Informatik
Takustr. 9,
14195 Berlin
room 005

Lecture - 14:15

### Sharing joints, in moderation: A groundshaking clash between algebraic and combinatorial geometry

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

### 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. 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.

Letzte Aktualisierung: 12.04.2010