728x90

반응형

`Jinyoung Park`

and `Huy Tuan Pham`

(Paper document in docuK SEE (Super Easy Edit) form.)
I think that it's time to use HTML MarkDown like docuK SEE (Super Easy Edit) rather than LaTeX when publishing a paper. It is better when sharing knowledges through smart devices like smartphone, PC, tablet PC using Internet | HTML. LaTeX is too old format to fit in printed papers. We usually do not print papers these days. We just see pdf files through PC, but not by smartphone. PDF files are not good format for smartphone.
Citing references and refering equations or sections or anything will be implemented soon. It is easy code, but I am tired now.

email :: jinypark@stanford.edu, huypham@stanford.edu
address :: Department of Mathematics, Stanford University450 Jane Stanford Way, Building 380, Stanford, CA 94305 ### abstract Proving the

`expectation-threshold`

conjecture of Kahn and Kalai, we show that for any increasing property $\mathcal{F}$ on a finite set $X$,
`expectation threshold`

of $\mathcal{F}$, and $\ell(\mathcal{F})$ is the maximum of $2$ and the maximum size of a minimal member of $\mathcal{F}$.
###[#sec-intro] Introduction
Given a finite set $X$, write $2^X$ for the power set of $X$. For $p \in [0,1]$, let $\mu_p$ be the product measure on $2^X$ given by $\mu_p(A)=p^{|A|}(1-p)^{|X \setminus A|}$. In this paper $\mathcal{F} \subseteq 2^X$ always denotes an increasing property, meaning that if $B \supseteq A \in \mathcal{F}$, then $ B \in \mathcal{F}$. We say that an increasing property $\mathcal{F}$ is nontrivial if $\mathcal{F} \ne \emptyset, 2^X$. It is a well-known fact that $\mu_p(\mathcal{F}) (:=\sum_{A \in \mathcal{F}} \mu_p(A))$ is continuous and strictly increasing in $p$ for any nontrivial increasing property $\mathcal{F}$. The threshold, $p_c(\mathcal{F})$, is then the unique $p$ for which $\mu_p(\mathcal{F})=1/2$. In this paper, we resolve a conjecture of Kahn and Kalai , reiterated by Talagrand , relating the threshold and the `expectation-threshold`

(definition is below).
Following , we say $\mathcal{F}$ is $p$-small if there is $\mathcal{G} \subseteq 2^X$ such that
There is a universal constant $K$ such that for every finite set $X$ and nontrivial increasing property $\mathcal{F} \subseteq 2^X$,
p_c(\mathcal{F}) \le K q(\mathcal{F}) \log \ell(\mathcal{F}).

Roughly speaking, Theorem says that for any increasing property, the threshold is never far from its trivial lower bound given by the expectation threshold.

Thresholds have been a central subject in the study of random discrete structures since its initiation by Erd\H{o}s and R$\acute{e}$nyi \cite{ER1, ER2}, the study of which has flourished in random graph theory, computer science \cite{K, Talagrand}, and statistical physics . The definition of the threshold above is finer than the original Erd\H{o}s-R$\acute{e}$nyi notion, according to which $p^*=p^*(n)$ is a threshold for $\mathcal{F}=\mathcal{F}_n$ if $\mu_p(\mathcal{F}) \rightarrow 0$ when $p \ll p^*$ and $\mu_p(\mathcal{F}) \rightarrow 1$ when $p \gg p^*$. That $p_c(\mathcal{F})$ is always an Erd\H{o}s-R$\acute{e}$nyi threshold follows from , in which it was observed that every increasing $\mathcal{F}$ admits a threshold in the Erd\H{o}s-R$\acute{e}$nyi sense. While much work has been done identifying thresholds for specific properties (see \cite{Bollobas, JLR}), another intensively studied direction in the study of thresholds is `sharpness threshold`

of thresholds: we refer interested readers to \cite{Friedgut1, Friedgut2}.
To emphasize the strength of Theorem `It would probably be more sensible to conjecture that it is not true.`

The expectation threshold is the most naive (and often the easiest) approach to estimating the threshold, and Theorem `universality`

result that above the correct threshold we actually have containment of all bounded degree spanning trees, which is not recoverable from Theorem `non pathological`

and atypical `pathological`

cases, to establish Theorem `non-pathological`

and atypical `pathological`

