Results on biased Fourier analysis, influences and thresholds of graph and hypergraph properties, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Influence and Fourier weights — Lemma 2.1. sum over S containing i of hhat(S)^2 = sigma^2 I_i(h), and sum |S| hhat(S)^2 = sigma^2 I(h).
• Margulis-Russo formula — Lemma 2.2. For increasing h, the derivative of E_p h in p is the total influence I_p(h).
• Biased hypercontractivity — Theorem 3.1. With rho = sigma/4, ||T_rho g||_4 <= ||g||_2 on every finite biased product space.
• Low-degree projections — Corollary 3.2. ||P_(<=d) v||_2 <= rho^(-d) ||v||_(4/3).
• A low-degree estimate (OpenAI) — Lemma 4.1. If every influence of a Boolean h is at most I(h)/m, the Fourier weight of degrees 1 to sigma log m / 64 is at most m^(-1/4) I(h).
• Averaging over a restriction — Lemma 1.1. Averaging restricted Fourier weights and influences over the fixed coordinates gives the corresponding sums for the original function.
• The block estimate (OpenAI) — Proposition 2.1. For a symmetric f and a random m-block B, the weight of supports meeting F_B in 1 to k edges is at most (2m/n) m^(-1/4) I(f).
• Capturing low degrees (OpenAI) — Lemma 3.1. For log n >= 16 and m = floor(sqrt n), the Fourier weight of degrees 1 to k^2/2 is at most 4 m^(-1/4) I(f).
• Variance and influence for graph properties (OpenAI) — Theorem 4.1. Var_p(f) <= 2^17 I_p(f) / (log n)^2 for every vertex-symmetric Boolean f and every p.
• The Friedgut-Kalai conjecture (OpenAI) — Theorem 5.1. Every nontrivial increasing graph property has p_(1-eps) - p_eps <= 2^19 log(1/(2 eps)) / (log n)^2.
• The block estimate for hypergraphs — Lemma 1.1. For an m-block with m >= r+1, the restricted low-degree weight is at most m^(-1/4) (rm/n) I_p(f).
• Capturing a hypergraph support — Lemma 2.1. A support with at most (k/r)^(r/(r-1)) edges meets a random block in 1 to k edges with probability at least m/(2n).
• Variance and influence for hypergraph properties (OpenAI) — Theorem 3.1. Var_p(f) <= C_r I_p(f) / (log n)^(r/(r-1)) for every r-uniform hypergraph property and every p.
• Hypergraph thresholds (OpenAI) — Corollary 3.2. Increasing r-uniform hypergraph properties have threshold width at most 2 C_r log((1-eps)/eps) / (log n)^(r/(r-1)).

Reading order

Read the lessons in order. The first develops the analysis; the second proves the theorems for graphs; the third adapts the argument to hypergraphs.