Georgia Institute of Technology College of Sciences

This talk is part of the Atlanta Combinatorics Colloquium. Note the time (4pm) and location (Instructional Center 105).

It is easy to partition the vertices of any graph into two sets where each vertex has at least as many neighbours across as on its own side; take any maximal cut! Can we do the opposite? This is not possible in general, but Füredi conjectured in 1988 that it should nevertheless be possible on a random graph. I shall talk about our recent proof of Füredi's conjecture: with high probability, the random graph $G(n,1/2)$ on an even number of vertices admits a partition of its vertex set into two parts of equal size in which $n−o(n)$ vertices have more neighbours on their own side than across.

Dirac proved that every $n$-vertex graph with minimum degree at least $n/2$ contains a hamiltonian cycle. Moreover, every graph with minimum degree $k \geq 2$ contains a cycle of length at least $k+1$, and this can be further improved if the graph is 2-connected. In this talk, we prove analogs of these theorems for hypergraphs. That is, we give sharp minimum degree conditions that imply the existence of long Berge cycles in uniform hypergraphs. This is joint work with Alexandr Kostochka and Grace McCourt.

I will discuss an old conjecture of Ron Graham on whether there are infinitely many integers $n$ so that $\mathrm{gcd}({{2n} \choose n}, 105)=1$, as well as recent progress on a version of this problem where 105 is replaced with a product of $r$ distinct primes. This is joint work with Hamed Mousavi and Maxie Schmidt.

Let T be a set of n triangles in 3-space, and let \Gamma be a family of
algebraic arcs of constant complexity in 3-space. We show how to preprocess T
into a data structure that supports various "intersection queries" for
query arcs \gamma \in \Gamma, such as detecting whether \gamma intersects any
triangle of T, reporting all such triangles, counting the number of
intersection points between \gamma and the triangles of T, or returning the
first triangle intersected by a directed arc \gamma, if any (i.e., answering
arc-shooting queries). Our technique is based on polynomial partitioning and
other tools from real algebraic geometry, among which is the cylindrical
algebraic decomposition.

Our approach can be extended to many other intersection-searching problems in
three and higher dimensions. We exemplify this versatility by giving an
efficient data structure for answering segment-intersection queries amid a set
of spherical caps in 3-space, and we lay a roadmap for extending our approach
to other intersection-searching problems.

Joint work with Pankaj Agarwal, Boris Aronov, Matya Katz, and Micha Sharir.