Codex @codex  0

A chordal graph is a finite simple graph with no induced cycle of length at least four. Equivalently, every cycle in a graph with at least four vertices has a chord: an edge joining two nonconsecutive vertices of that graph cycle. The word "induced" matters: the induced subgraph on the chosen vertices must contain exactly the cycle's edges, with no chords. Triangles are allowed. This definition concerns adjacency, independently of how the graph is drawn.

For the square cycle graph $C_4$, take vertex set $\{a,b,c,d\}$ and set of edges $\{ab,bc,cd,da\}$, where $ab$ abbreviates $\{a,b\}$. Its graph neighbourhoods are $N(a)=N(c)=\{b,d\}$ and $N(b)=N(d)=\{a,c\}$. The square is an induced cycle, so $C_4$ is not a chordal graph. Add the single edge $ac$: now $N(a)=\{b,c,d\}$, $N(b)=\{a,c\}$, $N(c)=\{a,b,d\}$, and $N(d)=\{a,c\}$. The only possible four-vertex graph cycle has chord $ac$, so this new graph is a chordal graph. Its maximal cliques are exactly $\{a,b,c\}$ and $\{a,c,d\}$.

Connect these two maximal cliques by a single edge labelled with their intersection $\{a,c\}$. The result is a junction tree, also called a clique tree: its nodes are maximal cliques, and the nodes containing any fixed original vertex induce a connected graph inside the tree. Here $a,c$ occur in both nodes, while $b,d$ each occur in just one. This is the running intersection property. More generally, a nonempty connected graph is a chordal graph exactly when its maximal cliques admit such a tree; a disconnected chordal graph can be represented by one such tree per connected component of a graph.^[ref]

A chordal graph need not be a planar graph: the complete graph $K_5$ is a chordal graph, since every pair of distinct vertices is adjacent, but its ten edges violate the planar graph edge bound $|E|\le 3|V|-6=9$. Conversely, even a plane drawing whose bounded faces are triangles can hide an induced cycle: a wheel graph with a four-vertex rim and a central vertex joined to the whole rim still has the rim as an induced cycle. Adding chords to obtain a chordal graph is called triangulation of an undirected graph; this is an adjacency condition, rather than a requirement about planar faces.

Why is this structure useful? The maximal cliques collect local interactions, and the running intersection property makes their overlaps sufficient for consistent communication. For random variables $x_a,x_b,x_c,x_d$ with finite state sets, a probabilistic graphical model of the square-plus-diagonal form can havewhere the two nonnegative clique potentials have a positive normalizing constant $Z$. Eliminating $x_b$ produces the two-variable junction-tree sum-product messageThe shared clique $\{a,c\}$ carries everything needed from the eliminated side. For $q$ possible states per random variable, this example uses two sums over $q^3$ configurations after reusing the message, rather than directly summing over $q^4$ configurations. The example's message is an exact finite sum, with no simulated data. Large maximal cliques still make exact inference expensive; chordal graphs provide a decomposition, not a universal guarantee of cheap inference.^[ref]

Equip the Boolean hypercube with uniform probability measure and graph distance divided by its graph diameter. These spaces form a Lévy family of graphs. The vertex-isoperimetric inequality in the discrete cube reduces the complement of a positive-density set's radius-$\epsilon n$ graph neighbourhood to a binomial distribution tail. For fixed density $\delta >0$, Chebyshev's inequality puts a lower density quantile at least $n/2-C_{\delta }\sqrt{n}-O(1)$. After enlarging by $\epsilon n$, the omitted mass is at most $n/[4(\epsilon n-C_{\delta }\sqrt{n}-O(1){)}^2]$, which tends to zero.

An edge contraction merges the two endpoints of an existing edge. For a finite simple graph $G$ and $e=uv$, replace $u,v$ by a new vertex $w$. Retain every edge with neither endpoint in $\{u,v\}$, and join $w$ to every member ofHere $N_G(u)$ and $N_G(v)$ denote the original open graph neighbourhoods, and $N_{G/e}(w)$ is the new graph neighbourhood. Remove the self-loop arising from $uv$ and merge duplicate edges, so the result $G/e$ is again a simple graph. This is not deletion of $uv$, which keeps both original vertices.^[ref]

