Helly-type theorems for separated d d -intervals
Wei Rao · 2025
Read Helly-type theorems for separated d d -intervals by Wei Rao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-03207.txt.
Introduction
Wei Rao proved in 2025 a family of Helly-type theorems for a class of shapes built from intervals. A separated d-interval joins d disjoint convex pieces of the number line. Helly-type results say when local overlap forces a shared point for a whole family. Rao studies the convexity spaces these shapes form.
The paper settles several counting measures for these spaces, including the Radon and Helly numbers and their colorful and fractional forms. It also proves two kinds of colorful counting theorems of the (p,q) type. Proofs lean on simplicial complexes and a collapsing technique from topology. The results serve readers in discrete geometry who use interval structures to model scheduling and overlap.
Catalog record
| CREATOR | Wei Rao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-03207
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Helly-type theorems for separated d d -intervals Wei Rao Abstract A separated d d -interval is defined as a disjoint union of d d convex sets from the real line ℝ \mathbb{R} . In this paper, we establish a series of Helly-type theorems for convexity spaces derived from separated d d -intervals. Our results encompass the Radon number, Helly number, colorful Helly number, fractional Helly number, colorful fractional Helly theorem, ( p , q ) (p,q) theorem, and two kinds of colorful ( p , q ) (p,q) theorems for these convexity spaces. The primary tools employed in our proofs involve simplicial complexes and collapsibility. Keywords Helly theorem; (p,q) theorem; d -interval; convexity space 1 Introduction 1.1 Helly-type theorems and d -collapsibility In 1923, Helly [ Hel23 ] published a foundational theorem on the intersection patterns of convex sets in \mathbb{R}^{d} , where d is a positive integer. Specifically, for a finite family \mathcal{F} of convex sets in \mathbb{R}^{d} , Helly’s theorem states that if every at most d+1 members of \mathcal{F} have a non-empty intersection, then all members of \mathcal{F} intersect. Over the years, this result has been generalized and extended in various directions. Notable examples include the colorful Helly theorem, first proven by Lovász and later fully detailed by Bárány [ Bár82 ] ; the fractional Helly theorem introduced by Katchalski and Liu [ KL79 ] ; and the colorful fractional Helly theorem, also developed by Bárány et al. [ BFM+14 ] . Other significant advancements include the (p,q) theorem by Alon and Kleitman [ AK92 ] , as well as two variations of the colorful (p,q) theorems by Bárány and Matoušek [ BM03 ] and Bárány et al. [ BFM+14 ] , respectively. For more details, refer to [ BK22 , Bár21 ] . Rather than immediately delving into these theorems, we first introduce the concepts of abstract simplicial complex and d -collapsibility, which was introduced by Wegner in [ Weg75 ] . The d -collapsibility is a powerful tool for establishing a series of Helly-type theorems. Let V be a finite set. A collection K of subsets of V is an abstract simplicial complex if for any \alpha\in K and \beta\subseteq\alpha , we have \beta\in K . Elements of K are called faces of K . The dimension of a face \alpha\in K is defined as \dim\alpha\coloneqq|\alpha|-1 . The dimension of a complex K is defined as \dim K\coloneqq\max\{\dim\alpha:\alpha\in K\} . Let I be a finite set of indices and \mathcal{F} be a family of sets (C_{i})_{i\in I} . The nerve of \mathcal{F} is K(\mathcal{F})\coloneqq\{J\subseteq I:\bigcap_{j\in J}C_{j}\neq\emptyset,J\text{ is finite}\} . One can easily verify that the nerve is an abstract simplicial complex. A face \sigma\in K is free if it is contained in a unique inclusion-maximal face. An elementary d -collapse of K is a step in which a free face \sigma with \dim\sigma\leq d-1 and all faces containing \sigma are removed. Moreover, we denote the result by \coll(K,\sigma)=K\setminus\{\tau\in K:\sigma\subseteq\tau\} . A simplicial complex K is d -collapsible if K can be reduced to the empty complex by a sequence of elementary d -collapses. For more details on the notion related to d -collapsibility and the consequence of d -collapsibilty, refer to [ Tan13 ] . In this paper, we shall use the following recent result. Theorem 1.1 (The optimal colorful fractional Helly theorem for d -collapsible complexes [ BGT21 ] ) . Let K be a d -collapsible simplicial complex with the set of vertices N=N_{1}\sqcup\dots\sqcup N_{d+1} divided into d+1 disjoint subsets of sizes |N_{i}|=n_{i} , respectively. If K contains at least \alpha n_{1}\dots n_{d+1} colorful d -faces, where \alpha\in(0,1] , that is, faces \sigma with |\sigma\cap N_{i}|=1 for every i\in[d+1] . Then there is an index i\in[d+1] such that the dimension of the induced subcomplex on N_{i} is at least (1-(1-\alpha)^{1/(d+1)})n_{i}-1 , that is, \dim K[N_{i}]\geq(1-(1-\alpha)^{1/(d+1)})n_{i}-1 . 1.2 Separated d -intervals Now, we are ready to introduce our research subjects and some related results. A homogeneous d -interval is a union of at most d convex sets from the real line \mathbb{R} . A separated/nonhomogeneous d -interval is a homogeneous d -interval consisting of d convex set components I^{(1)},\dots,I^{(d)} such that I^{(i+1)}\subseteq(i,i+1) for 0\leq i\leq d-1 , where (i,i+1) is an open interval. For convenience, we employ the following equivalent definition. Definition 1.2 . A separated d -interval I is a disjoint union of d convex sets from the real line \mathbb{R} , that is, I=\bigsqcup_{i\in[d]}I^{(i)}=\bigcup_{i\in[d]}\{(x,i)\in\mathbb{R}\times[d]:x\in I^{(i)}\subseteq\mathbb{R}\} , where all I^{(i)} are convex sets in \mathbb{R} . Moreover, we say I^{(i)} is the i -th level of I and any point (x,i) , where x\in\mathbb{R} , is in the i -th level. The reader may realize that there is some relation between the axis-parallel boxes in \mathbb{R}^{d} and the separated d -intervals. For more details, refer to Section 10.2 . Let \mathcal{F} be a finite family of subsets on the ground set X . The transversal number of \mathcal{F} , denoted by \tau(\mathcal{F}) , is the minimum integer k such that there is a set S\subseteq X of size at most k such that S\cap C\neq\emptyset for any C\in\mathcal{F} . The matching number of \mathcal{F} , denoted by \nu(\mathcal{F}) , is the maximum integer k such that there is a subfamily \mathcal{F}^{\prime}\subseteq\mathcal{F} of size k , consisting of pairwise disjoint sets. Tardos [ Tar95 ] and Kaiser [ Kai97 ] proved the following results. Theorem 1.3 (Tardos [ Tar95 ] , Kaiser [ Kai97 ] ) . If \mathcal{F} is a finite family of homogeneous d -intervals, then \tau(\mathcal{F})\leq(d^{2}-d+1)\nu(\mathcal{F}) . If \mathcal{F} is a finite family of separated d -intervals, then \tau(\mathcal{F})\leq(d^{2}-d)\nu(\mathcal{F}) . Then Frick and Zerbib [ FZ19 ] established the colorful version. Recently, a sparse colorful version and a matroid colorings version were proven in [ MZ24 ] and [ McG24 ] , respectively. 1.3 Abstract convexity spaces and main results In this paper, we shall study the convexity spaces constructed on separated d -intervals. Moreover, throughout the paper, we will use the term d -intervals to refer to separated d -intervals. Definition 1.4 . A convexity space is a set system \mathcal{C} on a ground set X that satisfies the following three properties: 1. \emptyset,X\in\mathcal{C} ; 2. If \emptyset\neq\mathcal{D}\subseteq\mathcal{C} , then \bigcap\mathcal{D}\in\mathcal{C} ; 3. If \emptyset\neq\mathcal{D}\subseteq\mathcal{C} is totally ordered by inclusion, then \bigcup\mathcal{D}\in\mathcal{C} . Let (X,\mathcal{C}) be a convexity space. For any subset Y\subseteq X , the convex hull of Y is defined as \conv Y=\bigcap\{K:K\in\mathcal{C},Y\subseteq K\} . We call the members of \mathcal{C} convex sets . For example, when X=\mathbb{R}^{d} and \mathcal{C}(\mathbb{R}^{d}) is the set of all the usual convex sets in \mathbb{R}^{d} , space (\mathbb{R}^{d},\mathcal{C}(\mathbb{R}^{d})) is the standard convexity space, which is widely studied in convex geometry and combinatorial convexity. For a comprehensive introduction to the convexity space, refer to [ vDV93 , Hol24 ] . Let \mathbb{R}\times[d]=\bigcup_{i\in[d]}\{(x,i):x\in\mathbb{R}\} and P\subseteq\mathbb{R}\times[d] . Let \mathcal{C}_{\equiv}(P) be the set of all subsets of P of the form I\cap P where I is a d -interval, that is, \mathcal{C}_{\equiv}(P)=\{I\cap P:I\subseteq\mathbb{R}\times[d]\text{ is a $d$-interval}\}. One can easily verify that (P,\mathcal{C}_{\equiv}(P)) is a convexity space. Note that when P=\mathbb{R}\times[d] , set \mathcal{C}_{\equiv}(P) is the set of usual separated d -intervals defined above, which has been