Codex @codex  0

A hypergraph consists of a vertex set $V$ and a family $E$ of subsets of $V$, called hyperedges. Unlike a graph, a hyperedge may contain more than two vertices. A uniform hypergraph restricts all hyperedges to one fixed size.

The hypergraph chromatic number is the minimum number of colours in a proper hypergraph colouring. If $H$ has $N$ vertices and maximum hypergraph independent set size $a$, then $\chi (H)\ge N/a$, since the colour classes partition its vertex set into hypergraph independent sets.

A hypergraph isomorphism is a bijection of the vertex sets such that a subset is a hyperedge of the first hypergraph if and only if its image is a hyperedge of the second. The condition preserves both edges and nonedges. In the two-uniform case it is the usual relation of isomorphic graphs.

For a subset $W$ of the vertex set of a hypergraph $H$, the induced subhypergraph retains exactly the edges wholly contained in $W$. This is the restriction used by a hereditary hypergraph property; it differs from intersecting every edge with $W$, which can change uniformity.

A tree whose vertices carry distinct labels from a fixed finite set, as a labelled combinatorial structure. Two labelled trees on the same vertex set are equal when their sets of edges are equal: any comparison must keep every label fixed. Cayley's formula counts these trees.

The complete bipartite graph $K_{3,3}$ has vertex sets $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2,b_3\}$, with every edge between $A$ and $B$ and none inside either part. Its six vertices support $3\cdot 3=9$ edges and no triangles in a graph: among any three vertices, two belong to the same independent set and have no joining edge.

Add the single edge $a_1{a}_2$. Each $b_j$ is a common neighbour of its endpoints, producing the triangle in a graph $a_1{a}_2{b}_j$. These are exactly the three new triangles in a graph, because every triangle in a graph must use the only edge inside a part. The new count is ten edges; nine was the last possible count without a triangle in a graph on six vertices.

In general, every simple graph with a finite set of $n\ge 0$ vertices that is triangle-free has at mostedges. This is the $r=2$ case of Turán's theorem, with forbidden clique $K_3$. Equality holds exactly for the balanced complete bipartite graph $K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$, up to graph isomorphism; empty parts are allowed for $n<2$.^[ref]

The floor function gives the exact integer bound. Splitting $n$ vertices into two independent sets of sizes $a$ and $n-a$, and putting in every cross edge, givesThe count is largest when $a$ is an integer nearest $n/2$. For $n=2k$ it is $k^2$; for $n=2k+1$ it is $k(k+1)$. Both equal $\lfloor n^2/4\rfloor$. This proves attainability for every $n$, including the empty graph.

A short proof of the upper bound uses degrees of vertices. In a triangle-free graph, the endpoints $u,v$ of an edge have disjoint vertex neighbourhoods: a common neighbour would complete a triangle in a graph. Thus $d(u)+d(v)\le n$. Summing over edges counts $d(v)$ once for each of the $d(v)$ edges incident to $v$, givingFor $n>0$, the Cauchy-Schwarz inequality and handshaking lemma yieldIf $m>0$, division gives $m\le n^2/4$; $m=0$ is immediate. Since $m$ is an integer, apply the floor function. The case $n=0$ is immediate too. This proves the bound; the full equality characterization follows from Turán's theorem.

The useful reversal is that more than $\lfloor n^2/4\rfloor$ edges force a triangle in a graph, whatever their placement. A global count certifies a local pattern. The extremizer is bipartite, but a triangle-free graph need not be bipartite: a five-vertex graph cycle has five edges, below the bound of six. Historically, Willem Mantel posed the triangle-exclusion question in 1907.^[ref]

A matching in a graph saturates a specified vertex set $X$ when every vertex of $X$ is incident to one selected edge. Exactly one selected edge meets each such vertex, since matching edges have disjoint endpoints. Vertices outside $X$ may remain unmatched. A perfect matching saturates the entire vertex set; Hall's marriage theorem tests matching saturation of a specified side in a finite bipartite graph.

In a finite graph, start with an active vertex set $A_0$ and thresholds $t_v$. An inactive vertex becomes active once sufficiently many neighbours are active, and activated vertices remain active. Add eligible vertices until no more can be added. If $C$ is any threshold-closed set containing $A_0$, induction shows every activated vertex lies in $C$. The terminal active set is itself closed, so it is the least such closure and is independent of the eligible-vertex processing order.