cases.
%The statement of the weaker version of Theorem
\label{CT}
There is a universal ${K}$ such that for every finite $X$ and nontrivial increasing
$\mathcal{F}\subseteq 2^X$,
p_c(\mathcal{F})< Kq_f(\mathcal{F})\log \ell(\mathcal{F}).

%The proof of Theorem `non-pathological`

and atypical `pathological`

cases.
Talagrand \cite[Conjecture 6.3]{Talagrand} also conjectured that the parameters $q$ and $q_f$ are in fact always of the same order:
Conjecture-LT
There is an absolute constant $L>0$ such that, for any nontrivial increasing $\mathcal{F}$, $q(\mathcal{F}) \ge q_f(\mathcal{F})/L$.

This of course implies equivalence of Theorems and , and up until now, proving Conjecture has been regarded as the most likely direction to prove Theorem . However, as Talagrand observes, even simple instances of Conjecture are not easy to establish. The two

Our proof of Theorem `test cases`

suggested by Talagrand, which are now proved respectively in and , already necessitate nontrivial arguments, and proving the full version of the conjecture is considered as a much harder task.
`spread`

plays a key role in the proofs. In particular, it provides the starting point of the proof of Theorem~
thm-KK
Let $\ell\ge 2$. There is a universal constant $L$ such that for any nonempty $\ell$-bounded hypergraph $\mathcal{H}$ on $X$ that is not $p$-small,

It is easy to see from the proof that one can obtain a quantitative bound for the $o_{\ell\to \infty}(1)$ term of the form $(\log \ell)^{-c}$ for $c>0$.