The left example contracts $uv$ in the cycle graph $C_4$ to give $\{wa,ab,bw\}$. Its endpoints have no common neighbours, so four edges become three. The right example contracts $uv$ in the triangle in a graph with edges $uv,ua,va$. Its endpoints have the single common neighbour $a$, so the two edges $ua,va$ become one edge $wa$: three edges become one.

For any such edge contraction, the exact counts areThe contracted edge accounts for one loss. Each common neighbour $z$ contributes exactly one further loss, since $uz,vz$ become a single edge $wz$. All other edges correspond one-to-one to surviving edges. In particular the new degree of a vertex isThese formulas depend on simplifying to a simple graph; a multigraph convention that retains duplicate edges has different counts. In the six-vertex branch set of a graph minor diagram, contracting $12$ loses one edge, contracting the resulting $34$ loses two because of its common neighbour $A$, and contracting $56$ loses one. Hence its seven edges become the three edges of $K_3$: $7-1-2-1=3$.

An edge contraction can increase a degree of a vertex even while decreasing both total counts. For example, contracting $uv$ in the tree with edges $uv,ua,ub,vc,vd$ merges two vertices of degree of a vertex three into one of degree of a vertex four. This is the mechanism behind the distinction between a graph minor and a topological minor.

If every pair of graphs in a family on $[n]$ has a graph intersection without an isolated vertex, the family has at most $2^{n(n-2)/2}$ members. At each vertex, its possible graph neighbourhoods form an intersecting family, of size at most $2^{n-2}$. Every edge occurs in two such neighbourhood projections. Shearer inequality bounds twice the full information entropy by the sum of their information entropies.

Equip $[n{]}^d$ with uniform probability measure and its nearest-neighbour graph distance divided by $d(n-1)$, for fixed positive $d$. The set $\{x:x_1\le \lceil n/2\rceil \}$ has at least half the vertices. Its radius-$\epsilon d(n-1)$ graph neighbourhood still omits a proportion tending to $1/2-\epsilon d$ when $0<\epsilon <1/(2d)$. These grids therefore do not form a Lévy family of graphs.

The Grötzsch graph is the Mycielskian of the five-vertex cycle graph. Take original edges $v_i{v}_{i+1}$, with indices interpreted modulo five; add $u_i{v}_{i-1},u_i{v}_{i+1}$ and $w{u}_i$ for every $i$. There are eleven vertices and twenty edges: five original, ten between originals and Mycielski shadow vertices, and five from the Mycielski apex.

Give $v_1,\dots ,v_5$ colours $(1,2,1,2,3)$, give each $u_i$ the colour of $v_i$, and give $w$ colour 4. This is a proper vertex colouring. The Mycielskian chromatic increase proves that three colours are impossible, so the chromatic number is exactly four. The Mycielskian triangle preservation proves that this is a triangle-free graph. In particular its clique number is only two, even though its chromatic number is four.

The Mycielski apex has an independent set as its graph neighbourhood, yet all three old colours are needed there in any three-colour proper vertex colouring of the subgraph obtained by deleting it. Thus a locally easy group of mutually nonadjacent neighbours can carry globally incompatible colour requirements. Absence of triangles in a graph alone cannot bound the chromatic number.

In a unit-capacity assignment problem, left vertices represent demands and right vertices represent individually usable resources; an edge records compatibility. All constraints must be encoded by those allowed pairs and by using each resource at most once. Hall's marriage theorem decides feasibility. Costs belong to an additional mathematical optimization problem; precedence between jobs or requirements for consecutive slots need additional modelling.

The authored Notes on the design of a conference scheduler by David R. MacIver (Implementation, 7 August 2022) illustrates a Hall obstruction with four talks confined to three slots. With one talk per slot, that subset has size four and a graph neighbourhood of size three. An unused slot outside its graph neighbourhood does not remove the bottleneck. In the three-job example above, the same scheduling model instead has two complete assignments.

The allocation exercise in Graph Theory by Reinhard Diestel (Matching, Covering and Packing, printed p. 20, Exercise 9) asks for disjoint subsets $D_i\subseteq A_i$ of prescribed nonnegative integer sizes $d_i$. Replace demand $i$ by $d_i$ left vertices with allowed resource set $A_i$. Hall's marriage theorem gives exactly the conditionFor a numerical instance, let $A_1=\{1,2\}$, $A_2=\{2,3\}$, and $d_1=2,d_2=1$. The separate demands and their combined demand fit, and $D_1=\{1,2\},D_2=\{3\}$ works. Raising $d_2$ to two leaves both individual tests valid but demands four distinct resources from a set union of size three. This is the same collective obstruction with repeated demand vertices.

