Triangle-Intersecting Families I

Part 1 of 3. Part 2 →

图见 PDF。

Section 1 Notes

Introduction

Background Statement (Original).

A basic theme in the field of extremal combinatorics is the study of the *largest size* of a structure given some combinatorial information concerning it.

Remark.

先给约束（例如“任意两集合交集非空”），再求能达到的最大规模。它不是在算一个固定对象，而是在所有满足条件的对象里做极值搜索。后文所有定理都围绕这个“约束$\to$ 极值$\to$ 结构”的主线展开。

Definition (Definition 1.1 (Original)).

A family of graphs$\mathcal{F}$ is triangle-intersecting if for every$G,H\in\mathcal{F}$, \keypart{$G\cap H$ contains a triangle}.

Remark.

这里的“intersecting”不是说两个图有公共边就够了，而是要求公共部分里必须完整地出现一个三角形。这个条件比“交集非空”强很多，因此真正可行的范围会明显变小，也更容易出现清晰的极值结构。

Question 1 (Simonovits--S'os, Original).

What is the maximum size of a triangle-intersecting family of subgraphs of the complete graph on$n$ vertices?

Remark.

这就是全文核心目标：在$K_n$ 的全部子图空间（规模是$2^{\binom n2}$）里，找出满足定义 1.1 的最大子族，并刻画何时达到上界。

Theorem (Theorem 1.2 (Original)).

Let$\mathcal{F}$ be a triangle-intersecting family of graphs on$n$ vertices. Then

Main Strengthenings (Original).

Our main result in this paper is actually a strengthening of the above in several aspects:

• *odd-cycle-intersecting replaces triangle-intersecting;*

• size is measured under *product measure*$\mu_p$ ($p\le 1/2$), not only uniform measure;

• for$p=1/2$, one may pass from intersecting to *agreeing*.

Remark 2.

第一步把禁忌结构从三角形放宽到奇环；第二步把计数问题推广成概率测度问题；第三步在均匀测度下把交集条件改成对称差条件。每一步都让问题更一般化。

Notation And Main Theorems

Definition 1 (Definition 1.3 (Original)).

A family$\mathcal{F}$ of subgraphs of$K_n$ is triangle-intersecting (respectively odd-cycle-intersecting) if for every$G,H\in\mathcal{F}$, \keypart{$G\cap H$} contains a triangle (respectively an odd cycle). We will say that$\mathcal{F}$ is triangle-agreeing (respectively odd-cycle-agreeing) if for every$G,H\in\mathcal{F}$, \keypart{$G\oplus H$} contains a triangle (respectively an odd cycle).

Remark 3.

这里最关键的是两个运算的角色不同：$G\cap H$ 是共同保留的边，$G\oplus H$ 是两图不一致的边。前者描述“共同拥有什么”，后者描述“差异里缺了什么”。论文在两个视角间来回切换，是因为谱方法在群结构（对称差）下更自然。

Immediate Consequence (Original).

Note that$G\cap H$ is contained in$\overline{G\oplus H}$, so a triangle-intersecting family is also triangle-agreeing.

Remark 4.

因此 intersecting 条件蕴含 agreeing 条件，说明前者更“硬”，后者更“松”。证明时若先拿到更松条件下的 sharp 上界，通常也能回推更强条件版本。

\paragraph{难点（对应此处）：$G\cap H$ 与$G\oplus H$ 为什么能在同一框架里处理？}

Remark 5.

关键在于后面把图空间看成$\mathbb{Z}_2$ 上的阿贝尔群，$\oplus$ 成为天然运算；很多算子和谱分解都围绕这个运算定义。于是 agreeing 版本更容易进入代数分析，再通过包含关系或 shift 结果转回 intersecting 版本。

Basic Notation (Original).

Let$n$ be fixed. The power set of$X$ is denoted by$P(X)$;$[n]=\{1,\dots,n\}$; and

It is convenient to identify the set of all subgraphs of$K_n$ with the Abelian group

whose group operation is symmetric difference (denoted by$\oplus$ or$\triangle$).

Remark 6.

这一段是后续所有计算的坐标系：把“图”改写成“边指示向量”，把“翻边”改写成“模 2 加法”。

Further Notation (Original).

Further notation in the original text:

• $\overline{G}$

  denotes the complement graph of$G$;

• $|G|$

  is the number of edges of$G$;

• $v(G)$

  is the number of non-isolated vertices of$G$;

• $G\cong H$

  denotes graph isomorphism;

• if$G$ is the disjoint union of$G_1,G_2$, write$G=G_1\sqcup G_2$;

• $\emptyset$

  denotes the empty graph on$n$ vertices;

• a$k$-forest is any forest with$k$ edges;

• $K_4^-$

  denotes the graph on four vertices with five edges;

• a biconnected component of$G$ means a maximal biconnected subgraph of$G$.

Measure and Inner Product (Original).

For any$p\in[0,1]$ and graph$G$ on$n$ vertices,

For a family$\mathcal{F}$,

For functions$f,g:\mathbb{Z}_2^{\binom{n}{2}}\to\mathbb{R}$,

Additional Conventions (Original).

Additional original conventions:

• identify$P(X)$ with$\{0,1\}^X=\mathbb{Z}_2^X$;

• an up-set$\mathcal{F}$ means:$S\in\mathcal{F},\,T\supset S \Rightarrow T\in\mathcal{F}$;

• $1_P$

  denotes the indicator of predicate$P$;

• for Abelian group$A$ and$Y\subset A$,$\mathrm{Cay}(A,Y)$ is the Cayley graph with edges$\{\{a,a+y\}: a\in A,y\in Y\}$.

Remark 7.

这些对象在方法段会立刻用到：尤其是 Cayley 图与特征值分析直接相关。

Terminology (Original).

A triangle junta is a family of all subgraphs of$K_n$ with a prescribed intersection with a given triangle. In the special case of the triangle junta being the family of all graphs containing a given triangle, we will call this family a \keypart{$\triangle$umvirate}.

Remark 8.

“junta”表示成员资格由很少的坐标决定（只根据图在某个固定的三角形航的边集情况来决定这个图是否属于某个图族）。在这里，这些坐标就是固定三角形的三条边；而$\triangle$umvirate（包含某个固定三角形的图） 是最关键特例：三条边都必须在图里。它会反复作为极值构造出现。

Theorem 1 (Theorem 1.4 (Original)).

[Extremal families] Let$p\le 1/2$, and let$\mathcal{F}$ be an odd-cycle-intersecting family of subgraphs of$K_n$. Then$\mu_p(\mathcal{F})\le p^3$, with equality if and only if$\mathcal{F}$ is a$\triangle$umvirate. Furthermore, in the case$p=1/2$, if$\mathcal{F}$ is odd-cycle-agreeing then$\mu(\mathcal{F})\le 1/8$, with equality if and only if$\mathcal{F}$ is a triangle junta.

[Stability] For each$p\le 1/2$ there exists a constant$c_p$ (bounded for$p\in[\delta,1/2]$, for any fixed$\delta>0$) such that for any$\varepsilon\ge 0$, if$\mathcal{F}$ is an odd-cycle-intersecting family with$\mu_p(\mathcal{F})\ge p^3-\varepsilon$ then there exists a$\triangle$umvirate$\mathcal{T}$ such that

For$p=1/2$, the corresponding statement holds for odd-cycle-agreeing families.

Remark 9.

这一条是全文主定理：上界、等号情形、稳定性一次给全。稳定性特别重要，因为它说明“几乎最优”的家族不会长得很奇怪，而是必须在测度意义上贴近某个$\triangle$umvirate。

Corollary 1 (Corollary 1.5 (Original)).

Let$\alpha<1/2$ and let$M=\alpha\binom{n}{2}$. Let$\mathcal{F}$ be an odd-cycle-intersecting family of graphs on$n$ vertices with$M$ edges each. Then

Equality holds if and only if$\mathcal{F}$ is the set of all graphs with$M$ edges containing a fixed triangle.

then there exists a triangle$T$ such that all but at most$c\varepsilon |\mathcal{F}|$ of graphs in$\mathcal{F}$ contain$T$, where$c=c(\alpha)$.

Remark 10.

这说明结论不仅在全体子图空间里成立，在“恰有$M$ 条边”的分层模型里也成立。也就是说，从概率模型投影到定边数模型，最优结构依旧保持不变。

**难点（对应此处）**：稳定性结论到底在控制什么？

Remark 11.

它不只是控制“数值接近上界”，而是控制“结构接近极值构造”。也就是从“几乎最优”推出“几乎是某个固定三角形族”，这是比单纯上界强得多的陈述。

Proof Idea for Corollary 1.5 (Original).

The idea of the proof is to study the family of all graphs containing a graph from$\mathcal{F}$, and to apply Theorem 1.4 to it, together with some Chernoff-type concentration of measure results.

Remark 12.

证明策略可以理解为三步：先做上闭包把定边数族嵌入到整体空间；再调用主定理得到测度上界；最后用集中不等式把概率结论拉回固定边数层，完成桥接。

拓展至超图。

Definition 2 (Definition 1.6 (Original)).

We say that a family$\mathcal{F}$ of hypergraphs on$[n]$ is odd-linear-dependency-intersecting if for any$G,H\in\mathcal{F}$ there exist$l\in\mathbb{N}$ and nonempty sets$A_1,\dots,A_{2l+1}\in G\cap H$ such that

Remark 13.

这一定义把图论语言抽象成代数语言：要求交集中存在“奇数个元素异或为零”的依赖关系。这样就能把三角形问题嵌入更一般的$\mathbb{Z}_2$ 线性依赖框架。

Definition 3 (Definition 1.7 (Original)).

A family$\mathcal{F}$ of subsets of$\mathbb{Z}_2^n$ is odd-linear-dependency-intersecting if for any two subsets$S,T\in\mathcal{F}$, there exist$l\in\mathbb{N}$ and non-zero vectors$v_1,\dots,v_{2l+1}\in S\cap T$ such that

Remark 14.

向量版本让“对称差”直接变成“模 2 加法”，因此后续 Fourier 角色函数和谱算子都能自然落在群结构上。这是从组合叙述过渡到分析工具的关键一步。

Odd-LD-Agreeing And Schur Terminology (Original).

Naturally, an odd-linear-dependency-agreeing family is defined by replacing$G\cap H$ with$G\triangle H$, and replacing$S\cap T$ with$S\triangle T$. Note that a Schur triple is a linearly dependent set of size$3$, so Schur-triple-intersecting implies odd-linear-dependency-intersecting. A family$\mathcal{F}$ of subsets of$\mathbb{Z}_2^n$ is a Schur-umvirate if there exists a non-zero Schur triple$\{x,y,x+y\}$ such that$\mathcal{F}$ consists of all subsets containing$\{x,y,x+y\}$. A family$\mathcal{F}$ is a Schur junta if there exists a Schur triple$\{x,y,x+y\}$ such that$\mathcal{F}$ consists of all subsets with prescribed intersection with$\{x,y,x+y\}$.

Remark 15.

这几句把“Schur-umvirate / Schur-junta”和前面的 triangle 版本完全对齐：一个是“必须全含”，一个是“交集模式固定”。后文所有等号结构结论都围绕这两个模板。

Theorem 2 (Theorem 1.8 (Original)).

Let$p\le 1/2$, and let$\mathcal{F}$ be an odd-linear-dependency-intersecting family of subsets of$\mathbb{Z}_2^n$. Then

Equality holds if and only if$\mathcal{F}$ is a Schur-umvirate. Moreover, for each$p\le 1/2$ there exists a constant$c_p$ (bounded for$p\in[\delta,1/2]$, for any fixed$\delta>0$) such that for any$\varepsilon>0$, if$\mu_p(\mathcal{F})\ge p^3-\varepsilon$ then there exists a Schur-umvirate$\mathcal{T}$ such that

For$p=1/2$, the corresponding statements hold for odd-linear-dependency-agreeing families.

Remark 16.

这说明主现象并不依赖“图”本身，而依赖“奇线性依赖”这一骨架。换句话说，triangle 是一个具体外观，odd dependency 才是底层机制。

Post-Theorem Remarks (Original).

This is indeed a generalization: any triangle-intersecting family of graphs can be lifted to a Schur-triple-intersecting family in the natural way. Also,$\{0,1\}^n$ can be viewed as a vector matroid over$\mathbb{Z}_2$, and any odd linear dependency contains a minimal odd dependency (an odd circuit), so Theorem 1.8 can also be interpreted as an odd-circuit-intersecting theorem in a$\mathbb{Z}_2$-matroid. The proof of Theorem 1.8 is deferred to Section 5.

Remark 17.

这段在方法上很关键：作者强调“图论问题只是外层壳”，真正稳定的结构来自$\mathbb{Z}_2$ 线性依赖与 matroid 奇回路。

Original Follow-up Remarks.

Original follow-up remarks:

• this is a genuine generalization: triangle-intersecting graph families can be lifted to Schur-triple-intersecting hypergraph families;

• in$\{0,1\}^n$ (viewed as a vector matroid over$\mathbb{Z}_2$), odd linear dependencies contain minimal odd dependencies (odd circuits);

• hence Theorem 1.8 may also be viewed as an odd-circuit-intersecting theorem in a$\mathbb{Z}_2$-matroid setting.

Remark 18.

作者在这里强调的是“抽象层级提升”：从图上的三角形，升维到 vector matroid （由矩阵列向量的线性无关关系定义出的拟阵）的奇回路约束，现象依旧稳定。

Methodological Observation (Original).

The ground set is a vector space over$\mathbb{Z}_2$; a triangle is not only a "triangle", but an \keypart{odd linear dependency over$\mathbb{Z}_2$}. This makes discrete Fourier analysis a natural choice.

Remark 19.

这一句是方法论核心。只要对象本质上受“奇偶/异或”控制，Fourier 分析就会比纯计数工具更直接，因为它把“依赖”转成频谱上的可估量量。

Historical Background

Prior Bound In [4] (Original).

In [4], if$\mathcal{F}$ is triangle-intersecting, then \keypart{$\mu(\mathcal{F})\le 1/4$}; this improves the trivial bound$1/2$.

Remark 20.

历史上先达到$1/4$，本文进一步压到 sharp 的$1/8$（均匀测度）。这体现了方法升级带来的精度提升。

Original Remarks Related To [4].

Original remarks related to [4]:

• because the argument there uses bipartiteness, it already extends from triangle-intersecting to odd-cycle-intersecting;

• for$p=1/2$, odd-cycle-agreeing can be shifted to odd-cycle-intersecting with the same measure;

• the basic observation can be written as$G\in\mathcal{F},\,B\text{ bipartite}\Rightarrow G\oplus B\notin\mathcal{F}$;

• for$p\le 1/2$, [4] yields a$p^2$-type bound, while this paper improves to$p^3$ and conjectures validity up to$p\le 3/4$.

Remark 21.

这一组历史注记解释了本文创新点：不是从零开始，而是在既有熵方法基础上换到更强的谱路径。

Connection To [8] (Original).

The paper [8] on$t$-intersecting families under product measure is a key thematic predecessor. For$S\subset [n]$,

For$p<\frac1{t+1}$, the unique largest-measure$t$-intersecting families are$t$-umvirates.

Remark 22.

作者在这里等于是在说：当前论文的谱构造与稳定性套路，是沿着 [8] 的技术轨道向图论问题迁移而来。

\paragraph{Classical$t$-Intersecting Context (Original).} For fixed$t\ge 2$, a family of subsets of$[n]$ is$t$-intersecting if all pairwise intersections have size at least$t$. The Erdős--Ko--Rado theorem gives the extremal model in large-$n$ regimes, while the Ahlswede--Khachatrian complete intersection theorem characterizes the largest$t$-intersecting families for all$n,k,t$. Under product measure, for$p<1/(t+1)$, [8] shows that the unique largest-measure$t$-intersecting families are$t$-umvirates, together with stability.

Remark 23.

这段是“祖先问题”定位：本文不是孤立技巧，而是把成熟的$t$-intersecting 谱框架迁移到了图空间与奇环约束。

Core Observation (Original).

Given triangle-intersecting$\mathcal{F}$ and bipartite$B$, for any$F_1,F_2\in\mathcal{F}$, the set$F_1\cap F_2$ must intersect$B$ non-trivially.

Remark 24.

这是许多后续算子的出发点：二分图不含奇环，因此可以作为“排除模板”去制造强约束。

Shift Equivalence (Original).

A triangle-agreeing family can be transformed, via monotone shifts, into a triangle-intersecting family of the same size.

Remark 25.

这条等价桥梁很有用：某些情形下 agreeing 更好算，算完可借 shift 机制转回 intersecting 结论。

Method Framework

Operator Motivation (Original).

If$\mathcal{F}$ is triangle-intersecting (or odd-cycle-agreeing) and$B$ is bipartite, then

So flipping edges of$B$ moves graphs out of the family.

Remark 26.

这一步把组合条件变成了运算闭包失效条件，进而可以转写为算子恒等式；这是从“看图”到“看线性变换”的关键转场。

**Operator Lift** (Original).

Let us lift this operation to an \keypart{operator$A_B$} on functions over subgraphs of$K_n$ (equivalently$\mathbb{Z}_2^{\binom{n}{2}}$):

If$B$ is random from distribution$\mathcal{B}$, define

Remark 27.

这里把“翻边”动作算子化后，可以系统研究特征值与特征函数。很多极值问题在这个步骤之后就转化成谱半径或最小特征值估计问题。

Key Identity (Original).

If$f=1_{\mathcal{F}}$, then$f(G)=1\Rightarrow A_{\mathcal{B}}f(G)=0$, hence

Linear combinations of such operators preserve this identity.

Remark 28.

这是全文最关键的代数约束之一。后续只要把$f$ 展开到 Fourier 基，结合算子特征值，就能把“零内积”翻译成关于频谱质量分布的不等式，从而推导上界与稳定性。

Linear Combination Step (Original).

For coefficients$c_B$ (not necessarily positive), define

Then the key identity is preserved:

The next step is to identify eigenvalues/eigenfunctions of$A$ and feed (1) into the Fourier side of$f$.

Remark 29.

这就是全文的“谱引擎”：把组合约束压缩成一个二次型等式，再用特征值把不同频段逐个控制。

\paragraph{难点（对应此处）：为什么$\langle f,Af\rangle=0$ 这么关键？}

Remark 30.

因为它是“可全局分解”的约束。一旦投影到特征基上，它会变成一串可比较的权重关系，从而直接产出 sharp 上界和稳定性误差界。

Next Technical Step (Original).

The next step is to identify eigenvalues/eigenfunctions of$A$, then use the identity above to control the Fourier transform of$f$, and finally deduce structure of$\mathcal{F}$.

Remark 31.

整条证明链可以记成：构造算子$\Rightarrow$ 计算谱$\Rightarrow$ 限制 Fourier 支持$\Rightarrow$ 读出极值构造与近极值构造。

Method Difficulty Remark (Original).

Even after finding the spectral route, the hard part is choosing the distributions$\mathcal B$ and coefficients$c_B$ so that the resulting eigenvalues are exactly the right ones.

Remark 32.

这是第一部分里最“工程化”的难点：不是知道要用谱就够了，而是要反向设计出一组分布与权重，让最小特征值正好卡在目标值并保留谱间隙。

Structure Of The Paper

Roadmap (Original).

The paper treats$p=1/2$ and$p<1/2$ separately; then extends to Schur-triple-intersecting families, and ends with open problems.

Remark 33.

阅读时可以把它看成三层推进：均匀模型（最直观）$\to$ 偏置模型（技术更细）$\to$ 抽象推广（结构本质）。

Section 1 Supplement.

Section 1 sets the target values$1/8$ (uniform measure) and$p^3$ (skew measure), and the rest of the paper constructs explicit spectra that force these bounds together with uniqueness and stability.

Remark 34.

补充一句主线：第一部分给的是“目标答案”，后续各节做的是“如何构造算子与谱，严格推出这个答案”。

Section 2 Notes

Fourier Analysis

\paragraph{Fourier Basics On$\mathbb Z_2^X$ (Original).} We briefly recall the essentials of Fourier analysis on the Abelian group$\mathbb Z_2^X$, where$X$ is finite. For any two functions$f,g:\mathbb Z_2^X\to\mathbb R$, define

For each$R\subseteq X$, define

Then$\chi_R(S\oplus T)=\chi_R(S)\chi_R(T)$, and$\{\chi_R:R\subseteq X\}$ is a complete orthonormal basis (the Fourier--Walsh basis). Hence every$f$ has expansion

with$\widehat f(R)=\langle f,\chi_R\rangle$, and Parseval:

If$f$ is Boolean, then

For a family$\mathcal F$ and its indicator, this is

A useful formula is the convolution identity

Remark 35.

这一小节是后续全部谱估计的坐标系：把家族问题转成 Fourier 系数的二次型问题，才能和 OCC 算子直接耦合。

\paragraph{难点（对应此处）：为什么 Boolean 情形下$\mu(\mathcal F)=\sum \widehat{\mathcal F}(R)^2$ 这么重要？}

Remark 36.

因为它把“家族大小”变成“频谱总能量”。后面定理就是用算子把这份能量强行压在低阶（或 tight 图对应频段）上，从而导出上界和结构唯一性。

**Key Mechanism (Original)**: energy, not counting.

In the Fourier view, measure is identified with spectral energy, and operator constraints become algebraic identities on Fourier coefficients.

Remark 37.

这一句是 Section 2 的底层逻辑：我们不再直接数家族元素，而是控制“能量如何分布在频谱上”。

Cayley Operators And Their Spectra

Spectral Route (Original).

Largest intersecting-family questions can be converted into independent-set questions in suitable Cayley graphs, then controlled via Hoffman-type eigenvalue bounds and weighted perturbations.

Remark 38.

这段是方法定位：先图论化（独立集），再谱化（特征值），最后通过加权构造把上界压到 sharp 值。Hoffman方法+加权扰动

Definition 4 (Definition 2.1 (Odd-Cycle-Cayley Operator, Original)).

A linear operator$A$ on real-valued functions on$\mathbb Z_2^{[n]^{(2)}}$ is called Odd-Cycle-Cayley (OCC) if:

1. for any odd-cycle-agreeing family$\mathcal F$ with indicator$f$,

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

Remark 39.

定义 2.1 把组合约束和可对角化要求合并成一个对象。没有第 1 条就无法编码 odd-cycle 条件，没有第 2 条就无法做频谱计算。

Spectrum Notation (Original).

For each$G\subseteq K_n$, let$\lambda_G$ be the eigenvalue of$\chi_G$. Write$\Lambda=(\lambda_G)_{G\subseteq K_n}$ for the OCC spectrum,$\lambda_{\min}$ for its minimum, and

The spectral gap is the maximal$\gamma$ such that

OCC operators (hence OCC spectra) form a linear space.

Remark 40.

线性空间性质是后面“先做一套主谱，再加一套修正谱”的根本原因。

Operator Construction (Original).

Let$B$ be a bipartite graph, and define

If$\mathcal B$ is a distribution over bipartite graphs, define

Remark 41.

这是 Section 1 里“翻边”动作的算子化版本。

**Markov Walk View** (Original).

The same operator can be viewed as a random walk on graph space with stationary uniform measure; if$\mathcal F$ is odd-cycle-intersecting, two consecutive states cannot both lie in$\mathcal F$.

Remark 42.

这个视角在后面$p<1/2$ 时尤其重要，因为偏置测度下会继续沿着“随机过程 + 谱”这条路线推进。

Claim (Claim 1 (Original)).

is an OCC operator, and its spectrum is

Proof.

If$\mathcal F$ is odd-cycle-agreeing and$f=1_{\mathcal F}$, then key annihilation step

Also, for Fourier characters: key eigenfunction step

so$\chi_R$ is an eigenfunction with eigenvalue

This can be rewritten in the claim form: key spectral formula

∎

Remark 43.

这条结论最有价值的地方是“把谱值表达成随机 cut 统计的期望”，从而把代数问题转成可算概率量。

\paragraph{Equivalent Views Of$A_{\mathcal B}$ (Original).}

• It is a convolution operator, so Fourier--Walsh characters are eigenfunctions.

• It is an average of tensor-product coordinate operators.

• It is a Cayley-graph adjacency operator (on an Abelian group).

• It is a Markov operator for a random walk on graph space.

Remark 44.

同一个算子的四种视角分别对应：分析、线性代数、图论、概率。后文在不同步骤会反复切换视角。

Theorem 3 (Theorem 2.2 (Original)).

Let$\Lambda=(\lambda_G)_{G\subseteq K_n}$ be an OCC spectrum with

Set

For any odd-cycle-agreeing family$\mathcal F$:

• Upper bound:$\mu(\mathcal F)\le \nu$.

• Uniqueness: if$\mu(\mathcal F)=\nu$, then$\widehat{\mathcal F}(G)\neq 0$ only for$G\in\Lambda_{\min}\cup\{\emptyset\}$.

• Stability: letting

we have

Proof.

Let$A$ be an OCC operator with spectrum$\Lambda$. Then

and thus key quadratic identity

Since$\widehat{\mathcal F}(\emptyset)=\sum_G\widehat{\mathcal F}(G)^2=\mu(\mathcal F)$ and

we get key mass decomposition

Therefore, core spectral inequality

Hence key bound transfer

Since$\gamma>0$, this implies$\mu(\mathcal F)\le \nu$, with equality iff$w=0$. Also,

so key stability estimate

∎

Remark 45.

Theorem 2.2 是 Section 2 的总模板：同一个二次型不等式同时产出上界、等号频谱支撑和稳定性误差界。

**Key Quadratic Constraint** (Original).

The whole theorem is driven by the identity

which turns combinatorial restrictions into a spectral quadratic inequality.

Remark 46.

这条等式是“组合条件转代数约束”的桥，后面的所有 sharp 常数都由它展开。

Corollary 2 (Corollary 2.3 (Original)).

Suppose there exists an OCC spectrum with

and all graphs in$\Lambda_{\min}$ have at most three edges. Then for any odd-cycle-agreeing family$\mathcal F\subseteq 2^{E(K_n)}$:

• \keypart{$\mu(\mathcal F)\le \frac18$};

• if$\mu(\mathcal F)=\frac18$, then$\mathcal F$ is a triangle junta;

• if$\mu(\mathcal F)\ge \frac18-\varepsilon$, then there exists a triangle junta$\mathcal T$ such that

for an absolute constant$c>0$.

Proof.

Upper bound key step: The upper bound follows directly from Theorem 2.2.

Uniqueness. First assume$\mathcal F$ is odd-cycle-intersecting; the reduction from agreeing to intersecting is Lemma 2.7 below. key low-degree reduction: since the Fourier transform is supported on graphs with at most three edges, Nisan--Szegedy implies$\mathcal F$ depends on at most$3\cdot 2^3=24$ coordinates. We may additionally assume$\mathcal F$ is an up-set (replace by up-filter if needed), and$\mu(\mathcal F)=1/8$. Then Lemma 2.4 applies: \keypart{$\mathcal F$ is a 3-umvirate}; in this setting, triangle-intersecting forces it to be a$\triangle$umvirate. Finally, Lemma 2.7 gives the odd-cycle-agreeing-to-junta reduction.

Stability. Use Theorem 2.5 (Kindler--Safra). Assume$\mu(\mathcal F)>1/8-\varepsilon$. By Theorem 2.2, key Fourier-tail estimate

Applying Kindler--Safra with$t=3$, provided$\varepsilon\le 7\gamma\varepsilon_0$, \keypart{$\mathcal F$ is quantitatively close} to some family depending on boundedly many coordinates:

to some family depending on at most$T_0$ coordinates. There are only finitely many such families that are not triangle juntas; by uniqueness, all of them have measure$<1/8$. Choose$\varepsilon_1>0$ so that each has measure$<1/8-\left(1+\frac{c_0}{7\gamma}\right)\varepsilon_1$. If$\varepsilon\le \varepsilon_1$,$\mathcal F$ cannot be that close to any of them while still having measure at least$1/8-\varepsilon$. Hence the approximating family must be a triangle junta. If$\varepsilon>\min(7\gamma\varepsilon_0,\varepsilon_1)=:\varepsilon_2$, take$c=1/\varepsilon_2$.

∎

Remark 47.

这个证明的结构是“谱稳定性$\to$ 有限坐标逼近$\to$ 排除有限坏例”：它不是直接分类全部族，而是借有限性做反证收口。

**Key Reduction In Uniqueness** (Original).

The uniqueness proof combines three ingredients in order: low-degree Fourier support$\Rightarrow$ bounded-coordinate dependence$\Rightarrow$ umvirate/junta rigidity.

Remark 48.

这三个步骤缺一不可：只有低阶支持不够，必须再借单调性与结构引理把“低维”压成“固定三角形”。

Lemma 1 (Lemma 2.4 ([8).

, Original)] Let$N\in\mathbb N$, let$p\le 1/2$, and let$f:\{0,1\}^N\to\{0,1\}$ be monotone with

Then$f$ is a$t$-umvirate (depends only on$t$ coordinates).

Remark 49.

这条是“低阶频谱集中 + 单调性$\Rightarrow$ 纯 umvirate 结构”的关键黑箱。

Theorem 4 (Theorem 2.5 (Kindler--Safra, Original)).

For every$t\in\mathbb N$, there exist$\varepsilon_0>0$,$c_0>0$,$T_0\in\mathbb N$ such that: if$f:\{0,1\}^N\to\{0,1\}$ satisfies

then there exists Boolean$g:\{0,1\}^N\to\{0,1\}$ depending on at most$T_0$ coordinates with

Remark 50.

这里最强的一点是：只要高阶尾质量足够小，逼近函数所需坐标数就被统一上界住，不随$\varepsilon$ 继续恶化。

**难点（对应此处）**：为什么 Corollary 2.3 的稳定性要引入“有限坏族排除”？

Remark 51.

因为 Kindler--Safra 先给的是“接近某个低维 Boolean 族”，但这个族未必就是 triangle junta。要得到最终结构，必须用唯一性结果把非 junta 的有限候选全部排掉。

The Intersecting/Agreeing Equivalence

Abstract Setup (Original).

Let$X$ be finite and$\mathcal Z\subseteq P(X)$. A family$\mathcal A\subseteq P(X)$ is$\mathcal Z$-intersecting if for all$A,B\in\mathcal A$ there exists$Z\in\mathcal Z$ with$Z\subseteq A\cap B$. It is$\mathcal Z$-agreeing if for all$A,B\in\mathcal A$ there exists$Z\in\mathcal Z$ with

Define

Remark 52.

这一步把图论中的 agreeing/intersecting 问题抽象成集合系统命题，方便直接调用压缩（monotonization）方法。

**Monotonization Principle** (Original).

Compression operators$C_i$ preserve family size and the agreeing property, while driving the family toward an up-set; once up-closed, agreeing upgrades to intersecting.

Remark 53.

这是 Lemma 2.6 的灵魂：操作本身不损规模，却提升结构可控性，最终把 agreeing 问题化成 intersecting 问题。

Lemma 2 (Lemma 2.6 (Original)).

For finite$X$ and$\mathcal Z\subseteq P(X)$,

Proof.

first inequality Clearly, every$\mathcal Z$-intersecting family is$\mathcal Z$-agreeing, so

It remains to show that any$\mathcal Z$-agreeing family can be transformed into a$\mathcal Z$-intersecting family of the same size.

For$i\in X$, define the$i$-monotonization$C_i$: for family$\mathcal A\subseteq P(X)$, replace each$A$ by$A\cup\{i\}$ whenever

Then$|C_i(\mathcal A)|=|\mathcal A|$, and if$\mathcal A$ is$\mathcal Z$-agreeing then so is$C_i(\mathcal A)$.

Starting from$\mathcal F_0=\mathcal F$, repeatedly apply such$C_i$ whenever possible: if there exist$F\in\mathcal F_k$ and$i\in X$ with$F\cup\{i\}\notin\mathcal F_k$, set

At each step, the sum of set sizes in the family increases by at least$1$, so the process terminates at some$\mathcal F_\ell$. Let$\mathcal F'=\mathcal F_\ell$. Then$\mathcal F'$ is$\mathcal Z$-agreeing,$|\mathcal F'|=|\mathcal F|$, and$\mathcal F'$ is an up-set.

Now for$F,G\in\mathcal F'$, we have$F\cup G\in\mathcal F'$. Since$\mathcal F'$ is$\mathcal Z$-agreeing, there exists$Z\in\mathcal Z$ such that

But$(F\cup G)\triangle G=F\setminus G$, so this implies$Z\subseteq F\cap G$. Hence \keypart{$\mathcal F'$ is$\mathcal Z$-intersecting}, therefore

So$m(\mathcal Z)=\bar m(\mathcal Z)$.

∎

Remark 54.

Lemma 2.6 的核心是“压缩后上闭 + agreeing 条件自动升级成 intersecting 条件”。

Lemma 3 (Lemma 2.7 (Original)).

Let$\mathcal F$ be odd-cycle-agreeing. Assume a sequence of monotonizations$C_e$ ($e\in [n]^{(2)}$) produces a family$\mathcal F_k$ that is a$\triangle$umvirate. Then$\mathcal F$ is a triangle junta.

Proof.

Suppose$\mathcal F_k$ is odd-cycle-agreeing and$\mathcal F_{k+1}=C_e(\mathcal F_k)\neq \mathcal F_k$ is a$T$-junta for some triangle$T\subseteq K_n$. Then there exists$G\notin \mathcal F_{k+1}$ with$G\cup\{e\}\in \mathcal F_{k+1}$; since$\mathcal F_{k+1}$ is a$T$-junta, necessarily$e\in T$. Let$S\subseteq T$ satisfy

Clearly$e\in S$.

Define

so$\mathcal F_k=\mathcal C\sqcup \mathcal D$. If$G\in\mathcal C$, then$G\cup\{e\}\notin\mathcal D$ (else both are in$\mathcal F_{k+1}$, contradicting fixed$G\cap T=S$ in the junta). Hence

Therefore every$G\in\mathcal D$ has$G\cap T=S$, and every$G\in\mathcal C$ has$G\cap T=S-e$.

Since$\mathcal F_{k+1}\neq \mathcal F_k$, we have$\mathcal C\neq\emptyset$. key claim: we claim$\mathcal D=\emptyset$. Assume not; let$|\mathcal D|=N\ge 1$, then

Because$T\oplus e$ intersects every triangle, if$G\in\mathcal F_k$ then