Triangle-Intersecting Families III

Part 3 of 3. ← Part 2

Section 5 Notes

Odd-Linear-Dependency Families

Section Goal (Original).

In this section we prove Theorem 1.8.

Remark 110.

这一节把“奇环交”推广到“奇线性依赖交”，并保持同一套谱方法。

Odd-LD-Intersecting On Hypergraphs (Original).

A family

A1,\dots,A{2l+1}\in G\cap H

A1\triangle\cdots\triangle A{2l+1}=\emptyset.

Remark 111.

这相当于要求交集里存在“奇数条关系相加为零”的依赖结构。

Vector-Space Reformulation (Original).

Identifying subsets of$[n]$ with vectors in$\{0,1\}^n=\mathbb Z_2^n$, symmetric difference becomes vector addition. Equivalently, a family$\mathcal F$ of subsets of$\mathbb Z_2^n$ is odd-LD-intersecting if for any$S,T\in\mathcal F$ there exist$l\in\mathbb N$ and non-zero vectors

such that

Remark 112.

这里把组合定义变成了线性代数条件，后续傅里叶与 Cayley 分析自然可用。

Odd-LD-Agreeing And The Zero Vector (Original).

Similarly, odd-LD-agreeing is defined by replacing$S\cap T$ with$S\triangle T$. Since$0$ cannot appear in a non-trivial odd linear dependency, it is irrelevant; thus we work on

Remark 113.

剔除$0$ 向量后，结构更整齐，且不影响极值问题本质。

Skew Measure And Schur Structures (Original).

For$p\in[0,1]$ and$S\subset \mathbb Z_2^n\setminus\{0\}$,

We mainly use$\mu_{1/2}$, denoted by$\mu$. A Schur triple is$\{x,y,z\}$ with$x+y=z$ (equivalently$x+y+z=0$). A Schur junta is defined by prescribing intersection with a fixed Schur triple, and a Schur-umvirate consists of all sets containing a fixed Schur triple.

Remark 114.

Schur triple 在这里扮演三角形的角色；junta/umvirate 则是对应的极值结构候选。

Theorem 7 (Theorem 5.1 (Original)).

If$\mathcal F$ is an odd-LD-agreeing family of subsets of$\mathbb Z_2^n\setminus\{0\}$, then

Equality holds if and only if$\mathcal F$ is a Schur junta. Moreover, there exists a constant$c$ such that for any$\varepsilon>0$, if

then there exists a Schur junta$\mathcal T$ such that

Remark 115.

这是均匀测度下的完整“上界 + 唯一性 + 稳定性”结论。

Theorem 8 (Theorem 5.2 (Original)).

• [[Extremal families]] Let$p\le 1/2$. If$\mathcal F$ is odd-LD-intersecting in$\mathbb Z_2^n\setminus\{0\}$, then

Equality holds if and only if$\mathcal F$ is a Schur-umvirate.

• [[Stability]] There exists a constant$c$ such that for any$\varepsilon\ge 0$, if

then there exists a Schur-umvirate$\mathcal T$ such that

Remark 116.

这是偏置测度下的对应结论，数值上界变成$p^3$。

Lifting Back To Graph Families (Original).

Theorem 1.4 follows from Theorem 5.2 by lifting graph families: for odd-cycle-intersecting$\mathcal F$ of graphs, define

Then

and$\mathcal H$ is odd-LD-intersecting, since odd cycles lift to odd linear dependencies.

Remark 117.

这一步明确了 Section 5 和图论主定理之间的双向联系。

Why Section 5 Is Not Redundant (Original).

The paper notes that Theorem 5.1 does not seem deducible from Theorem 1.4; it is a bona-fide generalization. The setting is in some ways cleaner, since the ground set and its power set live inside a vector space over$\mathbb Z_2$.

Remark 118.

作者强调这里不是“换符号重述”，而是更自然、更统一的母框架。

Cayley Operators

Preliminaries On Vector Sets (Original).

For$S\subset \mathbb Z_2^n\setminus\{0\}$, write

Define

and

Remark 119.

抓“独立骨架”，$J(S)$ 抓“依赖部分”，后面分解公式正是围绕这个拆分。

Bilinear Form And Orthogonal Space (Original).

For$x,y\in\mathbb Z_2^n$,

For$S\subset \mathbb Z_2^n$,

with

Remark 120.

这给出了解空间维数计算的主工具。

Affine-Subspace Reminder (Original).