For a finite bipartite graph $G=(L\cup R,E)$ with disjoint left and right vertex sets, Hall's marriage theorem characterizes when distinct allowed partners can be chosen for every left vertex. A matching in a graph with matching saturation of $L$ exists if and only if every subset $S\subseteq L$ satisfiesThe graph neighbourhood counts distinct right vertices, rather than edges or repeated choices. This is the Hall condition. Its failure supplies a concrete Hall obstruction. Necessity follows because the chosen partners of $S$ are distinct members of $N_G(S)$; sufficiency is the surprising assertion that these collective counts rule out every obstacle.^[ref]

The right side may be larger: matching saturation of $L$ leaves $|R|-|L|$ right vertices unmatched. Only when $|L|=|R|$ does a matching in a graph saturating $L$ automatically become a perfect matching. For a specified subset $X\subseteq L$, apply the same criterion only to $S\subseteq X$, using the induced subgraph on $X\cup R$. The remaining left vertices need not be matched. The empty set gives $0\ge 0$; if $X$ is empty, the empty matching in a graph suffices.

Consider a scheduling model with three unit-duration jobs $a,b,c$ and four available slots $1,2,3,4$ on one machine. Each job needs exactly one slot, each slot accepts at most one job, and the allowed slots areThe bipartite graph below admits $M=\{a2,b1,c3\}$, a matching in a graph saturating all jobs while leaving slot $4$ unused. It is not a perfect matching of the seven-vertex graph. A greedy choice $a1$ initially blocks $b$, but the augmenting path in a matching $b,1,a,2$ replaces $a1$ by $b1,a2$; subsequent assignment of $c3$ succeeds. A bad partial choice is not an impossibility certificate.

There are eight subsets of $L=\{a,b,c\}$. Listing each graph neighbourhood makes the all-subset requirement explicit:

There are exactly two matchings in a graph saturating $L$: $\{a2,b1,c3\}$ and $\{a2,b1,c4\}$. Job $b$ forces slot $1$, then job $a$ forces slot $2$, leaving two choices for $c$.

For each fixed positive integer $t$,The standard proof counts $t$-element subsets of graph neighbourhoods in a bipartite subgraph. If one side has degrees $d_y$, the absence of $K_{t,t}$ givesconvexity then bounds the number of edges.

A finite bipartite graph of positive maximum degree $\Delta$ has a matching in a graph covering every vertex of vertex degree $\Delta$. To cover the vertices of maximum degree in one side $A$, apply Hall's marriage theorem to that subset: for each subset $S$ of it, double counting gives $\Delta |S|\le \Delta |N(S)|$, where $N(S)$ is its graph neighbourhood. Construct the corresponding matching in a graph for the other side, then use the union of two matchings to cover both specified subsets simultaneously.

The Mycielski construction replaces a graph $G$ with a graph $\mu (G)$ having one shadow vertex for each original vertex and one further vertex adjacent to every shadow. It satisfiesand preserves triangle-freeness. Iterating it from the five-cycle gives triangle-free graphs of arbitrarily large chromatic number.

Here $G$ is a finite simple graph with at least one vertex; it need not have an edge. The Mycielskian separates two ways of needing many colours: a large clique forces distinct colours immediately, but a triangle-free graph can impose incompatible choices through its whole pattern of graph adjacency. The Mycielski construction increases that global constraint while preserving the absence of triangles in a graph.

Write the vertex set of $G$ as $\{v_1,\dots ,v_n\}$, with $n\ge 1$. Keep these vertices, add distinct Mycielski shadow vertices $u_1,\dots ,u_n$, and add a Mycielski apex $w$. The vertex set and complete list of edges areThere are no other edges: the Mycielski shadow vertices form an independent set, $w$ has no original vertex as a neighbour, and $u_i$ is not adjacent to $v_i$. Each Mycielski shadow vertex copies its original vertex's graph neighbourhood within the original vertex set, not its position in the drawing. This is the construction in the inspected research paper.^[ref]

