Minimum blocking sets for families of partitions

Guillermo Gamboa Quintero, Ida Kantor · 2025

Read Minimum blocking sets for families of partitions by Guillermo Gamboa Quintero, Ida Kantor (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-2505-15362.txt.

Introduction

Guillermo Gamboa Quintero and Ida Kantor solve a combinatorics problem about blocking sets in a 2025 paper. Take a set split into three nonempty parts in any way at all. A blocking set is a family of triples such that, no matter the split, at least one triple lands with one element in each part. The question asks for the smallest such family.

The authors find the exact minimum for three parts, given by a neat formula that rounds up a simple fraction of the set size. They then extend the question to splits into more than three parts and pin down the growth order of the minimum. Matching upper and lower bounds, apart from constant factors, frame the answer for all larger cases.

Catalog record

CREATORGuillermo Gamboa Quintero, Ida Kantor
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15362

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Minimum blocking sets for families of partitions Guillermo Gamboa Quintero, Ida Kantor Abstract A 3 3 -partition of an n n -element set V V is a triple of pairwise disjoint nonempty subsets X , Y , Z X,Y,Z such that V = X ∪ Y ∪ Z V=X\cup Y\cup Z . We determine the minimum size φ 3 ​ ( n ) \varphi_{3}(n) of a set ℰ \mathcal{E} of triples such that for every 3 3 -partition X , Y , Z X,Y,Z of the set { 1 , … , n } \{1,\dots,n\} , there is some { x , y , z } ∈ ℰ \{x,y,z\}\in\mathcal{E} with x ∈ X x\in X , y ∈ Y y\in Y , and z ∈ Z z\in Z . In particular, φ 3 ​ ( n ) = ⌈ n ⁡ ( n − 2 ) 3 ⌉ . \varphi_{3}(n)=\left\lceil\frac{n(n-2)}{3}\right\rceil. For d > 3 d>3 , one may define an analogous number φ d ​ ( n ) \varphi_{d}(n) . We determine the order of magnitude of φ d ​ ( n ) \varphi_{d}(n) , and prove the following upper and lower bounds, for d > 3 d>3 : 2 d ! ⋅ n d − 1 − o ⁡ ( n d − 1 ) ≤ φ d ​ ( n ) ≤ 0.86 ( d − 1 ) ! ⋅ n d − 1 + o ⁡ ( n d − 1 ) . \frac{2}{d!}\cdot n^{d-1}-o(n^{d-1})\leq\varphi_{d}(n)\leq\frac{0.86}{(d-1)!}\cdot n^{d-1}+o(n^{d-1}). 1 Minimum blocking set In this paper, we are interested in the following extremal problem: given n , find a smallest possible family \mathcal{E} of triples of elements of \{1,\dots,n\} such that whenever we partition \{1,\dots,n\} into three nonempty sets X,Y,Z , there is some triple \{x,y,z\}\in\mathcal{E} for which x\in X , y\in Y and z\in Z . We call such family a 3 -blocking set . Given a hypergraph \mathcal{H} , a transversal (or edge cover , or blocking set ) is a set of vertices that intersects all hyperedges of \mathcal{H} . Transversals are objects that have been thoroughly studied in discrete mathematics (see [ 1 , 4 , 11 , 12 , 15 , 16 ] for a selected bibliography). Naturally, one is looking for a tranversal of minimum possible size. Our problem is a particular instance of this: consider the auxiliary hypergraph where the vertices are all triples of numbers in \{1,\dots,n\} , and each hyperedge corresponds to the partition X,Y,Z of \{1,\dots,n\} into three nonempty parts: the corresponding hyperedge contains all triples that have one vertex in each of the three parts. For hypergraphs that are well-behaved, the asymptotic solution is known (see [ 9 ] or [ 18 ] , and many later papers). However, these results do not apply to our hypergraph, as it does not satisfy the conditions (it is far from regular, and the maximum codegree is close to the maximum degree). Our problem also has a strong connection to Turán theory of hypergraphs. If \mathcal{F} is a family of hypergraphs, then the Turán number {\rm ex}(n,\mathcal{F}) is the maximum number of edges in an n -vertex hypergraph that does not contain any hypergraph in \mathcal{F} as a subgraph. Turán numbers of hypergraphs are notoriously hard to handle (see, for example, the nice surveys [ 10 , 13 ] ) but in a lot of particular cases, a progress has been made. In our case, if B is a 3 -blocking set, its complement B^{\prime} (i.e., the family of triples that are not in B ) is a hypergraph that has no spanning complete 3 -partite subhypergraph. To see this, consider the case where B^{\prime} has such a subhypergraph with nonempty parts X,Y,Z . Then, it follows that B does not contain a triple of the form \{x,y,z\} for x\in X,y\in Y and z\in Z . So, we are looking for {\rm ex}(n,\mathcal{F}_{n}) , where \mathcal{F}_{n} is the family of all spanning 3 -partite 3 -uniform hypergraphs on n vertices. We have \binom{n}{3}-{\rm ex}(n,\mathcal{F}_{n})=\Theta(n^{2}) , but we are interested in determining this number exactly. Usually in Turán theory problems, the family \mathcal{F} is fixed and the same for all n , while in our case, the forbidden hypergraphs are spanning. Examples where the configuration in question is spanning include, e.g., theorems that specify conditions (in graphs or hypergraphs) that guarantee a Hamiltonian cycle, a packing by copies of a particular graph or the presence of a spanning subhypergraph of bounded degree (see, e.g., [ 14 , 19 , 2 ] ). We may define a d -blocking set analogously, as follows. Definition 1 . If V is a finite set and d\in\mathbb{N} , a d -partition of V is a d -tuple of sets \{X_{1},\dots,X_{d}\} that are all nonempty and pairwise disjoint, and V=X_{1}\cup\dots\cup X_{n} . The set of all d -element subsets of V will be denoted by \binom{V}{d} . Definition 2 . Let d be a positive integer. If \mathcal{E}\subseteq\binom{V}{d} , we say that \mathcal{E} blocks the d -partition \{X_{1},\dots,X_{d}\} if there is a d -tuple \{x_{1},\dots,x_{d}\}\in\mathcal{E} such that x_{i}\in X_{i} for all i . We call \mathcal{E} a d -blocking set if it blocks all d -partitions of V . Denote \varphi_{d}(n) the size of the smallest d -blocking set for an n -element set V . In a way, a d -blocking set is a natural generalization of a connected graph to d -uniform hypergraphs. If E is the edge set of a connected graph, then for every partition of vertices into two nonempty sets, we have an edge with one vertex in each set. In other words, the edge set of a connected graph is precisely what we call a 2 -blocking set. The minimum size of a connected graph on n vertices is, trivially, n-1 . There are many ways to extend the notion of connectivity to d -uniform hypergraphs. In most of these, determining the minimum size of a connected hypergraph is not too interesting. However, we may, inspired by previous paragraph, say that a d -uniform hypergraph is arch-connected if for every partition of the vertex set into d nonempty classes, there is an edge intersecting all classes. Determining the minimum number of edges in a hypergraph which is connected in this sense is the same as determining the size of minimum d -blocking set. Some related problems seem to have been considered in the literature, but while we are looking for a partition that minimizes the number of edges (of a given hypergraph) that intersect all parts, in some papers the aim is to maximize this number, or to minimize the number of edges that are not contained in one part, etc. See, e.g., [ 7 ] , [ 3 ] , or [ 17 ] . See also [ 8 ] for a related concept of partition-connectedness . Most of this paper concentrates on d=3 , which is the first non-trivial case of our problem. We determine the minimum size of a 3 -blocking set exactly, for all n . Theorem 1 . For all n , we have \varphi_{3}(n)=\left\lceil\frac{n(n-2)}{3}\right\rceil . For d>3 , we determine the order of magnitude for the

Read the complete text