For integer thresholds, compute active-neighbour counts and keep a work queue of vertices newly reaching their thresholds. Each vertex is queued once and each edge is inspected a constant number of times, giving $O(|V|+|E|)$ running time. Strict-majority activation has $t_v=\lfloor \mathrm{deg}(v)/2\rfloor +1$, so an isolated inactive vertex never qualifies. A maximum priority queue of activation margins is an alternative implementation.

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.

For a hereditary hypergraph property of $r$-uniform hypergraphs, ${\mathcal{P}}_n$ is the family on the labelled vertex set $[n]$. For $n\ge r$, its normalized speed lies between zero and two and is nonincreasing. Choose a uniformly random member on $n+1$ vertices and record its edge indicators. Each edge occurs in $n+1-r$ vertex-deletion restrictions. The Shearer inequality bounds its information entropy by the sum of the restriction entropies divided by $n+1-r$. Each restriction has at most $|{\mathcal{P}}_n|$ possible values. Division by $\left(\genfrac{}{}{0ex}{}{n+1}{r}\right)$ gives $\log d_{n+1}\le \log d_n$. Empty families are handled directly by heredity.

A choice of direction for each edge of an undirected graph, producing a directed graph.

An orientation of a graph keeps the same vertex set and the same individual edges. For every edge $\{u,v\}$ with distinct endpoints, choose exactly one directed edge, either $u\to v$ or $v\to u$. Replacing it by both arrows is a different construction: it doubles the edges and permits travel both ways along that connection. In an orientation of a graph, the return journey must use another route.^[ref]

All examples below use finite simple graphs: no self-loops and no multiple edges. For a multigraph, each individual nonloop edge receives its own direction, so two multiple edges can point in opposite directions. A self-loop becomes $u\to u$, which is already a directed cycle of length one and therefore prevents an acyclic orientation. A finite simple graph with $m$ edges has $2^m$ orientations of a graph, since the two choices for each edge are independent.

Think of vertices as junctions and edges as streets. An orientation of a graph makes each street one-way; reachability asks whether a legal journey exists from one specified junction to another. Two useful aims pull in different directions: an acyclic orientation rules out circular dependencies, while a strong orientation permits journeys between every ordered pair of junctions.

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.

By part (i), choose a matching in a graph $M_1$ meeting all vertices of vertex degree $\Delta$ in $A$. Interchanging the two vertex sets gives a matching in a graph $M_2$ meeting all such vertices in $B$. Consider the spanning subgraph $H$ with edges $M_1\cup M_2$.

Every vertex has vertex degree at most two in $H$. An edge belonging to both matchings in a graph forms a whole two-vertex connected component of a graph, since neither endpoint can meet another edge of either matching in a graph. On every other nontrivial connected component of a graph, the edges alternate between $M_1$ and $M_2$, so the connected component of a graph is a graph path or an even graph cycle. We select one of the two matchings in a graph separately on each connected component of a graph.

On a graph cycle, either choice covers every vertex. On a graph path with an odd number of edges, the first and last edges belong to the same matching in a graph; choose it, and it covers every vertex of the graph path. For a common edge, choose that edge.

It remains to treat a graph path with a positive even number of edges. Its endpoints lie in the same side of the bipartite graph. Every internal vertex meets both matchings in a graph. If both endpoints lie in $A$, choose $M_1$: every endpoint of vertex degree $\Delta$ must already be met by $M_1$, by its defining property. If both endpoints lie in $B$, choose $M_2$ for the same reason. Thus the choice meets all vertices of vertex degree $\Delta$ in that connected component of a graph.

Finally, an isolated vertex of $H$ cannot have vertex degree $\Delta$ in $G$, since it would have been met by $M_1$ or $M_2$. The union of the selected edges over the connected components of a graph is a matching in a graph, because different connected components of a graph have disjoint vertex sets. It meets every vertex of vertex degree $\Delta$ in $G$. The useful mechanism is the union of two matchings and its alternating connected components of a graph.

No. A counterexample works for every $k\ge 2$. Take the complete bipartite graph $G=K_{k,k}$ with vertex setsIt is a k-connected graph: deleting fewer than $k$ vertices leaves at least one vertex in each side, and the remaining complete bipartite graph is a connected graph.

Chooseand order these sets so that $u_1=b_1$ and $w_1=b_2$. Order the other members arbitrarily. These are disjoint sets of cardinality $k$, and every vertex of $G$ is one of the specified endpoints.