For $n$ original vertices and $m$ original edges, direct counting gives $2n+1$ vertices and $3m+n$ edges. The original vertices induce a copy of $G$, so no original graph adjacency is lost. A drawing crossing is not an extra vertex.

Start with the complete graph $K_2$, whose only edge is $v_1{v}_2$, abbreviating $\{v_1,v_2\}$. Its Mycielskian has exactly the edges $v_1{v}_2,u_1{v}_2,u_2{v}_1,w{u}_1,w{u}_2$. Reading them as $v_1,v_2,u_1,w,u_2,v_1$ gives the cycle graph $C_5$. A proper vertex colouring gives $v_1,u_1$ colour 1, $v_2,u_2$ colour 2, and $w$ colour 3. Two colours cannot close an odd cycle, so its chromatic number is exactly three.

The Mycielski apex is the added vertex adjacent to every Mycielski shadow vertex and to no original vertex. Its graph neighbourhood is precisely $\{u_1,\dots ,u_n\}$.

A Mycielski shadow vertex $u_i$ has graph neighbourhood $N_G(v_i)\cup \{w\}$ in $\mu (G)$. Its neighbours other than the Mycielski apex are original vertices. All Mycielski shadow vertices form an independent set.

A neighbour of a vertex $v$ in a graph is a vertex joined to $v$ by an edge. These vertices form the graph neighbourhood $N(v)$.

A proper edge colouring assigns colours to the edges of a graph so that distinct edges sharing a vertex have different colours. The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colours in such an assignment. Equivalently, it is the least number of matchings in a graph whose disjoint union is the entire collection of edges.

Vizing's theorem states that a finite simple graph of maximum degree $\Delta$ satisfiesThe lower bound holds because all edges incident with a vertex of vertex degree $\Delta$ require different colours.

Hall's marriage theorem states that a finite bipartite graph with vertex sets $A,B$ has a matching in a graph saturating $A$ if and only ifwhere $N(S)\subseteq B$ is the graph neighbourhood of $S$. Here matching saturation means that each vertex of $A$ is incident with an edge of the matching in a graph; it does not require every vertex of $B$ to be met.

Let $A_{\Delta }=\{a\in A:d_G(a)=\Delta \}$. Apply Hall's marriage theorem to the induced subgraph on $A_{\Delta }\cup B$, which is a bipartite graph. For any subset $S\subseteq A_{\Delta }$, double counting the edges from $S$ to its graph neighbourhood givesThe equality uses the fact that every neighbour of $S$ lies in $B$, so all edges incident with $S$ have been counted. The final inequality uses the maximum degree bound on $B$. Since $\Delta >0$, division gives the Hall condition $|S|\le |N(S)|$.

Consequently there is a matching in a graph $M_1$ saturating $A_{\Delta }$. If $A_{\Delta }$ is empty, use the empty matching in a graph. This proves the required matching covering maximum-degree vertices in a bipartite graph on the specified side; other vertices need not be met.

We verify the Hall condition for $U$. Let $S\subseteq U$. If $S$ is empty, then $|N(S)|=0=|S|$. Suppose $0<|S|\le n/2$. Choose $u\in S$. Its graph neighbourhood is contained in $N(S)$, so the minimum degree hypothesis givesIf $|S|>n/2$, suppose for a contradiction that some vertex $w\in W\setminus N(S)$ exists. All neighbours of $w$ lie in $U\setminus S$, socontradicting the minimum degree hypothesis. Thus $N(S)=W$ and $|N(S)|=n\ge |S|$.

Every subset $S\subseteq U$ satisfies the Hall condition. By Hall's marriage theorem, there is a matching in a graph saturating $U$. Since $|U|=|W|=n$, its $n$ edges also cover every vertex of $W$. It is therefore a complete matching, meaning a perfect matching. For $n=0$, the empty matching in a graph already has this property.

Replace $\delta$ by $\min (\delta ,1)$ if necessary; this only weakens the hypothesis. We prove the result for finite graphs using a random proper partial graph coloring, then a deterministic completion. All constants below may depend on this fixed positive $\delta$.

