2021/05/11 by Jesse Geneson, Geneson, Jesse
Mathematics · #05D99 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.2105.04864
openalex publication_date 2021/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we define a notion of containment and avoidance for subsets of\n\ℝ2. Then we introduce a new, continuous and super-additive extremal\nfunction for subsets P \⊆ \ℝ2 called px(n, P), which is the\nsupremum of \μ2(S) over all open P-free subsets S \⊆ [0, n]2,\nwhere \μ2(S) denotes the Lebesgue measure of S in \ℝ2. We show\nthat px(n, P) fully encompasses the Zarankiewicz problem and more generally\nthe 0-1 matrix extremal function ex(n, M) up to a constant factor. More\nspecifically, we define a natural correspondence between finite subsets P\n\⊆ \ℝ2 and 0-1 matrices MP, and we prove that px(n, P) =\n\Θ(ex(n, MP)) for all finite subsets P \⊆ \ℝ2, where\nthe constants in the bounds depend only on the distances between the points in\nP.\n We also discuss bounded infinite subsets P for which px(n, P) grows\nfaster than ex(n, M) for all fixed 0-1 matrices M. In particular, we show\nthat px(n, P) = \Θ(n2) for any open subset P \⊆ \ℝ2.\nWe prove an even stronger result, that if QP is the set of points with\nrational coordinates in any open subset P \⊆ \ℝ2, then px(n,\nQP) = \Θ(n2). Finally, we obtain a strengthening of the\nK Hovari-S 'os-Tur 'an theorem that applies to infinite subsets of\n\ℝ2. Specifically, for subsets Ps, t, c \⊆ \ℝ2\nconsisting of t horizontal line segments of length s with left endpoints on\nthe same vertical line with consecutive segments a distance of c apart, we\nprove that px(n, Ps, t,c) = O(s\(1)/(t)n2-\(1)/(t)), where the\nconstant in the bound depends on t and c. When t = 2, we show that this\nbound is sharp up to a constant factor that depends on c.\n