[Derivation of Theorem from Theorem .]
Let $\mathcal{F}$ be as in Theorem . We assume Theorem and derive that if $q>q(\mathcal{F})$ then, with $p=Kq\log\ell(\mathcal{F})$ ($K$ is a universal constant to be determined), we have $\mathbb{P}(X_p \in \mathcal{F}) > 1/2$. Here, we recall that for $0\le p\le 1$, we denote by $X_p$ the random variable with distribution $\mu_p$.
Let $\mathcal{H}$ be the set of minimal elements of $\mathcal{F}$ (so $\langle \mathcal{H} \rangle=\mathcal{F}$). Then $\mathcal{H}$ is $\ell(\mathcal{F})$-bounded and not $q$-small (since $q>q(\mathcal{F})$). Let $C$ be a (universal) constant for which, with $\ell=C\ell(\mathcal{F})$, the exceptional probability in Theorem is less than $1/4$.
Let $m=(Lq\log \ell)|X|$ and $p'=2Lq\log \ell$, and choose $K$ sufficiently large so that $p\ge p'$. Theorem~ vacuously holds if $p'>1$, so we can assume that $p'\le 1$, in which case
\mathbb{P}(X_{p'} \in \langle \mathcal{H}\rangle) \ge \mathbb{P}(X_m \in \langle \mathcal{H}\rangle) \;\mathbb{P}(|X_{p'}|\ge m) \ge (3/4)\; \mathbb{P}(|X_{p'}| \ge m) > 1/2,
where the last inequality follows from standard concentration bound, upon noting that $\mathcal{H}$ is not $q$-small implies $|X|q>1/2$ (since $\{\{x\}:x \in X\}$ covers $\mathcal{H}$) and hence $m > (L\log \ell)/2$ (so is somewhat large). This concludes the derivation.

Notations and Conventions. All logarithms are base $2$ unless specified otherwise. We have not made an attempt to optimize the absolute constants. For the sake of clarity of presentation, we omit floor and ceiling signs when they are not essential.

###[#subsec-proofKK] Proof of Theorem `cheap`

cover, where being cheap refers to the condition in `leftover`

$\mathcal{H}_{i-1}\setminus \mathcal{G}_i$ to finding a cover of $\mathcal{H}_i$. Property `large`

formally,
lem3-1
For $W$ uniformly chosen from ${X \choose w}$,
\mathbb{E}\left[ \sum_{U\in \mathcal{U}(W)}p^{|U|} \right] < L^{-0.8\ell},
where the expectation is over the randomness of $W$.

Observe that Lemma
[Proof of ]
Given $W$ and $m \ge 0.9\ell$, let
\mathcal{G}_m(W):=\{S \in \mathcal{H}: t(S,W) =m\}
and
\mathcal{U}_m(W):=\{T(S,W): S \in \mathcal{G}_m(W)\}.
Note that for any $U \in \mathcal{U}_m(W)$ we have $|U|=m$, so $ \sum_{W \in {X \choose w}} \sum_{U \in \mathcal{U}_m(W)} p^{|U|}$ is equal to $p^m$ multiplied by
\left|\left\{(W,T(S,W)): W \in {X \choose w}, S \in \mathcal{H}, \mbox{ and } t(S,W)=m\right\}\right|.
We bound the number of choices of $W$ and $T=T(S,W)$'s in the collection in using the following specification steps.
\begin{enumerate}[Step 1.]
\item Pick $Z:=W \cup T$. Since $|Z|=w+m$ (note $W$ and $T$ are always disjoint), the number of possibilities for $Z$ is at most (recalling $w=Lpn$)
{n \choose w+m} = {n \choose w} \cdot \mathbb{P}od_{j=0}^{m-1}\frac{n-w-j}{w+j+1} \le {n\choose w} (Lp)^{-m}.
\item
Note that $Z\; (= W \cup T)$ must contain an edge of $\mathcal{H}$ by the definition of minimum fragment. Make a choice of $\hat S \subseteq Z$ arbitrarily so that the choice of $\hat S$ only depends on $Z$. In particular, the choice of $\hat S$ is free given $Z$. Here a crucial observation is that, since $T(S,W)$ is a minimum fragment,
T \subseteq \hat S.
Indeed, since $\hat S$ is contained in $T\cup W\subseteq S\cup W$, the failure of implies that $\hat S \subseteq S \cup W$ has $|\hat S \setminus W| < |T|$, contradicting the minimality of $T$.
The property enables us to specify $T$ as a subset of $\hat S$, the number of possibilities of which is at most $2^\ell$.
\end{enumerate}
Note that $(W,T)$ is determined upon fixing a choice of $Z$ and $T$. In sum, we have
\sum_{W \in {X \choose w}} \sum_{U \in \mathcal{U}_m(W)} p^{|U|}\le p^m{n \choose w}(Lp)^{-m}2^\ell={n \choose w}L^{-m}2^\ell,
and the left hand side of is at most
\sum_{m \ge 0.9\ell} {n \choose w}L^{-m}2^\ell \le {n \choose w} L^{-0.8\ell}
for $L$ {sufficiently large}.

rmk-2-2
The proofs of the main lemma of and \cite{FKNP, KNP} also use similar-looking specification steps. By replacing their definition of $Z \; (:=W \cup S)$ with the one in the above proof $(Z:=W \cup T)$, one can remove the

`pathological`

case analysis in \cite{FKNP, KNP} and thus obtain a simplification of the argument there.
prop-obs-term
We have that either $W\in \langle \mathcal{H}\rangle$ or $\mathcal{U}:=\bigcup_{i \le \gamma} \mathcal{U}(W_i)$ covers $\mathcal{H}$.

Note that $\ell_\gamma<1$, hence either $\mathcal{H}_\gamma = \emptyset$ or $\mathcal{H}_\gamma = \{\emptyset\}$.
In the former case ($\mathcal{H}_\gamma =\emptyset$), we show that $\mathcal{U}$ covers $\mathcal{H}$. Indeed, for $S\in \mathcal{H}$, let $S=S_0, S_1, S_2, \ldots$ ($S_i \in \mathcal{H}_i$) be the evolution of $S$ in the iteration process, i.e., $S_i:=T(S_{i-1},W_i)$. In each iteration, either $S_i \in \mathcal{G}_i$ and is covered by $\mathcal{U}_i$, or otherwise, $S_{i+1}\in \mathcal{H}_{i+1}$. Since $\mathcal{H}_\gamma=\emptyset$, there exists $j < \gamma$ for which $S_j \in \mathcal{G}_j$. Hence, $S$ is covered by $\mathcal{U}$.
In the latter case ($\mathcal{H}_\gamma = \{\emptyset\}$), we show that $W\in \langle \mathcal{H}\rangle$. Indeed, by Property , $W_1\cup \ldots \cup W_\gamma\cup \emptyset \in \langle \mathcal{H}\rangle$, and hence $W \in \langle \mathcal{H}\rangle$.

Let $\mathcal{E}$ be the event that $\mathcal{U}$ covers $\mathcal{H}$. By Proposition `cost`

for {the} cover $\mathcal{U}$ is
- ArXiv - A Proof of the Kahn-Kalai Conjecture by Jinyoung Park, Huy Tuan Pham. 2022-03-31
- ArXiv - Thresholds versus fractional expectation-thresholds by Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park. 2019-10-29
- Wiki - Kahn–Kalai conjecture
- R. Alweiss, S. Lovett, K. Wu, and J. Zhang,

Improved bounds for the sunflower lemma,

Ann. of Math. (2) 194 (2021), no. 3, 795--815. - T. Bell and A. Frieze,

Rainbow powers of a Hamilton cycle in $G_{n,p}$,

Preprint, arXiv:2210.08534. - B. Bollob$\acute{a}$s,

Random Graphs,

second ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. - B. Bollob$\acute{a}$s and A. Thomason,

Threshold functions,

Combinatorica 7 (1987), 35--38. - B. DeMarco and J. Kahn,

Note on a problem of M. Talagrand,

Random Structures Algorithms 47 (2015), No. 4, 663-668. - P. Erd\H{o}s and A. R$\acute{e}$nyi,

On random graphs I,

Publ Math Debrecen 6 (1959), 290--297. - P. Erd\H{o}s and A. R$\acute{e}$nyi,

On the evolution of random graphs,

Publ Math Inst Hungar Acad Sci 5 (1960), 17--61. - K. Frankston, J. Kahn, B. Narayanan, and J. Park,

Thresholds versus fractional expectation-thresholds,

Ann. of Math. (2) 194 (2021), no. 2, 475--495. - K. Frankston, J. Kahn, and J. Park,

On a problem of M. Talagrand,

Random Structures Algorithms

https://doi.org/10.1002/rsa.21077 - E. Friedgut,

Sharp thresholds of graph properties, and the k-SAT problem,

J. Amer. Math. Soc. 12 (1999), 1017--1054, With an appendix by J. Bourgain. - E. Friedgut,

Hunting for sharp thresholds,

Random Structures Algorithms 26 (2005), 37--51. - G. R. Grimmett,

The random-cluster model,

Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Math. Sciences], vol. 333,

Springer-Verlag, Berlin, 2006. - J. H\r{a}stad,

Computational limitations of small-depth circuits,

MIT Press, Cambridge, MA, USA, 1987. - S. Janson, T. \L uczak, and A. Rucinski,

Random graphs,

Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. - A. Johansson, J. Kahn, and V. Vu,

Factors in random graphs,

Random Structures Algorithms 33 (2008), 1–28. - J. Kahn and G. Kalai,

Thresholds and expectation thresholds,

Combin. Probab. Comput. 16 (2007), 495--502. - G. Kalai,

Boolean functions: influence, threshold and noise,

European Congress of Mathematics, 85--110, Eur. Math. Soc., Z$\ddot{u}$rich, 2018. - J. Kahn, B. Narayanan, and J. Park,

The threshold for the square of a Hamilton cycle,

Proc. Amer. Math. Soc. 149 (2021), no. 8, 3201--3208. - R. Montgomery,

Spanning trees in random graphs,

Adv. Math. 356 (2019), 106793, 92. - J. Park and H. T. Pham,

On a conjecture of Talagrand on selector processes and a consequence on positive empirical processes,

Preprint, arXiv 2204.10309 [math.PR]. - A. A. Razborov,

Bounded arithmetic and lower bounds in boolean complexity,

Feasible Mathematics II, 344--386, Springer, 1995. - M. Talagrand,

Selector processes on classes of sets,

Probab. Theory Relat. Fields 135 (2006), 471--486. - M. Talagrand,

Are many small sets explicitly small?,

STOC'10 -- Proceedings of the 2010 ACM International Symposium on Theory of Computing, 13--35, ACM, New York, 2010. - M. Talagrand,

Upper and Lower Bounds for Stochastic Processes,

Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge (A Series of Modern Surveys in Mathematics book series) vol. 60, Springer, 2021. - M. Talagrand, personal communication, 2022.

728x90

반응형

#### '[Physics/Math] > Math' 카테고리의 다른 글

Runge-Kutta method, Matrix exponential (0) | 2023.07.11 |
---|---|

괄호, 중괄호, 대괄호 LaTeX equation 크기별 구분. (0) | 2023.06.16 |

Proof of Geometrization and Poincaré conjectures, by Grigori Perelman (0) | 2023.06.15 |

Method of Lagrange multipliers (0) | 2023.05.30 |

최적화, 라그랑지 승수법 (Optimization with the Method of Lagrange multipliers) (0) | 2023.05.30 |

Sturm-Liouville and Completeness Theory (0) | 2019.04.01 |

디락 델타 함수 (Dirac delta function) (0) | 2019.03.04 |