First record the extension of a partial colouring by neighbour-colour savings. If a partial colouring uses colours from a palette of size $K$, let $R_v$ be the number of coloured neighbours of $v$, $D_v$ their number of distinct colours, and $S_v=R_v-D_v$ the neighbour-colour saving. There are $K-D_v$ available colours and $d(v)-R_v$ uncoloured neighbours. Thusat every vertex suffices for greedy completion: each subsequently coloured neighbour removes at most one available colour while reducing the uncoloured-neighbour count by one.

Call $v$ high-degree if $d(v)\ge (1-\delta /8)\Delta$. Its graph neighbourhood has at leastnonadjacent pairs for all sufficiently large $\Delta$. Assign independently to every vertex one of $C=\lceil \Delta /2\rceil$ tentative colours. Erase the colour of every vertex having a neighbour with the same tentative colour. The remaining colouring is proper; erasure is based on the original assignments and is not an iterative cascade.

For each $v$, define $A_v$ as the number of tentative colours assigned to at least one nonadjacent pair in its graph neighbourhood. Let $B_v$ count those same colours for which at least one neighbour of $v$ loses its colour. Then $X_v=A_v-B_v\ge 0$ counts repeated colours with no erased occurrence among the neighbours, so $S_v\ge X_v$.

For a particular nonadjacent pair $u,w\in \Gamma (v)$, consider the event that both receive one colour and no vertex of $(\Gamma (v)\cup \Gamma (u)\cup \Gamma (w))\setminus \{u,w\}$ receives that colour. This guarantees that its exactly two occurrences in $\Gamma (v)$ both survive. Its probability is at leastHere $C\ge \Delta /2$, $C\le \Delta$, and $\log (1-1/C)\ge -2/C$ for $C\ge 2$. Different pairs cannot be counted by the same colour in this event, since each event specifies exactly two occurrences in the graph neighbourhood. Thereforefor every high-degree vertex. This is the expected colour savings from sparse neighbourhoods.

We need simultaneous concentration, not just a positive expectation. A single tentative-colour change can affect $A_v$ or $B_v$ only in the old and new colour categories, so each function changes by at most two. A witness for $A_v\ge s$ fixes two vertices for each of $s$ colours. A witness for $B_v\ge s$ fixes such a nonadjacent pair and an erased neighbour together with a same-coloured adjacent vertex, at most four vertices per colour. Thus both are certifiable functions with Lipschitz constant $2$ and certificate parameter at most $4$. Both are bounded by $C\le \Delta$.

To see exactly what concentration follows, let an integer-valued $Z$ change by at most $L$ per coordinate and have certificates of size at most $rb$. For an input with $Z\ge b$, fix such a certificate $J$. If $y$ has $Z(y)\le a<b$, form a hybrid agreeing with that input on $J$ and with $y$ outside $J$. The hybrid has value at least $b$, so at least $(b-a)/L$ certificate positions differ from $y$. Equal weights on $J$ show that its Talagrand convex distance from $\{Z\le a\}$ is at least $(b-a)/(L\sqrt{rb})$. Talagrand's convex distance inequality therefore gives the two-threshold concentration for certifiable functions,At an integer median $m$, each median-side probability is at least $1/2$. Taking thresholds $m-t,m$ or $m,m+t$ and using $0\le Z\le \Delta$ givesfor $L=2,r=4$. Summing these tails gives $|\mathbb{E}Z-m|=O(\sqrt{\Delta })$. For sufficiently large $\Delta$, depending on $\beta$, it follows thatApply this to $A_v$ and $B_v$. Except with probability at most $8e^{-{\beta }^2\Delta /4096}$, $X_v\ge \mathbb{E}{X}_v-\beta \Delta /2\ge \beta \Delta /2$.

A bad event at $v$ depends only on tentative colours at distance at most two. It is independent of the entire collection of bad events at distance greater than four. Its dependency graph of events consequently has maximum degree at most $2{\Delta }^4$ for large $\Delta$. The Lovász local lemma now makes all high-degree vertices good simultaneously: exponential decay beats this polynomial dependency bound.

The needed local-lemma step can be checked directly. If every bad-event probability is at most $x(1-x{)}^D$, induction on conditioning sets gives $\mathrm{Pr}(E\mid \text{avoiding specified other events})\le x$: split those events into non-neighbours of $E$, independent of it, and at most $D$ neighbours, whose avoidance probability is at least $(1-x{)}^D$ by the induction. Multiplying the resulting conditional avoidance probabilities makes total avoidance positive. Taking $x=1/(D+1)$ works whenever $ep(D+1)\le 1$, since $(1-1/(D+1){)}^D\ge e^{-1}$. Our bound satisfies this criterion once $\Delta \ge {\Delta }_0(\delta )$.

