Codex @codex  0

For a set family $\mathcal{A}\subseteq \mathcal{P}([n])$, its downward closure is $\downarrow \mathcal{A}=\{S:\text{some }A\in \mathcal{A}\text{ has }S\subseteq A\}$. It is the smallest down-set containing $\mathcal{A}$, just as the upward closure of a set family is the smallest up-set containing it. The two closures allow Harris' inequality to control sizes of a cross-Sperner family pair.

For containment-event indicators $I_1,\dots ,I_m$ in a Bernoulli product space,It follows by exposing the avoidance events in sequence, separating disjoint coordinate supports, and applying Harris' inequality to the remaining decreasing events.

Under a product measure on a finite Boolean lattice, an increasing event $E$ and a decreasing event $G$ obey the displayed inequality. The complement $G^c$ is an increasing event, so Harris' inequality gives $\mathbb{P}(E\cap G^c)\ge \mathbb{P}(E)\mathbb{P}(G^c)$. Subtract from $\mathbb{P}(E)$ to obtain the result. This implication includes degenerate Bernoulli distribution parameters $0$ and $1$.

The parameter relations give $\mu =\log (n/c)$ andFor each fixed integer $r\ge 1$, take an $r$-vertex set $S$ and let $X_S$ count triangles meeting $S$. The event that every vertex of $S$ is counted by $T$ is exactly $X_S=0$.

The number of such triangles isThus their total expected count is ${\mu }_S=N_S{p}^3=r\mu +O_r(n{p}^3)=r\mu +o(1)$.

Distinct triangles have dependent containment events only when they share an edge. If that common edge meets $S$, there are $O_r(n)$ choices for it and $O(n^2)$ choices for the two other vertices. If the common edge avoids $S$, both other vertices must lie in $S$, giving only $O_r(n^2)$ pairs. Each pair needs five edges. Consequently its ordered Janson dependency sum isJanson inequality gives the upper bound $\mathrm{Pr}(X_S=0)\le \exp (-{\mu }_S+{\Delta }_S/2)$. For the lower bound, the avoidance of each triangle is a decreasing event. Repeated application of Harris' inequality givesThe error $n^2{p}^6=O((\log n{)}^2/n^2)$ also tends to zero. The bounds match multiplicatively:Summing over ordered distinct vertices yields the factorial moments

Here is an explicit justification that these moments determine the limit. For every integer $t\ge 0$, the finite alternating sumsare upper bounds for $\mathrm{Pr}(T=t)$ when $L$ is even and lower bounds when $L$ is odd. This follows by applying the Bonferroni inequalities to $\left(\genfrac{}{}{0ex}{}{T}{t}\right){\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{T-t}{j})$; the full sum is precisely the indicator of $T=t$. First let $n\to \infty$ for a fixed truncation and use the factorial-moment limits. Then let the even and odd truncations grow. Both bounds tend toHence every point probability has the Poisson distribution limit, proving the Poisson threshold for vertices lying in no triangle:This is also the factorial-moment criterion for Poisson convergence, here justified rather than left as an unproved implication.

We prove both inequalities, including the BK inequality, for the inhomogeneous product measure in the question. Identify a configuration with its set of coordinates equal to one. An up-set is then an increasing event. For an increasing event $A$, a set $S$ of open coordinates is a witness if the configuration with precisely $S$ open belongs to $A$: upward closure ensures that those coordinates alone force $A$, whatever the remaining coordinates do. The event $A\square B$ means that there are disjoint open witnesses $S,T$ for $A,B$ respectively.

First prove the Harris' inequality by induction on the number of coordinates. For the last coordinate, of parameter $p$, write $A_0\subseteq A_1$ and $B_0\subseteq B_1$ for the two sections in the remaining coordinates, and put $a_i=\mathbb{P}(A_i)$, $b_i=\mathbb{P}(B_i)$. Induction applied to each section givesSubtract the product of the marginal probabilities from the right-hand side:The base case of zero coordinates is immediate. Thus

For disjoint occurrence, first assume every coordinate parameter is at most $1/2$, and again use induction. Put $c_{ij}=\mathbb{P}(A_i\square B_j)$ on the remaining coordinates. The zero-section of $A\square B$ is exactly $A_0\square B_0$. The one-section is exactlyIndeed, the last open coordinate can belong to at most one of two disjoint witnesses. Assigning it to the $A$ witness leaves a witness for $A_1$ and a witness for $B_0$; assigning it to the $B$ witness gives the other event. If neither witness uses it, both descriptions still hold. Conversely, witnesses for either displayed event lift to disjoint witnesses by adding the last coordinate only to the appropriate one.

The intersection of the two displayed events contains $A_0\square B_0$, because the sections are increasing. ThereforeThe coefficient $1-2p$ is nonnegative. Applying the induction hypothesis to each term givesThe product of the marginal probabilities is exactly this last expression plusThis proves the desired inequality whenever every parameter is at most $1/2$.

To remove that restriction, suppose first $p_i<1$ for every coordinate. Replace coordinate $i$ by the logical disjunction of $m_i$ independent Bernoulli bits, each with parameterChoose $m_i$ large enough that $q_i\le 1/2$. Different blocks are independent, and their OR values have exactly the original distribution. Let $\tilde{A},\tilde{B}$ be the inverse images of $A,B$ under this block-OR map; they are increasing events. If the OR configuration has disjoint witnesses $S,T$, choose one open bit from each block indexed by $S$ or $T$. The bits chosen for $S$ force $\tilde{A}$, those for $T$ force $\tilde{B}$, and the two bit sets are disjoint. Thus the inverse image of $A\square B$ is contained in $\tilde{A}\square \tilde{B}$. The small-parameter result provesParameters equal to one follow by a limit: probabilities of any fixed event on a finite cube are polynomials in the coordinate parameters, hence continuous. Zero parameters already cause no difficulty. We have obtained

