Strong Noise Sensitivity and Random Graphs
summary
Defines strong noise sensitivity via conditioning on a particular one witness and connects it to witness geometry and influences; uses second moment and hypercontractivity ideas. Main concrete claims: cycles of length ~n^{1/3} in G(n,1/n) are one-strong-noise-sensitive with quantitative cutoff ε ≫ n^{-1/3} (stability for ε ≪ n^{-1/3}); minimum-degree ≥k at p=(log n+(k−1)log log n)/n is zero-strong-noise-sensitive with cutoff ε ≪ 1/log n; tribes give one-strong but not zero-strong; strictly balanced subgraph containment yields further one-strong results, with explicit counterexamples.
AI-written summary · about
chapters (18)
- 0:00Outline
- 2:08Noise Sensitivity
- 4:29What is Noise Sensitivity
- 6:45Examples
- 9:19Percolation
- 12:17PIP influences
- 16:56Random Graphs
- 21:07Strong Noise Sensitivity
- 28:27Example Tribes
- 31:07Quantitative Results
- 34:28Critical Window
- 38:40Proof
- 39:54Connection
- 43:23Graph Containment
- 45:32Graph Balance
- 47:03Noise Sensitivity vs Strong Noise Sensitivity
- 47:50Noise Stability
- 49:57Discussion