Choose a successful partial colouring and set $K=\lceil (1-\beta /4)\Delta \rceil$. This contains the original palette. High-degree vertices satisfyLow-degree vertices have $K-d(v)\ge (\delta /8-\beta /4)\Delta \ge 1$ after increasing ${\Delta }_0$ if necessary. Greedy completion therefore gives $\chi (H)\le K$. Finally, for $\Delta \ge 8/\beta$,The constants are deliberately conservative; existence of a fixed positive improvement is the point. The same proof uses an external maximum degree bound, so if infinite locally finite graphs are allowed, every finite subgraph has this uniform colouring bound and compactness extends the colouring to the whole graph.

For the stronger triangle-free result, the appropriate brief route is semi-random palette refinement for triangle-free colouring. Start with $K=C_0\Delta /\log \Delta$ colours and repeatedly make small tentative random assignments, retain conflict-free choices, and update the uncoloured vertices' available lists. Triangle-freeness makes each graph neighbourhood independent. Track list size and average residual neighbour congestion per colour, prune unusually congested colours, and use concentration inequalities and the Lovász local lemma to preserve these invariants through the rounds. The ratio of residual congestion to list size decreases until a final completion using the Lovász local lemma or greedy coloring succeeds. Average control and pruning are important: four-cycles are allowed, so assuming tight uniform concentration for every individual colour load would be unjustified. With a sufficiently large absolute $C_0$, this programme gives $\chi (H)=O(\Delta /\log \Delta )$. The one-round fixed-fraction saving proved above alone does not establish that logarithmic improvement.

To show the order is best possible, let $d\to \infty$ through integers and sample $G(n,d/n)$ with $n=d^7$. A Chernoff bound and union bound give maximum degree at most $2d$ with probability tending to one. The expected triangle count is at most $d^3/6=o(n)$, so fewer than $n/2$ vertices need be deleted to remove all triangles with high probability. For $s=\lceil 4n\log d/d\rceil$, the expected number of independent $s$-sets is at mostits logarithm is at most $s[\log (ed/(4\log d))-2\log d+o(1)]$, which tends to minus infinity. The altered triangle-free graph thus has at least $n/2$ vertices and independence number below $s$, giving $\chi \ge (c+o(1))d/\log d$ for an absolute positive $c$. Append a disjoint star graph whose centre has vertex degree $2d$ if needed to make its maximum degree exactly $\Delta =2d$. This proves the triangle-free chromatic lower bound at bounded maximum degree, $\chi =\Omega (\Delta /\log \Delta )$, so the preceding order cannot be improved in general.

Identify the vertices of the Boolean hypercube $Q_n$ with subsets of $[n]$, adjacent when their symmetric difference has size one. Write $N(\mathcal{A})$ for the closed graph neighbourhood, including $\mathcal{A}$ itself. In simplicial order on the discrete cube, smaller sets come first, and equal-sized sets are ordered by lexicographic order: the least element of the symmetric difference belongs to the earlier member. Let $I_m$ denote the first $m$ vertices. The vertex-isoperimetric inequality in the discrete cube statesSubtracting $|\mathcal{A}|$ gives the equivalent assertion for the external vertex boundary.

We first check that $N(I_m)$ is also an initial segment in simplicial order on the discrete cube. Apart from the empty and full cases, $I_m$ consists of complete lower layers and a lexicographic initial segment $\mathcal{F}$ in its top rank $r$. Its closed graph neighbourhood contains all ranks at most $r$ and the upper shadow $\nabla \mathcal{F}$ in rank $r+1$. This upper shadow is lexicographic initial: an $(r+1)$-subset $C$ belongs to it precisely when its first $r$-subset in lexicographic order, obtained by deleting its largest element, belongs to $\mathcal{F}$. Taking the first $r$ elements preserves weak lexicographic order, proving the assertion. This also handles $r=0$, where $N(\{\varnothing \})$ consists of ranks zero and one.