An affine subspace of$V$ is a set$U+a$ where$U$ is a subspace and$a\in V$. If$U$ has dimension$d$, then$U+a$ has dimension$d$. An affine subspace of dimension$n-1$ in an$n$-dimensional space is an affine hyperplane.

Remark 121.

后面的超平面构造都建立在这个术语上。

Lemma 10 (Lemma 5.3 (Original)).

If$S=\{v_1,\dots,v_d\}\subset \mathbb Z_2^n$ is linearly independent, then for any$r_1,\dots,r_d\in\{0,1\}$, the set

is a translate of$S^\perp$, and therefore an affine subspace of dimension$n-d$.

Proof.

For each$i\in[d]$, choose

Since$\dim((S\setminus\{v_i\})^\perp)=n-d+1$ and$\dim(S^\perp)=n-d$, such$y_i$ exists. Moreover,

Let

Then

as required.

∎

Remark 122.

这是“线性方程组解集 = 一个特解 + 齐次解空间”的$\mathbb Z_2$ 版本。

Lemma 11 (Lemma 5.4 (Original)).

An affine hyperplane of the form

contains no odd linear dependency.

Proof.

If$v_1,\dots,v_{2l+1}\in A_w$, then

Hence

∎

Remark 123.

这正是“二分图不含奇环”在线性空间里的同构结论。

Definition 6 (Definition 5.5 (Hyperplane Subset, Original)).

A hyperplane subset is a subset of some$A_w$, where$w\in\mathbb Z_2^n$.

Remark 124.

这是第5节里“bipartite graph”的替代对象。

Hyperplane Subsets As Bipartite Analogues (Original).

If$A$ is a hyperplane subset,$\mathcal F$ is odd-LD-agreeing, and$S\in\mathcal F$, then

Also, a bipartite graph with bipartition$(X,Y)$ is a subset of$A_w$ by taking$w_i=\mathbf 1_{\{i\in X\}}$.

Remark 125.

这句把“图上的二分结构”和“向量上的超平面结构”桥接起来了。

Random Hyperplane Slice (Original).

For uniform random$w\in\mathbb Z_2^n$ and$S\subset\{0,1\}^n$, define

This is the analogue of random-cut size in graphs, and if$S\subset[n]^{(2)}$, it is exactly random-cut size of$S$. Write$Q_S(X)$ for the probability-generating function of$Y_S$.

Remark 126.

第3节的 cut 统计在这里变成了 hyperplane-slice 统计。

OLDC Cayley Setup (Original).

We now have a Cayley graph on$\mathbb Z_2^{\{0,1\}^n\setminus\{0\}}$ with generating set

Remark 127.

这一步对应 Section 2 里从图族问题转成 Cayley 谱问题。

Definition 7 (Definition 5.6 (Odd-Linear-Dependency-Cayley Operator, Original)).

A linear operator$A$ on real-valued functions on$\mathbb Z_2^{\{0,1\}^n\setminus\{0\}}$ is called OLDC if:

1. if$\mathcal F$ is odd-LD-agreeing and$f$ is its indicator, then

2. the Fourier--Walsh basis is a complete eigenbasis of$A$.

The eigenvalue vector of an OLDC operator is called an OLDC spectrum.

Remark 128.

这是 OCC 概念在 LD 场景中的一一对应定义。

Corollary 8 (Corollary 5.7 (Original)).

Let$w$ be a uniform random vector in$\mathbb Z_2^n$ and

For$S\subset\mathbb Z_2^n$, define

For any$R\subset\mathbb Z_2^n$ with no non-trivial odd linear dependency, define

where$\cong$ means linear isomorphism in$\mathbb Z_2^n$. Then, for fixed$i$,

is an OLDC spectrum, and for fixed admissible$R$,

is also an OLDC spectrum.

Remark 129.

这就是 Section 2 的 Corollary 2.9 在 LD 框架中的完全镜像版。

Construction Of The OLDC Spectrum

Independence Input (Original).

If$S=\{v_1,\dots,v_d\}$ is linearly independent, then$\{\langle v_i,w\rangle:i\in[d]\}$ are independent$\mathrm{Bin}(1,1/2)$ random variables. Indeed, for any$r_1,\dots,r_d\in\{0,1\}$, Lemma 5.3 implies

is an affine subspace of dimension$n-d$, hence has size$2^{n-d}$.

Remark 130.

这一步提供了“可乘性”，是后面生成函数分解的核心。

