Open Collections

Tight paths and matchings in convex geometric hypergraphs

Banff International Research Station for Mathematical Innovation and Discovery

A {\em convex geometric hypergraph} or {\em cgh} is a hypergraph whose vertices form a convex polygon in the plane. It will be convenient to place the vertices in clockwise order on the vertices of a regular polygon $\vb{\gamma}_n$ (for $n \ge 3$), and to write $v_1 < v_2 < \dots < v_n < v_1$ to denote that the clockwise ordering of the vertices $\vb{\gamma}_n$ is $(v_1,v_2,\dots,v_n,v_1)$. We write cgg (cgh, cg $r$-graph) as abbreviation for convex geometric graph (convex geometric hypergraph, convex geometric $r$-graph), Given an $r$-uniform cgh $F$, let $\ex_{\circlearrowright}(n,F)$ be the maximum number of edges in an $r$-uniform cgh on $n$ vertices that does not contain $F$. In the case of graphs, this problem has a rich history with applications to a variety of problems in combinatorial geometry. Extremal questions for convex geometric graphs and hypergraphs are connected to a variety of topics in discrete geometry (see for instance Bra{\ss}, Rote, and Swanepoel~2001, %\cite{Brass-Rote-Swanepoel}, Pach and Pinchasi~2013, %\cite{Pach-Pinchasi}) and questions around the triangle removal problem (see Section 4.3 in Aronov, Dujmovi\v{c}, Morin, Ooms and da Silveira~2017, %\cite{Aronov}, Gowers and Long~2016 %\cite{Gowers-Long} and Loh~2016). %\cite{Loh}) We focus on the case that $F$ is a certain type of embedding of a tight path or matching. We obtain in many cases asymptotically sharp estimates for $\ex_{\circlearrowright}(n,F)$, generalizing classical results of Kupitz and Perles. As a consequence, we show that the number of edges in an $n$-vertex $r$-graph containing no tight $k$-edge path is at most \[\frac{(k-1)(r - 1)}{r}{n \choose r - 1}.\] The case $r = 2$ is the Erd\H{o}s-Gallai Theorem. For $r \geq 3$, this is the first non-trivial upper bound on the extremal number for tight paths in $r$-graphs which applies for all $k \ge 3$, and marks progress towards Kalai's tight tree conjecture.

Mathematics; Convex and discrete geometry; Combinatorics

video/mp4

Author affiliation: Renyi Institute of Mathematics

2018-08-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/66668

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/