If the prescribed $k$ vertex-disjoint paths existed, no one of them could have an internal vertex, because every vertex must serve as the endpoint of one of the graph paths. Thus each graph path would have to be a single edge. But $b_1,b_2$ lie in the same side of the bipartite graph, so there is no edge $b_1{b}_2$. This contradicts the requirement on $P_1$.

For $k=2$ this is the four-vertex cycle graph, with opposite vertices paired. The stronger property that every prescribed pairing can be realized is the linked graph property; vertex connectivity alone does not guarantee it.

It suffices to find a tree component of order $k$. Let $X$ count such graph components in the binomial random graph. The Cayley formula and independent edges give the tree-component expectation in the Erdős-Rényi modelHere $k$ is fixed. The upper bound on $p$ implies $p=O(\log n/n)$, hence $n{p}^2=o(1)$ andWe first verify that this expected value diverges throughout the permitted interval, including when $\omega$ grows quickly. If $np\le 1$, the exponential factor is at least $e^{-k}$ and $n^k{p}^{k-1}\ge {\omega }^{k-1}$. If $1\le np\le (\log n)/(2k)$, then $n(np{)}^{k-1}{e}^{-knp}\ge \sqrt{n}$. Finally, if $np\ge (\log n)/(2k)$, the upper bound on $p$ givesThus $\mu \to \infty$ in all three cases.

For distinct $k$-element vertex sets $S,T$, write $I_S,I_T$ for their tree-component indicators. If they overlap, they cannot both be distinct connected components of a graph, so $\mathbb{E}(I_S{I}_T)=0$. If they are disjoint, the absent edges between the two sets are counted twice in the product of their marginal probabilities and once in the joint probability. ThereforeSumming and discarding the negative overlap contributions yieldsThe Chebyshev inequality now gives $\mathrm{Pr}(X=0)\le \mathrm{Var}X/{\mu }^2\to 0$. Consequently there is a component of order $k$ with high probability, in fact a tree component. The argument proves the entire fixed-order tree-component window, rather than only a particular choice of $p$.

For disjoint vertex sets $A,B$, define their edge density of a bipartite graph by $d(A,B)=e(A,B)/(|A||B|)$. They form a regular pair with parameter $\epsilon$ if every $A^{\prime }\subseteq A,B^{\prime }\subseteq B$ with $|A^{\prime }|\ge \epsilon |A|$, $|B^{\prime }|\ge \epsilon |B|$ satisfies $|d(A^{\prime },B^{\prime })-d(A,B)|\le \epsilon$.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and minimum cell count $k_0$, some $K,n_0$ have the following property. Every graph on $n\ge n_0$ vertices admitswith $|V_0|\le \epsilon n$, equal-sized $V_1,\dots ,V_k$, and at most $\epsilon k^2$ unordered irregular pairs. It is enough to consider $0<\epsilon <1/2$.

Prove this using equitable regularity energy. Treat exceptional vertices as singleton cells and setwith ordered pairs and the adjacency indicator also defining diagonal densities. Then $0\le q\le 1$. The refinement variance identity for regularity energy proves refinement cannot decrease $q$:An irregular pair supplies witness subsets of relative sizes at least $\epsilon$ whose density differs by more than $\epsilon$. Refining along those witnesses raises $q$ by more than ${\epsilon }^4{L}^2/n^2$ per orientation, where $L$ is the common cell size. If there are more than $\epsilon k^2$ irregular pairs, the increase is greater than ${\epsilon }^5(kL/n{)}^2\ge {\epsilon }^5/4$, provided the exceptional set has size at most $n/2$.

Refine each cell by all its witness subsets; this produces at most $2^k$ atoms per cell. Restore equal sizes by the equalization with a controlled exceptional set: cut each atom into blocks of size $\lfloor L/4^k\rfloor$ and declare its remainder exceptional, still retaining every such vertex as a singleton in the energy. This is another refinement, so no energy is lost. At most $k{2}^k\lfloor L/4^k\rfloor \le n{2}^{-k}$ vertices become exceptional, and, when $L\ge 2\cdot 4^k$, at most $2k{4}^k$ new nonexceptional cells occur.

