Random partition for Tokushige’s r r -wise intersecting conjecture

Yongjiang Wu, Lihua Feng · 2026

Read Random partition for Tokushige’s r r -wise intersecting conjecture by Yongjiang Wu, Lihua Feng (2026) 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-2606-31075.txt.

Introduction

Wu and Feng settle a conjecture in extremal combinatorics. That field asks how large a structured family can be. The families here are sets of subsets. Any r of them must share at least one common element, so they are called r-wise intersecting families. Each element is included on its own, with its own probability, under a biased product measure. Tokushige had shown the largest such families are stars: sets that all contain one fixed element. His proof needed a restrictive hypothesis.

Tokushige conjectured the hypothesis could be weakened a lot. Wu and Feng prove the conjecture in full. Their key idea is a random partition method. It reduces the whole problem to at most r coordinates and solves those cases exactly. The method also covers cases where several coordinates are supercritical, too probable for earlier arguments to handle.

Catalog record

CREATORYongjiang Wu, Lihua Feng
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.31075

Browse the full library · About the Tower of Babel

Full text

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

Random partition for Tokushige’s r r -wise intersecting conjecture Lihua Feng was supported by the NSFC (Nos. 12271527 and 12471022) and NSF of Qinghai Province (No. 2025-ZJ-902T). E-mail addresses: [email protected] (Y. Wu), [email protected] (L. Feng). Yongjiang Wu, Lihua Feng Abstract Let r ≥ 3 r\geq 3 and let 1 > p 1 ≥ p 2 ≥ ⋯ ≥ p n > 0 1>p_{1}\geq p_{2}\geq\cdots\geq p_{n}>0 . Let μ 𝐩 \mu_{\mathbf{p}} denote the product measure on 2 [ n ] 2^{[n]} where each coordinate i i is included independently with probability p i p_{i} . A family 𝒜 ⊆ 2 [ n ] \mathcal{A}\subseteq 2^{[n]} is r r -wise intersecting if A 1 ∩ ⋯ ∩ A r ≠ ∅ A_{1}\cap\cdots\cap A_{r}\neq\emptyset for all A 1 , … , A r ∈ 𝒜 A_{1},\ldots,A_{r}\in\mathcal{A} . In 2022, Tokushige proved that if p 2 < r − 1 r p_{2}<\frac{r-1}{r} , then every r r -wise intersecting family 𝒜 ⊆ 2 [ n ] \mathcal{A}\subseteq 2^{[n]} satisfies μ 𝐩 ​ ( 𝒜 ) ≤ p 1 \mu_{\mathbf{p}}(\mathcal{A})\leq p_{1} , with equality only for stars centred at coordinates of maximum probability. He conjectured that the hypothesis p 2 < r − 1 r p_{2}<\frac{r-1}{r} can be replaced by p r + 1 < r − 1 r p_{r+1}<\frac{r-1}{r} . In this paper, we prove this conjecture in full. The key novelty is the introduction of a new random partition method, which reduces the problem to at most r r coordinates and solves it exactly, thereby fully covering all cases with multiple supercritical coordinates. AMS Classification : 05D05; 05C65 Keywords : r -wise intersecting family; Product measure; Random partition 1 Introduction For a probability vector \mathbf{p}=(p_{1},\ldots,p_{n})\in(0,1)^{n} and a family \mathcal{A}\subseteq 2^{[n]} , define the \mathbf{p} -biased measure \mu_{\mathbf{p}}(\mathcal{A})=\sum_{A\in\mathcal{A}}\prod_{i\in A}p_{i}\prod_{j\notin A}(1-p_{j}). When p_{1}=\cdots=p_{n}=p , this is the usual p -biased measure , denoted by \mu_{p} . A family \mathcal{A}\subseteq 2^{[n]} is called r -wise t -intersecting if |A_{1}\cap\cdots\cap A_{r}|\geq t\qquad\text{for all }A_{1},\ldots,A_{r}\in\mathcal{A}. When t=1 , this is the usual r -wise intersecting family ; when r=2 , it is the usual t -intersecting family ; when r=2 and t=1 , it is simply intersecting . The star centred at i is \mathcal{S}_{i}=\{A\subseteq[n]:i\in A\}. It is r -wise intersecting and has measure \mu_{\mathbf{p}}(\mathcal{S}_{i})=p_{i} . The p -biased measure formulation of intersection problems has been extensively studied. For the uniform bias 0<p<1 , Friedgut [ 5 ] developed a spectral approach, showing that for p\leq\frac{1}{t+1} , every t -intersecting family satisfies \mu_{p}(\mathcal{A})\leq p^{t} . The non-uniform version was introduced by Fishburn, Frankl, Freed, Lagarias and Odlyzko [ 3 ] , who proved that if p_{1}\geq\cdots\geq p_{n} and p_{2}\leq\frac{1}{2} , then every intersecting family satisfies \mu_{\mathbf{p}}(\mathcal{A})\leq p_{1} . Suda, Tanaka and Tokushige [ 6 ] later conjectured that the condition p_{2}\leq\frac{1}{2} can be relaxed to p_{3}\leq\frac{1}{2} . Tokushige [ 7 ] proved this conjecture under the additional assumptions p_{1}\leq 1/2 or 1-p_{2}>p_{3} , using the high-dimensional Hoffman bound of Filmus, Golubev and Lifshitz [ 2 ] . Very recently, Wu and Feng [ 8 ] confirmed the full conjecture using the generating set method, and moreover established a natural t -intersecting generalization. For r -wise intersecting families with r\geq 3 , Frankl and Tokushige [ 4 ] studied the uniform bias case, proving that if p\leq\frac{r-1}{r} , then every r -wise intersecting family satisfies \mu_{p}(\mathcal{A})\leq p . Filmus, Golubev and Lifshitz [ 2 ] later gave an alternative proof of this result using the high-dimensional Hoffman bound for hypergraphs. The related r -cross intersecting setting was also studied recently by Chang, Liu and Liu [ 1 ] . Tokushige [ 7 ] extended the Frankl-Tokushige theorem to the non-uniform setting. Theorem 1.1 (Tokushige [ 7 ] ) . Let r\geq 3 and let 1>p_{1}\geq\cdots\geq p_{n}>0 . If p_{2}<\frac{r-1}{r} and \mathcal{A}\subseteq 2^{[n]} is r -wise intersecting, then \mu_{\mathbf{p}}(\mathcal{A})\leq p_{1}. Moreover, equality holds if and only if \mathcal{A}=\mathcal{S}_{i} for some i\in[n] with p_{i}=p_{1} . Tokushige further conjectured that the hypothesis p_{2}<\frac{r-1}{r} can be replaced by p_{r+1}<\frac{r-1}{r} . In this paper, we prove this conjecture in full. Theorem 1.2 . Let r\geq 3 and let 1>p_{1}\geq\cdots\geq p_{n}>0 , and use the convention p_{i}=0 for i>n . Suppose that p_{r+1}<\frac{r-1}{r}. If \mathcal{A}\subseteq 2^{[n]} is r -wise intersecting, then \mu_{\mathbf{p}}(\mathcal{A})\leq p_{1}. Moreover, equality holds if and only if \mathcal{A}=\mathcal{S}_{i} for some i\in[n] with p_{i}=p_{1} . The new difficulty is the case in which several coordinates have probability larger than \frac{r-1}{r} . Our proof introduces a random partition method that solves the resulting finite linear program on at most r coordinates. The proof has two main components. We first replace the given family by its upset, allowing us to assume monotonicity and to raise all supercritical coordinates to the common maximum probability without decreasing the measure. We then apply a critical coupling, in the spirit of Chang, Liu and Liu [ 1 ] , to absorb all subcritical coordinates, namely those whose probabilities are at most \frac{r-1}{r} , into a single additive bound. This leaves only the supercritical coordinates, of which there are at most r by the hypothesis p_{r+1}<\frac{r-1}{r} . The resulting problem is a small linear program on these remaining coordinates, which we solve explicitly via a random partition argument. This gives a clean and self-contained proof of the extremal bound. The equality case requires additional work: we show that equality forces the top slice to be the whole tail cube, which in turn implies that the supports of the remaining slices form an (r-1) -wise intersecting family. This extra set-theoretic information collapses the equality face to a single common coordinate. This paper is organized as follows. Section 2 collects the preliminary tools, including the upset reduction and the critical additive bound. Section 3 introduces the slicing argument that reduces the problem to a finite linear program on the supercritical coordinates, and proves the key supercritical slice inequality using a random partition argument. Section 4 presents the collapse lemma and completes the proof of the main theorem. 2 Basic tools A family \mathcal{A}\subseteq 2^{[n]} is called increasing if it is closed under taking supersets: whenever A\in\mathcal{A} and A\subseteq B , we have B\in\mathcal{A} . The upset \mathcal{A}^{\uparrow} of \mathcal{A} is defined by \mathcal{A}^{\uparrow}=\{B\subseteq[n]:\text{there exists }A\in\mathcal{A}\text{ such that }A\subseteq B\}. We shall use the following standard facts about increasing families. Lemma 2.1 . Let \mathcal{A}\subseteq 2^{[n]} be r -wise intersecting. Then \mathcal{A}^{\uparrow} is r -wise intersecting and \mu_{\mathbf{p}}(\mathcal{A}^{\uparrow})\geq\mu_{\mathbf{p}}(\mathcal{A}) . If \mathcal{A} is increasing and a coordinate probability p_{j} is increased, then \mu_{\mathbf{p}}(\mathcal{A}) cannot decrease. More precisely, writing \mathcal{A}_{0}=\{A\subseteq[n]\setminus\{j\}:A\in\mathcal{A}\},\qquad\mathcal{A}_{1}=\{A\subseteq[n]\setminus\{j\}:A\cup\{j\}\in\mathcal{A}\}, we have \mathcal{A}_{0}\subseteq\mathcal{A}_{1} , and the measure is strictly increasing in p_{j} unless \mathcal{A}_{0}=\mathcal{A}_{1} . Proof. If B_{1},\ldots,B_{r}\in\mathcal{A}^{\uparrow} , choose A_{i}\in\mathcal{A} with A_{i}\subseteq B_{i} . Then \emptyset\neq A_{1}\cap\cdots\cap A_{r}\subseteq B_{1}\cap\cdots\cap B_{r}. Hence, \mathcal{A}^{\uparrow} is r -wise intersecting. For the measure inequality, observe that \mathcal{A}\subseteq\mathcal{A}^{\uparrow} . Since every atom of the product measure has positive weight, adding sets to a family can only increase its measure. It follows that \mu_{\mathbf{p}}(\mathcal{A}^{\uparrow})\geq\mu_{\mathbf{p}}(\mathcal{A}) . For monotonicity, condition on all coordinates except j . If \mathbf{p}_{-j} denotes the remaining probability vector, then \mu_{\mathbf{p}}(\mathcal{A})=(1-p_{j})\mu_{\mathbf{p}_{-j}}(\mathcal{A}_{0})+p_{j}\mu_{\mathbf{p}_{-j}}(\mathcal{A}_{1}). Since \mathcal{A} is increasing, \mathcal{A}_{0}\subseteq\mathcal{A}_{1} . Thus, the derivative with respect to p_{j} is \mu_{\mathbf{p}_{-j}}(\mathcal{A}_{1}\setminus\mathcal{A}_{0})\geq 0 , and it is zero only when \mathcal{A}_{1}=\mathcal{A}_{0} , because all

Read the complete text