Continuous Tur\'an numbers

arXiv2105.04864MaRDI QIDQ6367351FDOQ6367351

Authors: Jesse Geneson 

Publication date: 11 May 2021

Abstract: In this paper, we define a notion of containment and avoidance for subsets of $mathbb{R}^2$. Then we introduce a new, continuous and super-additive extremal function for subsets $Psubseteqmathbb{R}^2$ called $px(n,P)$, which is the supremum of $m{u}_2(S)$ over all open $P$-free subsets $Ssubseteq[0,n{]}^2$, where $m{u}_2(S)$ denotes the Lebesgue measure of $S$ in $mathbb{R}^2$. We show that $px(n,P)$ fully encompasses the Zarankiewicz problem and more generally the 0-1 matrix extremal function $ex(n,M)$ up to a constant factor. More specifically, we define a natural correspondence between finite subsets $Psubseteqmathbb{R}^2$ and 0-1 matrices $M_P$, and we prove that $px(n,P)=Theta(ex(n,M_P))$ for all finite subsets $Psubseteqmathbb{R}^2$, where the constants in the bounds depend only on the distances between the points in $P$. We also discuss bounded infinite subsets $P$ for which $px(n,P)$ grows faster than $ex(n,M)$ for all fixed 0-1 matrices $M$. In particular, we show that $px(n,P)=Theta(n^2)$ for any open subset $Psubseteqmathbb{R}^2$. We prove an even stronger result, that if $Q_P$ is the set of points with rational coordinates in any open subset $Psubseteqmathbb{R}^2$, then $px(n,Q_P)=Theta(n^2)$. Finally, we obtain a strengthening of the KH{o}vari-S'{o}s-Tur'{a}n theorem that applies to infinite subsets of $mathbb{R}^2$. Specifically, for subsets $P_{s,t,c}subseteqmathbb{R}^2$ consisting of $t$ horizontal line segments of length $s$ with left endpoints on the same vertical line with consecutive segments a distance of $c$ apart, we prove that $px(n,P_{s,t,c})=O(s^{frac1t}{n}^{2-frac1t})$, where the constant in the bound depends on $t$ and $c$. When $t=2$, we show that this bound is sharp up to a constant factor that depends on $c$.

Recommendations

• Some remarks on the Zarankiewicz problem
• A contribution to the Zarankiewicz problem
• A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem
• Zarankiewicz's problem for semi-algebraic hypergraphs
• On the Zarankiewicz problem for intersection hypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

This page was built for publication: Continuous Tur\'an numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367351)