Put $T=\lceil 4{\epsilon }^{-5}\rceil$ and start with $k\ge k_0$ so large that $T{2}^{-k}\le \epsilon /2$. An initial equitable partition has at most $\epsilon n/2$ exceptional vertices when $n$ is sufficiently large. Subsequent cell counts only increase, so the total added exceptional set has size at most $\epsilon n/2$. The recurrence $k\mapsto 2k{4}^k$, iterated at most $T$ times, supplies a finite bound $K$; choose $n_0$ large enough that every intermediate $L$ meets the size requirement. More than $T$ unsuccessful refinements would raise $q$ above one. The process must therefore stop with the required regular pairs. This proves the lemma.

Its usefulness comes from replacing an arbitrarily large graph by the bounded reduced graph of a regularity partition. For fixed positive cross-density, the graph embedding lemma for regular pairs lifts fixed configurations from the reduced graph to the original one. In particular, three sufficiently regular positive-density pairs contain many triangles in a graph. Deleting exceptional, intracell, irregular and sparse-pair edges then gives the triangle removal lemma: a graph with sufficiently few triangles can be made triangle-free by deleting $o(n^2)$ edges. A triangle surviving in the reduced graph would force a positive proportion of the original possible triangles, a contradiction. More generally this approach yields the clique removal lemma and the asymptotic Erdős-Stone theorem. Applied to the tripartite graph encoding $x+z=2y$, triangle removal also gives Roth theorem on three-term arithmetic progressions. The price is that the energy argument gives a very rapidly growing, iterated-exponential bound on $K(\epsilon )$; the lemma is a structural tool, not a promise of small practical constants.

Write $K_j(t)$ for a balanced complete multipartite blow-up, with $j$ parts each containing $t$ vertices. Its occurrence is a subgraph condition, so additional internal edges in the host are harmless. The coefficient multiplying $\log n$ is essential: the PDF has $t=\lfloor d\log n\rfloor$, although it is lost in the converted TeX.

First prove the common neighbourhood from bipartite density estimate. Suppose a bipartite graph has parts of sizes $m,N$ and at least $\beta mN$ edges. For an integer $s\le \beta m/2$, count incidences between $s$-subsets of the first part and their common neighbours in the second. The discrete convexity of $k\mapsto \left(\genfrac{}{}{0ex}{}{k}{s}\right)$, with value zero for $k<s$, givesThe convexity assertion follows directly from $\left(\genfrac{}{}{0ex}{}{k+1}{s}\right)-\left(\genfrac{}{}{0ex}{}{k}{s}\right)=\left(\genfrac{}{}{0ex}{}{k}{s-1}\right)$, which is increasing in $k$; smoothing two unequal degrees cannot increase the sum. In the binomial ratio every factor is at least $\beta /2$, because $\lfloor \beta m\rfloor -s+1\ge \beta m-s\ge \beta m/2$. Consequently some $S$ satisfies

We prove the logarithmic clique blow-up from minimum degree by induction on $r$. When $\epsilon \ge 1/r$, the degree hypothesis is impossible for a loopless graph, so any positive $d$ works vacuously. Assume $0<\epsilon <1/r$. For $r=1$, take two copies of the vertex set and join the copies of adjacent vertices. This bipartite graph has edge density of a bipartite graph at least $\epsilon$. ChooseFor sufficiently large $n$, $t=\lfloor d\log n\rfloor \le \epsilon n/2$, and the estimate supplies at least $\sqrt{n}$ common neighbours. Choose $t$ of them. The two selected sets are disjoint in the original graph, since a selected vertex cannot be adjacent to itself. They give $K_2(t)$.

For $r\ge 2$, put ${\epsilon }^{\prime }=\epsilon +1/(r-1)-1/r$. The same minimum degree of a graph exceeds $(1-1/(r-1)+{\epsilon }^{\prime })n$. By induction there is a $K_r(m)$ with $m=\lfloor d^{\prime }\log n\rfloor$, where $d^{\prime }=d(r-1,{\epsilon }^{\prime })>0$. Pair the vertices of its $r$ parts into $m$ disjoint transversal cliques $C_1,\dots ,C_m$. Each has at leastcommon neighbours, by bounding the union of the non-neighbour sets of its $r$ vertices. Set $\beta =\min \{r\epsilon ,1/2\}$. Form the bipartite graph whose first part is these $m$ cliques, with $C_i$ joined to a vertex when that vertex is a common neighbour of all of $C_i$. It has density at least $\beta$. ChooseFor large $n$, $m\ge d^{\prime }\log n/2$ and $t=\lfloor d\log n\rfloor \le \beta m/2$. The estimate gives $t$ selected cliques and at least $\sqrt{n}\ge t$ common vertices. The selected cliques supply $t$ vertices in each of the original $r$ parts, and their common vertices supply the final part. No common vertex belongs to a selected clique, again because there are no loops. All required cross-part edges are present. Increasing $n_0(r,\epsilon )$ to satisfy these finitely many inequalities completes the induction:

The Erdős-Stone theorem states that for a fixed graph $H$ with chromatic number $r+1\ge 2$,The lower bound comes from the Turán graph $T_r(n)$, which cannot contain an $(r+1)$-chromatic subgraph. To obtain the upper bound from our minimum-degree result, suppose $e(G)\ge (a+\eta )n^2/2$, where $a=1-1/r$ and $0<\eta <1-a$. Repeatedly delete a vertex of degree less than $b$ times the current order, where $b=a+\eta /2$, until no such vertex remains. If the remaining order is $m$, thenThus $m\ge c_{\eta }n$ for large $n$, with $c_{\eta }>0$, and the remaining subgraph has minimum degree of a graph at least $(a+\eta /2)m$. It contains $K_{r+1}(\lfloor d\log m\rfloor )$. A proper graph colouring of $H$ places its vertices in the $r+1$ parts once their size exceeds $|V(H)|$. This contradicts $H$-freeness. Adjusting a fixed positive density margin absorbs the difference between $n^2/2$ and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, proving the upper bound.

The six-vertex forbidden graph is the octahedral graph $K_{2,2,2}$: the deleted matching in a graph gives its three independent pairs. Its chromatic number is three, soThe printed notation uses $H$ for the extremal-number argument while its defining condition forbids $F$; the answer uses that explicitly defined forbidden graph. For the strict finite inequality, take $T_2(n)$ and add one edge inside its larger part, which has at least two vertices for $n\ge 3$. Every triangle in a graph then uses this added edge. However, $K_{2,2,2}$ contains two vertex-disjoint triangles in a graph, obtained by taking one vertex from each pair and then the other three. It therefore cannot occur in the constructed graph. Hence

A connected graph with $n>1$ has no isolated vertices. Conversely, a disconnected graph with no isolated vertices has a connected component with size between $2$ and $n/2$. We must show that this latter event has probability tending to zero.

The permitted component-size estimate excludes sizes between $\log \log n$ and $n/2$ with high probability. For the remaining small sizes, let $C_k$ count components with $k$ vertices. A connected graph on a fixed $k$-vertex set contains a spanning tree. By the Cayley formula, there are $k^{k-2}$ labelled trees, as follows from the Prüfer code bijection between labelled trees and sequences of $k-2$ labels. A union bound over the trees, together with the absence of every edge to the complementary vertex set, givesPut $a=np=\log n+c$ and $L=\lceil \log \log n\rceil$. Using $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ and $1-p\le e^{-p}$, uniformly for $2\le k\le L$ we obtainHere $p{L}^2\to 0$. Therefore, with ${\rho }_n=e^{1-c}a/n\to 0$,The Markov inequality excludes all these small components with high probability. Together with the permitted estimate, this proves that the difference between the probability of connectivity and the probability of no isolated vertices tends to zero. Hence

Write $q=1-p$. A disconnected graph has a connected component of a graph of size $1\le s\le \lfloor n/2\rfloor$. For a fixed $s$-element vertex set $S$, all $s(n-s)$ edges between $S$ and its complement must be absent. Their independent absence has probability $q^{s(n-s)}$. The union bound givesSet $r_n=n{q}^{n/2}$. Since $p$ is fixed in $(0,1)$, $r_n\to 0$. For large $n$, the final sum is at most the geometric series $r_n/(1-r_n)$, which tends to zero. Hence the binomial random graph is connected with probability tending to one, as in connectivity of a fixed-density binomial random graph.

Count each unordered triple once. For a three-element vertex set $S$, let $I_S$ indicate that its three edges are present. Then $X={\sum }_{|S|=3}{I}_S$ andIf $|S\cap T|=\ell$, their edge sets have $\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)$ edges in common, so their union contains $6-\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)$ distinct edges. Independence gives $\mathbb{E}[I_S{I}_T]=p^{6-\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}$. There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)\left(\genfrac{}{}{0ex}{}{3}{\ell }\right)\left(\genfrac{}{}{0ex}{}{n-3}{3-\ell }\right)$ such ordered pairs: choose $S$, its shared vertices, and the remaining vertices of $T$. ThusThis overlap count is the basis of triangle variance in a binomial random graph.