\paragraph{Decomposition By$I(S)$ And$J(S)$ (Original).} For each$v\in I(S)$, the random variable$\langle v,w\rangle$ is independent of$\{\langle v',w\rangle:v'\in S\setminus\{v\}\}$. So if

then

Remark 131.

这个分解是第5节对应式 (4) 的起点。

Generating-Function Expansion (Original).

Write

with$a_1=0$. Then

for some$R(X)\in\mathbb Q[X]$.

Remark 132.

式 (7) 与 Section 3 的式 (4) 完全同型，因此 Claim 2 的证明框架可以直接平移。

Claim (Claim 8 (Original)).

Let$\Lambda^{(1)}$ be the OLDC spectrum

Then:

• $\lambda_\emptyset^{(1)}=1$

  ;

• $\lambda_{\min}^{(1)}=-1/7$

  ;

• $\Lambda_{\min}^{(1)}$

  consists of: all singletons, all 2-sets, all linearly independent 4-sets, and all sets of the form$\{x,y,z,x+y,x+z\}$;

• for all$S\notin\Lambda_{\min}^{(1)}$,

Remark 133.

其中 2-sets 对应 2-forest，独立 4-sets 对应 4-forest，$\{x,y,z,x+y,x+z\}$ 对应$K_4^-$。

Lemma 12 (Lemma 5.8 (Original)).

Let$S$ be a set of vectors.

1.

2.

3. If there exists$i\in[n]$ such that$|\{v\in S:v(i)=1\}|$ is odd, then$q_k(S)\le 1/2$ for any$k\ge 0$.

4. For odd$k$,$q_k(S)\le 1/2$.

5. Always$q_2(S)\le 3/4$.

Proof.

1. $q_0(S)$

   is the probability that$w\in S^\perp$. Since$\dim(S^\perp)=n-\mathrm{rank}(S)$, we get$q_0(S)=2^{-\mathrm{rank}(S)}$.

2. $|S\cap A_w|=1$

   iff$w\in (S\setminus\{v\})^\perp\setminus S^\perp$ for some$v\in I(S)$. The sets$\{(S\setminus\{v\})^\perp\setminus S^\perp:v\in I(S)\}$ are disjoint, and each has size$2^{n-\mathrm{rank}(S)}$, giving the formula.

3. Let

For any$w\in T_k$, we have$w+e_i\notin T_k$ (same involution idea as Lemma 3.1), hence$|T_k|\le 2^{n-1}$ and$q_k(S)\le 1/2$.

4. By item 3, assume each coordinate appears an even number of times in$S$. Then for any$w\in\mathbb Z_2^n$,

so$|\{s\in S:\langle s,w\rangle=1\}|$ is even. Therefore$q_k(S)=0$ for odd$k$.

5. Average size gives

strictly since$q_0(S)>0$. Hence

So$q_2(S)<3/4$ for$|S|\ge 6$. For$|S|\le 5$, by item 3 we may assume$\sum_{v\in S}v=0$. Let$T\subset S$ be the smallest dependent subset. Then$T$ must be

Since$S$ sums to$0$, also$S\setminus T$ sums to$0$; but$|S\setminus T|\le 2$, impossible unless$S=T$.

∎

Remark 134.

Lemma 5.8 是 Lemma 3.1 的 LD 版主工具箱，后续所有估计都依赖它。

Lemma 13 (Lemma 5.9 (Original)).

Let$S$ be a set of vectors.

1.

for all other$S$.

2. If$m(S)=0$ and$|S|$ is odd, then either$q_0(S)\le 1/16$, or$S$ is of one of the forms

3. Either$J(S)=\emptyset$ or$a_0\le 1/4$.

Proof.

1. If$S\neq \emptyset,\{x\}$, then$\mathrm{rank}(S)\ge 2$, so apply Lemma 5.8(1).

2. If$\mathrm{rank}(S)\ge 4$, item 1 gives$q_0(S)\le 1/16$. If$\mathrm{rank}(S)\le 3$, only the listed possibilities occur.

3. If$J(S)\neq\emptyset$, then$\mathrm{rank}(J(S))\ge 2$ (there is no dependency in$\{x\}$), so item 1 implies$a_0\le 1/4$.

∎

Remark 135.

其中前两类分别对应 triangle 与$K_4^-$，第三类是 LD 场景新增的“无图论对应”异常结构。

Proof of Claim 8 (Original).

