Intersecting families with large covering number - On a conjecture of Frankl, Ota, and Tokushige
Abstract
Stability theorems on intersecting families are often formulated via the covering number of set families. Let M(n,k,t) denote the maximum size of a k-uniform intersecting family ℱ⊆ binom[n]k with covering number t. It is known that for any fixed t and fixed k sufficiently large relative to t, one has M(n,k,t)=(pt−1(k)+o(1))(k)binomnk as n tends to infinity, where pt−1(k) is the maximum number of covers of size t−1 that a k-uniform intersecting family can have provided its covering number is t−1. Frankl, Ota, and Tokushige conjectured that pt(k)=kt−binomt2kt−1+Ot(kt−2) for fixed t as k tends to infinity and they also showed that pt(k)=kt−b(t)kt−1+Ot(kt−2), where b(t) is defined as the extremum of the following minimization problem. Suppose a k-uniform intersecting family ℱ of covering number t can be partitioned into ℱ1,…,ℱt such that for every i there exists a set Xi with Xi ⊆ Fi for all Fi∈ℱi and the Xi's are pairwise disjoint and non-empty. Then b(t) is the minimum of ∑i=1t(k−|Xi|) over all such families, partitions and Xi's. In accordance with the conjecture on pt(k), Frankl, Ota, and Tokushige conjectured b(t)=binomt2 for all t≥ 2 and proved 1/√2⌊ (t−1)/2⌋3/2≤ b(t)≤ binomt2. In this note, we present a counterexample to the conjecture showing b(t)≤ 2√2 t3/2√(log t) +O(t3/2) and improve the lower bound to 2/33/4t3/2−O(t)≤ b(t). The counterexample was found by ChatGPT 6.1Sol, the lower bound proof is due to the human author.
Related
- Large Maximal Intersecting Families with Covering Number Three
- The maximum size of intersecting k-graphs with covering number k
- A Sharp Product Bound for Disjoint Cross-Intersecting 3-Graphs with Covering Number Three
- Alon's conjecture on intersecting families of graphs
- On the Frankl--Tokushige conjecture and almost complete r-cross t-intersection theorems for vector spaces
BibTeX
@misc{patkos2026intersecting,
title = {{Intersecting families with large covering number - On a conjecture of Frankl, Ota, and Tokushige}},
author = {Balázs Patkós},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28029},
eprint = {2610.28029},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28029},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Intersecting families with large covering number - On a conjecture of Frankl, Ota, and Tokushige
AU - Balázs Patkós
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28029
UR - https://arxiv.org/abs/2610.28029
AB - Stability theorems on intersecting families are often formulated via the covering number of set families. Let M(n,k,t) denote the maximum size of a k-uniform intersecting family ℱ⊆ binom[n]k with covering number t. It is known that for any fixed t and fixed k sufficiently large relative to t, one has M(n,k,t)=(p_t−1(k)+o(1))(k)binomnk as n tends to infinity, where p_t−1(k) is the maximum number of covers of size t−1 that a k-uniform intersecting family can have provided its covering number is t−1. Frankl, Ota, and Tokushige conjectured that p_t(k)=k^t−binomt2k^t−1+O_t(k^t−2) for fixed t as k tends to infinity and they also showed that p_t(k)=k^t−b(t)k^t−1+O_t(k^t−2), where b(t) is defined as the extremum of the following minimization problem. Suppose a k-uniform intersecting family ℱ of covering number t can be partitioned into ℱ_1,…,ℱ_t such that for every i there exists a set X_i with X_i ⊆ F_i for all F_i∈ℱ_i and the X_i's are pairwise disjoint and non-empty. Then b(t) is the minimum of ∑_i=1^t(k−|X_i|) over all such families, partitions and X_i's. In accordance with the conjecture on p_t(k), Frankl, Ota, and Tokushige conjectured b(t)=binomt2 for all t≥ 2 and proved 1/√2⌊ (t−1)/2⌋^3/2≤ b(t)≤ binomt2. In this note, we present a counterexample to the conjecture showing b(t)≤ 2√2 t^3/2√(log t) +O(t^3/2) and improve the lower bound to 2/3^3/4t^3/2−O(t)≤ b(t). The counterexample was found by ChatGPT 6.1Sol, the lower bound proof is due to the human author.
ER -