Minimum blocking sets for families of partitions

2025/05/21 by Quintero, Guillermo Gamboa, Kantor, Ida
#05D15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2505.15362

Abstract

A 3-partition of an n-element set V is a triple of pairwise disjoint nonempty subsets X,Y,Z such that V=X∪ Y∪ Z. We determine the minimum size φ₃(n) of a set E of triples such that for every 3-partition X,Y,Z of the set \1,…,n\, there is some \x,y,z\∈ E with x∈ X, y∈ Y, and z∈ Z. In particular, φ₃(n)=\lceil(n(n-2))/(3)\rceil. For d>3, one may define an analogous number φ_d(n). We determine the order of magnitude of φ_d(n), and prove the following upper and lower bounds, for d>3: \frac2 n^d-1d! -o(n^d-1) ≤ φ_d(n) ≤ (0.86)/((d-1)!)n^d-1+o(n^d-1).

Citations

• Metric spaces in which many triangles are degenerate
• Hypergraph cuts above the average
• The Turán number of sparse spanning graphs
• Embedding large subgraphs into dense graphs

Related

• On the packing for triples
• Families of sets with no matchings of sizes 3 and 4
• Tight bounds for judicious 3-partitions of graphs
• A complete solution of the Erdős-Kleitman matching problem for n≤ 3s
• Non-trivial 3-wise intersecting uniform families