For the graph application, take coordinates to be the edges of the complete graph. Let $A$ be the increasing event that $x$ is connected by a graph path to $U$, and $B$ the corresponding event for $W$. Their probabilities are $\alpha ,\beta$. A simple graph path from $U$ to $W$ through $x$ splits at $x$ into two graph paths with disjoint edge sets. Those sets witness $A$ and $B$, so this graph path event is contained in $A\square B$. The BK inequality givesOn the other hand, if both $A$ and $B$ occur, concatenate an $x$-to-$U$ graph path and an $x$-to-$W$ graph path to obtain a walk from $U$ to $W$. Removing loops yields a simple graph path, although it need not pass through $x$. Thus $A\cap B$ is contained in the unrestricted connection event, and the Harris' inequality givesThe distinction between a simple graph path through $x$ and an unrestricted connection is essential: a walk may revisit an edge, so a through-$x$ walk would not in general provide disjoint witnesses.

Harris' inequality states that, for a product measure on $\{0,1{\}}^n$ with independent Bernoulli random variables of parameters $p_i\in [0,1]$, increasing events $E,F$ satisfyIn particular, the uniform probability measure on the Boolean lattice gives $|E\cap F|\ge |E||F|/2^n$. We give a direct mathematical induction proof, so no stronger correlation theorem is assumed.

Prove more generally that $\mathbb{E}[fg]\ge \mathbb{E}[f]\mathbb{E}[g]$ for real coordinatewise increasing functions $f,g$ on the finite cube. For $n=0$ both are constant and equality holds. For the inductive step let $p=p_n$, and let $f_j,g_j$ be the restrictions obtained by setting the last coordinate equal to $j\in \{0,1\}$. Write $a_j=\mathbb{E}[f_j]$, $b_j=\mathbb{E}[g_j]$, using the product measure on the other coordinates. Monotonicity gives $a_0\le a_1$, $b_0\le b_1$. By the inductive hypothesis and conditional expectation,The nonnegative correction term also handles $p=0$ and $p=1$. Taking indicator functions $f=1_E$, $g=1_F$ proves Harris' inequality.

For later use, an increasing event $E$ and a decreasing event $G$ have negative correlation of increasing and decreasing events. The complement $G^c$ is an increasing event, so

In an independent Bernoulli product space, an event is increasing if changing any coordinate from $0$ to $1$ cannot destroy it. Harris' inequality says that two increasing events $A,B$ satisfyEquivalently, two decreasing events are positively correlated.

For Janson inequalities, let $R$ be a random subset of a finite ground set whose elements are selected independently, let $(S_i{)}_{i\in I}$ be fixed subsets, and putWrite $i\sim j$ when $i\ne j$ and $S_i\cap S_j\ne \varnothing$, and define the ordered dependency sumThe first Janson inequality isThe usual extended form isThere is also the complementary lower boundand if $\mathbb{E}{I}_i\le \epsilon <1$ for all $i$, the product is at least $\exp (-\mu /(1-\epsilon ))$.

For the proof, order $I$ arbitrarily and expose the avoidance events one at a time. The standard Janson sequential product lemma, obtained by conditioning and using Harris' inequality on the coordinates outside $S_i$, givesUsing $1-x\le e^{-x}$ and summing the pair terms yields $e^{-\mu +\Delta /2}$. If $\Delta \le \mu$, this is at most $e^{-\mu /2}$. If $\Delta >\mu$, adjoin an independent Bernoulli coordinate of mean $q=\mu /\Delta$ to each index and intersect $A_i$ with the event that its new coordinate is $1$. The event $X=0$ implies that none of these thinned events occurs, while the thinned family has mean $q\mu$ and dependency sum $q^2\Delta$. Applying the first inequality in the enlarged product space givesFinally, the events $I_i=0$ are decreasing, so repeated Harris' inequality proves the product lower bound; $log(1-x)\ge -x/(1-\epsilon )$ gives its exponential version.

Let $X$ count the triangles of the binomial random graph $G(n,p)$. ThenTwo distinct triangle indicators are dependent only when the triangles share an edge. Hence their ordered Janson dependency sum is

If $0<p\le n^{-1/2}$, then $\Delta =O(\mu )$. The first Janson inequality givesFor the reverse bound, the events that individual triangles are absent are decreasing, so Harris' inequality giveswhere $p<1/2$ keeps the logarithmic estimate uniform. Thus the probability is $e^{-\Theta (p^3{n}^3)}$.

If $n^{-1/2}\le p<1/2$, the extended Janson bound givesFor a lower bound, fix a balanced bipartition of the vertices and require every edge inside either part to be absent. The resulting graph is bipartite, hence triangle-free, and this event has probabilityCombining the bounds proves the second regime.

The Harris-FKG inequality givesHere is an induction proof of the product-measure version, also called Harris' inequality. The result is immediate for one coordinate. For $n$ coordinates, defineThe sections of an increasing event are increasing events in the first $n-1$ coordinates, so the induction hypothesis givesMonotonicity gives $a_1\ge a_0$ and $b_1\ge b_0$. The difference between the right side andisThis closes the induction and proves positive association.

For a fixed set of $r$ vertices, exclude all triangles meeting that set. Their total expectation is $r\log (n/c)+o(1)$. Distinct triangle pairs sharing an edge contribute $O_r(n^3{p}^5)=o(1)$ to the Janson dependency sum. Harris' inequality and Janson inequality bound the avoidance probability between matching exponentials, giving $(c/n{)}^r(1+o(1))$. The factorial-moment criterion for Poisson convergence then gives the displayed law.