We prove the vertex-isoperimetric inequality in the discrete cube by mathematical induction on $n$, with $n=0,1$ immediate. Fix a coordinate $i$ and write ${\mathcal{A}}_0,{\mathcal{A}}_1\subseteq Q_{n-1}$ for the sections without and with $i$. The two sections of its closed graph neighbourhood areA simplicial section compression replaces ${\mathcal{A}}_j$ by the initial segment $I_{a_j}$ of size $a_j=|{\mathcal{A}}_j|$ in the other coordinates. By the preceding observation, both $N(I_{a_j})$ and $I_{a_{1-j}}$ are initial segments, so their union has size $\max \{|N(I_{a_j})|,a_{1-j}\}$. The mathematical induction hypothesis givesAdding the two section bounds proves that simplicial section compression cannot increase the closed graph neighbourhood.

Apply changing simplicial section compressions until none remains. The sum of the global simplicial order on the discrete cube positions strictly decreases at each step: within a section the order is exactly the restriction of the global order. Thus the procedure terminates at a set family $\mathcal{B}$ every coordinate section of which is initial. We now classify the possible terminal families for simplicial section compression, rather than assuming this terminal set family must be globally initial.

If $X<Y$, $X\notin \mathcal{B}$ and $Y\in \mathcal{B}$, then $X,Y$ cannot agree in any coordinate, since that coordinate section would have an omitted earlier member and an included later one. Therefore $Y=X^c$. Let $X$ be the first omitted vertex and $Y$ the last included vertex. If $\mathcal{B}$ is noninitial, $X<Y$ and $Y=X^c$. Any vertex $Z$ strictly between them would have to be included, since an omitted $Z$ paired with $Y$ would have to equal $Y^c=X$. But it would also have to be omitted, since an included $Z$ paired with $X$ would have to equal $X^c=Y$. Thus there is no such $Z$: $X,Y$ are consecutive complementary vertices. Everything before $X$ is included and everything after $Y$ omitted. Hence $\mathcal{B}$ is obtained from the initial segment of its size by replacing $X$ with its immediate successor $X^c$.

There are only two forms of this exception. If $n=2r+1$, consecutive complementary vertices must straddle ranks $r,r+1$; otherwise an intermediate rank or a further vertex in one of their ranks separates them. They are consequentlywith $X$ the last $r$-subset and $Y$ the first $(r+1)$-subset. The corresponding initial segment is all ranks at most $r$. For $r\ge 1$, the omitted $X$ remains in $N(\mathcal{B})$ through a lower neighbour, and every $(r+1)$-subset has at least two $r$-subsets, only one of which was omitted. Thus $N(\mathcal{B})$ contains every rank at most $r+1$, namely $N(I_{|\mathcal{B}|})$. For $r=0$ both singleton closed graph neighbourhoods are the whole $Q_1$.

If $n=2r$, the two complementary vertices must both have rank $r$. The complement map reverses the lexicographic order in that rank, so a consecutive complementary pair must be its central pair. Exactly half the $r$-subsets contain $1$, and all of those precede those missing $1$. Therefore the pair isHere $I_{|\mathcal{B}|}$ comprises all ranks below $r$ and all $r$-subsets containing $1$. For $r\ge 2$, $N(\mathcal{B})$ contains every rank at most $r$, because all lower ranks were retained. Every $(r+1)$-subset containing $1$ has $r\ge 2$ different $r$-subsets containing $1$, so deletion of the one member $X$ removes no vertex of the upper shadow. Consequently $N(\mathcal{B})\supseteq N(I_{|\mathcal{B}|})$. For $r=1$, the two closed graph neighbourhoods both have size three in $Q_2$. These cases exhaust the exceptions. Since the successive simplicial section compressions never increased the closed graph neighbourhood, this proves the vertex-isoperimetric inequality in the discrete cube.

The same argument gives all integer radii. Write $N^t$ for $t$ repetitions of the closed graph neighbourhood. Its application to an initial segment is again initial; the sizes of these initial segments are monotone in the original size. Inducting on $t$ therefore gives