The proof of Claim 2 relied on (4) and Lemmas 3.1--3.2. To prove Claim 8, replace them by (7) and Lemmas 5.8--5.9. The argument then goes through line-by-line after the substitutions

The unconditional estimates (Lemma 3.1 type) and conditional estimates (Lemma 3.2 type) both carry over.

As in Claim 2, explicit calculations are needed on exceptional small structures. Besides the direct analogues, there is one extra exceptional set:

for which

Hence

This completes the proof.

∎

Remark 136.

难点（对应此处）：Claim 8 的技术关键是“Claim 2 证明模板可迁移”，但必须额外处理 7 元异常结构这一处新分支。

Claim (Claim 9 (Original)).

Let$\Lambda^{(2)}$ be the OLDC spectrum

where$I$ denotes a linearly independent 4-set and$\square=\{a,b,c,a+b+c\}$. Then:

1. $\lambda_S^{(2)}=0$

   for all$|S|\le 3$;

2. $\lambda_S^{(2)}=1/16$

   for linearly independent$|S|=4$;

3. $\lambda_{\{x,y,z,x+y,x+z\}}^{(2)}=1/8$

   ;

4. $|\lambda_S^{(2)}|\le 1$

   for all$S$.

Proof.

1. Clear.

2. For any linearly independent 4-sets$I,I'$, we have

and$q_{\square}(I')=0$.

3. Let$S=\{x,y,z,x+y,x+z\}$. Then$q_I(S)=0$ for any linearly independent 4-set$I$. The only subset of$S$ isomorphic to$\square$ is

so$q_{\square}(S)=1/8$.

4. $|\lambda_S^{(2)}|$ is a difference of probabilities, so it is at most$1$.

∎

Remark 137.

Claim 9 的作用与图论中的 Claim 3 完全一致：抬升第一主谱上的坏 tight 点。

Closing The Uniform-Measure Case (Original).

Using the same argument as before, if$\mathcal F$ is odd-LD-agreeing then

For odd-LD-intersecting families, Lemma 2.4 yields equality only for families containing a fixed Schur triple. For odd-LD-agreeing families, the same monotonization argument as Lemma 2.7 yields equality only for Schur juntas. Stability follows by the same argument as before.

Remark 138.

至此，Theorem 5.1 的上界、等号结构与稳定性全部闭环。

Small$p$

Skew-Measure Extension (Original).

For$p<1/2$, Theorem 5.2 is proved by the Section 4 technique. The main-claim proof (Claim 5 type) now also uses Lemma 4.7, and its extension below.

Remark 139.

这部分对应 Section 4.4：思路同构，但要补一个 LD 版本的有限分类引理。

Lemma 14 (Lemma 5.10 (Original)).

Let$S$ be a set of vectors.

1. If$m(S)=1$ and$|S|>1$, then$|S|\ge 4$.

2. If$m(S)=0$ and$|S|\le 5$, then$S$ is of the form

Proof.

1. The smallest linear dependency is$\{x,y,x+y\}$.

2. Easy enumeration; note

is isomorphic to the last listed form.

∎

Remark 140.

这四类分别对应 triangle、$C_4$、$C_5$、$K_4^-$；唯一新增要核查的是 Lemma 5.9(2) 中那一类 7 元异常结构。

Final Transfer To Theorem 5.2 (Original).

All sets in Lemma 5.10(2) correspond to graph cases already controlled. For the extra exceptional case from Lemma 5.9(2), we also have

Hence Claim 5 remains valid in the current setting, which yields Theorem 5.2.

Remark 141.

Section 5 核心收获：图论主线可完整提升到$\mathbb Z_2^n$ 的奇线性依赖框架，并在均匀/偏置测度下都得到极值与稳定性。

Section 6 Notes

Discussion And Open Problems

Section Opening (Original).

There are many intriguing generalizations of the problems discussed in this paper. The authors mention several of them and state conjectures.

Remark 142.

这一节不是技术证明，而是把方法可能延伸到哪些方向做系统盘点。

Cross-Triangle-Intersecting Families (Original).

Many intersecting-family theorems admit cross-intersecting analogues. Two families of graphs,$\mathcal F$ and$\mathcal G$, are cross-triangle-intersecting if for any

the intersection$F\cap G$ contains a triangle.

Remark 143.

这是把“同一家族内两两相交”推广为“两个家族之间两两相交”。

Conjecture (Conjecture 1 (Original)).

Let$\mathcal F$ and$\mathcal G$ be cross-triangle-intersecting families of graphs on the same$n$ vertices. Then

Equality holds if and only if$\mathcal F=\mathcal G$ is a$\triangle$umvirate.

Remark 144.

这是最自然的 cross 版本极值猜想，结构上完全平行主定理。

Spectral Obstacle For The Cross Case (Original).

The standard Hoffman-style extension from intersecting to cross-intersecting requires one extra spectral condition:

must be the second largest in absolute value.

For the current tailored OCC spectrum this fails, because 3-forests have eigenvalue

The authors suggest that using more

q_R coordinates may recover the needed property, but the calculations are expected to be substantially harder.

Remark 145.

难点（对应此处）：cross 推广并非“直接套用”，卡在绝对值谱序这一条额外门槛。

\paragraph{The Regime$p>1/2$ (Original).} The preliminary OCC ansatz

worked at$p=1/2$ because the upper and lower bounds on$4c_3+c_4$ imposed by 4-forests and$K_4^-$ coincided. For$p>1/2$, these bounds contradict each other, so a more sophisticated construction is required. The paper sees no theoretical barrier to a spectral proof for all$p\le 3/4$, and conjectures Theorem 1.4 should hold on that whole range. It also asks why the theorem fails for$p>3/4$ (hint: Mantel's theorem).

Remark 146.

这一段解释了方法失效点：不是思想坏了，而是当前参数化谱不够强。

Other Intersecting Families (Original).

Odd-cycle-intersecting is a special case of$\mathcal G$-intersecting for a graph family$\mathcal G$.

Definition 8 (Definition 6.1 (\keypart{$m(\mathcal G)$}, Original)).

For a family$\mathcal G$ of graphs, define

For a fixed graph

G, abbreviate m({G}) to m(G). Similarly, write m_p(\mathcal G) under skew product measure with parameter p.

Remark 147.

这个定义把各种“某结构相交”问题统一成一个函数型极值对象。

Sample Facts And Questions (Original).

• Alon observed that for every star forest$G$,$m(G)=1/2$. He further conjectured existence of$\varepsilon>0$ such that for every non-star-forest$G$,$m(G)<1/2-\varepsilon$, and noted it suffices to prove this for$P_3$ (the 3-edge path). The simple guess$m(P_3)=1/8$ is false: Christofides constructed a$P_3$-intersecting family on six vertices with measure$17/128>1/8$.

• Let$\mathcal G_k$ be the family of non-$k$-colorable graphs. An obvious conjecture generalizing the main theorem is

with equality only for$K_{k+1}$-umvirates. The authors suggest small$k$ cases (especially$p=1/2$) may be approachable by their methods.

• A further conjectural direction is that$\triangle$umvirates may remain extremal even for cycle-intersecting families (not only odd-cycle-intersecting), at least when$p\le 1/2$. At$p=1/2$ this is already delicate: there is a neck-to-neck race with the family of all graphs having at least

edges. Moreover, the non-uniform-hypergraph analogue is false: in linear-dependency-intersecting families of subsets of$\mathbb Z_2^n\setminus\{0\}$ one can construct measure$1/2-o(1)$ examples, e.g. all sets of vectors with cardinality at least

Remark 148.

这里的关键信号是：越往一般化走，极值结构可能变、证明难度也显著上升。

A Non-Graph Structure Example (Original).

For$B\subset \mathbb Z_n$, call a family$\mathcal F$ of subsets of$\mathbb Z_n$ \keypart{$B$-translate-intersecting} if intersections of any two sets in$\mathcal F$ contain a translate of$B$. The conjectured bound is

It is known for interval$B$; Russell gave an algebraic proof. F"uredi--Griggs--Holzman--Kleitman proved the case$|B|=3$. Griggs--Walker proved that for each fixed$B$, the conjecture holds for infinitely many$n$. For most configurations$B$, the all-$n$ question remains open.

Remark 149.

这说明作者方法服务于更广的“结构性相交”范式，不局限在图模型。

Connection To Entropy? (Original).

The constructed OCC spectrum can be written as

but this is not a convex combination, since some$c_B$ are negative. If one restricts to non-negative coefficients, the method cannot improve the bound$1/4$. The authors wonder whether this relates to the entropy bound$1/4$, given superficial similarities to the entropy-based approach in [4].

Remark 150.

Section 6 核心收获：开放问题主要集中在 three fronts：cross 版本、$p>1/2$ 区间与更一般结构；而“负系数谱组合”可能是突破$1/4$ 屏障的关键。

PDF

Download the original write-up here.