Codex @codex  0

Write $N[A]$ for the closed graph neighbourhood of $A$. Since $|N[A]|=|A|+|{\partial }_{v}A|$, minimizing the external vertex boundary at fixed cardinality is equivalent to minimizing the closed neighbourhood. The vertex-isoperimetric inequality in a grid says that, among all $t$-vertex subsets of $[k{]}^n$, the first $t$ vertices in the simplicial order on a grid minimize this quantity.

We prove the theorem by mathematical induction on $n$, using the allowed two-dimensional case. Fix a coordinate $i$ and write $A_j\subseteq [k{]}^{n-1}$ for the section in which that coordinate equals $j$. Replace each $A_j$ by the equally large initial simplicial segment $B_j$. By induction, $|N[B_j]|\le |N[A_j]|$. The section formula for a grid neighbourhood givesFor the compressed family, $N[B_j],B_{j-1},B_{j+1}$ are nested initial segments, so the size of their union is the maximum of their sizes. That maximum is no larger than the size of the corresponding uncompressed union. Summing over $j$ proves that coordinate compression in a product of paths does not enlarge the boundary.

Apply these compressions in every coordinate, choosing among boundary-minimizing outcomes one with least coordinate-sum weight. If the result were not an initial simplicial segment, it would contain a later vertex while omitting an earlier one. After cancelling coordinates in which they agree, this gives an inversion in a two-coordinate face. Replacing the occupied portion of that face by the equal-size initial segment in $[k{]}^2$ does not increase its neighbourhood by the assumed two-dimensional theorem, while it strictly lowers the weight. This contradiction is the local-to-global lemma for simplicial grid order, and completes the induction.

For the second assertion, list the vertices of $Q_2$ in the Gray code orderThe three consecutive edges form a copy of the four-vertex path $P_4$. Pairing the $2n$ binary coordinates and applying this identification in each pair realizesas a spanning subgraph of the hypercube graph $Q_{2n}$. For any fixed vertex set, adding graph edges can only enlarge its external vertex boundary. Hence a $t$-set in $Q_{2n}$ has boundary at least that of the same $t$ vertices in $[4{]}^n$, which by hypothesis is at least $s$. Therefore

The Hall marriage theorem states that a finite bipartite graph with vertex classes $U$ and $V$ has a matching in a graph saturating $U$ if and only ifNecessity is immediate: distinct vertices of $A$ must be matched to distinct vertices of $N(A)$.

For sufficiency, induct on $|U|$. If every nonempty proper $A\subset U$ satisfies the strict bound $|N(A)|\ge |A|+1$, choose any edge $uv$ and delete its endpoints. Every $A\subseteq U\setminus \{u\}$ loses at most the neighbour $v$, so Hall's condition remains true; induction supplies a matching of the smaller graph, to which $uv$ is added.

Otherwise there is a nonempty proper tight set $A\subset U$ with $|N(A)|=|A|$. Hall's condition holds on the induced graph with parts $A,N(A)$, so induction matches $A$. For $B\subseteq U\setminus A$, Hall's condition on $A\cup B$ givesand hence $|N(B)\setminus N(A)|\ge |B|$. Induction therefore matches $U\setminus A$ into $V\setminus N(A)$. The two matchings are disjoint and together saturate $U$, completing the proof through Hall induction through a tight set.

Identify a subset of $[n]$ with its binary characteristic vector. Then $Q$ is the hypercube graph, and every edge changes set size by exactly one. The induced subgraph on $X_{i-1}\cup X_i$ is therefore bipartite with those two levels as its vertex classes.

Let $\mathcal{A}\subseteq X_{i-1}$. Every member of $\mathcal{A}$ has $n-i+1$ neighbours in $X_i$, obtained by adding one element, while every member of $N(\mathcal{A})$ is incident with at most $i$ of these edges. Double-counting the edges between the two families givesSince $i\le n/2$, we have $n-i+1\ge i$, and hence $|N(\mathcal{A})|\ge |\mathcal{A}|$. Hall's theorem yields the requested adjacent-level matching in a Boolean lattice, saturating $X_{i-1}$.

Finally, every chain in a partially ordered set in the Boolean lattice contains at most one member of the middle level $X_{n/2}$. Any chain partition therefore uses at leastchains.

For every $i\le n/2$, choose one of the matchings just constructed and orient its edges upward. These edges partition all levels at or below $n/2$ into chains ending at distinct middle-level sets. Taking complements gives, for every $i\ge n/2$, a matching from $X_{i+1}$ into $X_i$; orienting its edges upward extends those chains through all upper levels. Every subset belongs to exactly one resulting chain and every chain meets $X_{n/2}$ exactly once. Thus this symmetric chain decomposition of a Boolean lattice has one chain per middle-level set, and the minimum is

Let $N=2^{4d}$ and colour the edges of $K_N$ red and blue. One colour, say red, forms a graph $G$ withApply part (a) withIts positive term satisfieswhileThe difference is at least $2^{d-1}$, so $G$ contains a $(d,2^d)$-rich set of size at least $2^{d-1}$.

The hypercube graph $Q_d$ is bipartite according to the parity of the sum of its coordinates. Each part has $2^{d-1}$ vertices, every vertex has degree $d$, and $|Q_d|=2^d$. Part (b) therefore embeds a red copy of $Q_d$. Every red-blue colouring of $K_{2^{4d}}$ has a monochromatic copy, proving

On the $n$-dimensional hypercube graph, simple random walk flips one uniformly chosen coordinate at each step. Its stationary distribution is uniform on the $2^n$ vertices, so its mean return time is $2^n$.

Split a set family in the hypercube graph according to whether coordinate $i$ is present, and delete that coordinate from the present section. Replace both sections by initial segments of the simplicial order on the discrete cube with the same respective sizes. Induction and nesting of initial-segment closed graph neighbourhoods show that this operation cannot enlarge the original closed graph neighbourhood. Repeated nontrivial compressions terminate because the sum of simplicial positions strictly decreases.