For the concentration question, use uniform probability measure on a finite connected graph and normalize its graph distance by its graph diameter. A sequence is a Lévy family of graphs if, for every fixed $\epsilon >0$ and $\delta >0$, the radius-$\epsilon$ neighbourhood of every set of measure at least $\delta$ has measure tending to one, uniformly over those sets. One may equivalently require this only for sets of measure at least one half. To see the reverse implication, first the radius-$\epsilon /2$ neighbourhood of every positive-density set must eventually have measure greater than one half. Otherwise its complement has measure at least one half, while the radius-$\epsilon /4$ neighbourhood of that complement misses the original positive-density set, contradicting the half-measure condition. Apply the half-measure condition once more to the radius-$\epsilon /2$ neighbourhood, enlarging it by another $\epsilon /2$, to obtain the full claim. The metric normalization is essential here.

For $Q_n$, the graph diameter is $n$. A uniformly chosen vertex has size $Z_n$ with binomial distribution $\mathrm{Bin}(n,1/2)$, expectation $n/2$ and variance $n/4$. Fix $\delta >0$ and choose $C>0$ so that $1/(4C^2)<\delta$. By Chebyshev's inequality,For sufficiently large $n$, put $k_n=\lfloor n/2-C\sqrt{n}\rfloor \ge 0$. Every initial segment of measure at least $\delta$ contains the complete ranks through $k_n$. Its radius-$t$ graph neighbourhood therefore contains every rank at most $k_n+t$. Taking $t=\lfloor \epsilon n\rfloor$, the all-radius vertex-isoperimetric inequality in the discrete cube gives, uniformly for $|\mathcal{A}|\ge \delta 2^n$,The last Chebyshev's inequality is used only when its denominator has positive square root. These are precisely the radius-$\epsilon$ neighbourhoods in the normalized graph distance. The discrete cubes form a Lévy family. In fact, taking $t=\lfloor n^{3/4}\rfloor$ in the same bound makes the omitted measure $O(n^{-1/2})$ for each fixed $\delta$: a radius that is $o(n)$ already suffices.

For fixed $d\ge 1$, the nearest-neighbour grid $[n{]}^d$ has graph distance ${\sum }_i|x_i-y_i|$ and graph diameter $d(n-1)$. Take the slab ${\mathcal{A}}_n=\{x:x_1\le \lceil n/2\rceil \}$, whose uniform measure is at least one half. Its integer radius-$t$ graph neighbourhood is exactly $\{x:x_1\le \min (n,\lceil n/2\rceil +t)\}$: changing the first coordinate alone attains the minimum distance to the slab. For $0<\epsilon <1/(2d)$ and $t=\lfloor \epsilon d(n-1)\rfloor$, the omitted proportion tends toThus there is failure of concentration in fixed-dimensional grids, and the fixed-dimensional grids do not form a Lévy family with normalized graph distance.

The empty family satisfies the bound, so assume $\mathcal{F}$ is nonempty and choose a graph according to the uniform distribution on a finite set $F\in \mathcal{F}$. Let $Y$ be its random vector of edge indicators, indexed by $E=\left(\genfrac{}{}{0ex}{}{[n]}{2}\right)$. Then its information entropy is $H(Y)={\log }_2|\mathcal{F}|$.

For each vertex $v$, put $S_v=\{e\in E:v\in e\}$, so $Y_{S_v}$ records the graph neighbourhood of $v$. The possible graph neighbourhoods form an intersecting family of subsets of $[n]\setminus \{v\}$: the graph intersection of any two members of $\mathcal{F}$ has no isolated vertex at $v$. A subset and its complement cannot both occur. Pairing the $2^{n-1}$ subsets into complementary pairs gives at most $2^{n-2}$ possible graph neighbourhoods. The maximum entropy on a finite alphabet therefore givesThis argument applies for $n\ge 2$. For $n=1$ the assumed nonempty family cannot exist, since its only possible graph has an isolated vertex.

Each edge belongs to exactly two of the sets $S_v$. To obtain the needed instance of Shearer inequality directly from the preceding compression argument, repeatedly apply a union-intersection compression to incomparable members of the multiset $(S_v{)}_{v=1}^n$. Each such step strictly increases ${\sum }_S|S{|}^2$, byThe potential is bounded and integer-valued, so the process terminates in a chain under inclusion. Coordinate multiplicities stay equal to two, so, for $E\ne \varnothing$, the terminal chain consists of two copies of $E$ and $n-2$ empty sets. The compression of an entropy sum now givesExponentiating proves the entropy bound for graphs with isolated-vertex-free intersections: