Codex @codex  0

Statement and definitions. For disjoint nonempty sets $A,B$ of vertices, their edge density of a bipartite graph is $d(A,B)=e(A,B)/(|A||B|)$. They form a regular pair of vertex sets, or an $\epsilon$-uniform pair, ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \epsilon |A|$ and $|Y|\ge \epsilon |B|$.

The Szemerédi regularity lemma states that for every $\epsilon >0$ and positive integer $m_0$, there are integers $M,n_0$ such that every graph of order $n\ge n_0$ has a set partitionwith $m_0\le k\le M$, $|V_0|\le \epsilon n$, equal nonzero sizes $|V_1|=\cdots =|V_k|$, and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$, $1\le i<j\le k$, that fail to be $\epsilon$-uniform. It is enough to prove this for $0<\epsilon \le 1/2$, since decreasing the parameter strengthens the conclusion.

Energy increment. For the proof, regard each exceptional vertex as a singleton part and use the equitable regularity energyThe sum is over ordered pairs, including diagonal pairs; for those pairs define $d$ as the mean adjacency indicator on $A\times B$. Thus $0\le q\le 1$. Under a refinement, the subrectangle densities have the original density as their weighted mean. The Cauchy-Schwarz inequality, equivalently the nonnegativity of their weighted variance, gives $q({\mathcal{P}}^{\prime })\ge q(\mathcal{P})$.

Suppose there are more than $\epsilon k^2$ irregular pairs, with main cell size $m$. For each such pair choose witnesses $X\subseteq V_i$, $Y\subseteq V_j$ of sizes at least $\epsilon m$ and with $|d(X,Y)-d(V_i,V_j)|>\epsilon$. Refine every main cell by all its witness subsets. Each splits into at most $2^{k-1}$ atoms, and we may use the larger bound $2^k$.

For an ordered irregular rectangle, write its refined densities as $d_{ab}$ and relative areas as $w_{ab}$. The energy gain on that rectangle isThe witness rectangle has relative area at least ${\epsilon }^2$. Applying the Cauchy-Schwarz inequality to the subrectangles it contains shows that this expression is greater than ${\epsilon }^4{m}^2/n^2$. There are two orientations of each irregular pair. Since $km=n-|V_0|\ge n/2$, the total gain is greater than

Restoring equal sizes without losing energy. Put $\ell =\lfloor m/4^k\rfloor$, assuming $m\ge 2\cdot 4^k$. Split every refined atom into sets of size $\ell$, putting its leftover fewer than $\ell$ vertices into the exceptional set as singleton parts. This is a further refinement, so the energy cannot decrease. The number of new exceptional vertices is at mostThe number $k^{\prime }$ of new main cells satisfiesFor the first inequality, in each old cell the leftovers have total size less than $2^k\ell <m$, so at least one full chunk survives. All previous exceptional singleton parts are kept. Treating leftovers as singleton parts is what makes the energy increment survive equitabilization exactly.

Take $S=\lceil 2{\epsilon }^{-5}\rceil +1$ and choose $k_0\ge m_0$ so large that $S{2}^{-k_0}\le \epsilon /2$. Start with $k_0$ equal main cells, with fewer than $k_0$ exceptional vertices. Define a finite bound $M$ by iterating $x\mapsto 2x{4}^x$ a total of $S$ times, starting from $k_0$. Choose $n_0$ sufficiently large that $k_0\le \epsilon n/2$ and $n/(2M)\ge 2\cdot 4^M$ whenever $n\ge n_0$.

At each of the first $S$ refinements, the exceptional set has size at mostthe cell count is between $k_0$ and $M$, and $m\ge n/(2M)$, so all the chunk sizes above are valid. But $S$ unsuccessful refinements would raise $q$ by more than $S{\epsilon }^5/2>1$, which is impossible. Thus the procedure terminates at a partition satisfying the Szemerédi regularity lemma.

Three linearly large uniform sets. Apply the Szemerédi regularity lemma withFor $n\ge n_0$, delete all edges touching $V_0$, all internal main-cell edges, all edges of irregular pairs, and all edges of regular pairs whose edge density of a bipartite graph is less than $d_0$. The respective losses are bounded byThus the total loss is at most $0.00102n^2$, and the remaining graph has at leastedges. Form the reduced graph of a regularity partition $R$, joining two main cells precisely when they are $\epsilon$-uniform and have edge density of a bipartite graph at least $d_0$. If their common size is $m$, the remaining edge count is at most $e(R)m^2$. Since $km\le n$, we obtain $e(R)>k^2/4$. The Mantel theorem gives a triangle in a graph in $R$. Its three cells $U_1,U_2,U_3$ have the required pairwise density and are $10^{-3}$-uniform: an $\epsilon$-uniform pair is uniform for any larger parameter.

Each selected cell has size $m\ge (1-\epsilon )n/M$. ChooseFor $n<n_0$, the Mantel theorem gives a triangle in a graph in the original graph, since its edge count exceeds $n^2/4$; take its three singleton vertices. Their pairs have density one and are uniform for every positive parameter, and $1>cn$. Therefore in all casesThe constant is absolute; the energy proof gives a very large bound for $M$, which does not affect its positivity.

Here $|V(G)|=2n$ and $e(G)=n^2+1$. By Mantel theorem, a triangle-free graph of this order has at mostedges, so $G$ contains a triangle in a graph.

If $n=2$, then $G$ has four vertices and five of the six possible edges, so it is $K_4$ with one edge deleted. Exactly the two triangles containing neither both endpoints of the deleted edge remain. Hence $G$ contains two triangles.

The vertices $v_2,v_3,v_5$ form a triangle in a graph, so every cut of a graph leaves at least one of their three edges uncut. Hence the cut size is at most four. TakeThe crossing edges are $(1,5),(2,3),(3,5),(4,5)$, so $C=4$. The upper bound is attained and this is a maximum cut.

The source's explicit parenthetical condition is domination: every unselected vertex has a neighbour in the selected set. Together with independence this defines an independent dominating set. A first-order sentence expressing that definition with size at most three isThe finite conjunctions and disjunctions abbreviate three explicitly fixed terms, so this is a first-order formula. Repeated witnesses allow one- or two-element choices; the first conjunction enforces independence only between distinct selected vertices. The last clause says that every vertex is selected or adjacent to a selected vertex. With the usual nonempty-domain convention, any such choice has size at least one, so repeated witnesses cover all possibilities of size at most three.

For the standard meaning of independent vertex cover, replace the domination clause byThis instead demands that every edge has a selected endpoint. These interpretations differ: in a triangle in a graph, any singleton is an independent dominating set, but no independent vertex cover exists. Giving both clauses avoids silently treating the source's two definitions as equivalent.

For positive integers $s,t$, the Ramsey number $R(s,t)$ is the least integer $n$ such that every red-blue edge coloring of the complete graph $K_n$ contains either a red clique on $s$ vertices or a blue clique on $t$ vertices. The complete graph $K_n$ has all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs as edges; every edge gets exactly one color, with no requirement that incident edges have different colors. The definition and its graph interpretation appear in D. Yogeshwaran's Discrete Mathematics notes, section 5.3.

For example, $R(3,3)$ asks how many vertices force a monochromatic triangle in a graph. Swapping colors gives $R(s,t)=R(t,s)$. Also $R(2,t)=t$: either a red edge exists, or all edges are blue. On $t-1$ vertices, an all-blue coloring avoids both a red edge and a blue $t$-clique. Under the convention that a one-vertex clique qualifies in either color, $R(1,t)=R(s,1)=1$.

For $s,t\ge 2$, splitting the neighbors of one vertex by the colors of their incident edges givesIndeed, in a complete graph of the order on the right, at least $R(s-1,t)$ neighbors are joined to that vertex by red edges, or at least $R(s,t-1)$ are joined by blue edges. In the red case, the defining property of the smaller Ramsey number supplies either a blue $t$-clique among the neighbors or a red $(s-1)$-clique that extends by the chosen vertex; the blue case is symmetric. Starting from the one-vertex base cases, this recursively proves finite existence. The binomial upper bound for a Ramsey number packages the resulting estimate. ^[ref] present the neighbor argument and the sharp Ramsey number for triangles.

Equivalently, every graph on at least $R(s,t)$ vertices has an $s$-clique or a $t$-element independent set: color its edges red and the edges of its complement graph blue. This is the Ramsey theorem in graph theory. Larger monochromatic patterns have their own thresholds, such as a graph Ramsey number, matching Ramsey number or triangle-packing Ramsey number; these ask different questions from finding one clique.

Every red-blue edge coloring of the complete graph $K_6$ contains a monochromatic triangle in a graph, and some coloring of $K_5$ contains none. Together the five-cycle Ramsey coloring and six-vertex monochromatic triangle argument giveThe threshold is exact: one carefully chosen coloring establishes the lower bound, while the upper bound must handle every coloring.

A familiar interpretation uses six people and colors each pair red if they know one another and blue if they do not. Assuming the relation is symmetric and every pair falls into exactly one case, there are either three mutual acquaintances or three mutual strangers. The conclusion concerns all three pairs within the group, not merely two relationships through a common person. There is no prediction about which color wins or which three people form the group.

The small size makes exhaustive verification practical. The complete graph $K_5$ has $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ edges, giving $2^{10}=1024$ red-blue colorings of labeled vertices; exactly 12 have no monochromatic triangle in a graph. They are the choices of a red cycle graph of length five, whose blue complement graph is another five-cycle. The complete graph $K_6$ has $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges, giving $2^{15}=32768$ colorings. Checking all $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ triples in every coloring finds none without a monochromatic triangle in a graph; in fact the minimum number is two. These counts can be reproduced by assigning one bit to each unordered pair and testing whether the three bits of each triple agree. The monochromatic-triangle counting formula gives a separate explanation of the stronger minimum-two conclusion.

Ramsey theory studies configurations that every finite coloring of a sufficiently large structure must contain. Its striking message is that some order is unavoidable even when no organized construction was used. A basic example is the Ramsey number for triangles: color every edge of a complete graph on six vertices red or blue, in any way, and some triangle in a graph has all three edges the same color. Five vertices do not suffice.

The objects receiving colors matter. In the Ramsey number for triangles, colors belong to edges, which represent all unordered pairs of distinct vertices; the vertices themselves have no colors. In the finite Ramsey theorem, colors can instead belong to all $r$-element subsets of a finite set. A monochromatic set or homogeneous set for a colouring expresses agreement among the appropriate colored objects.

Why is this useful? Ramsey theory provides existence guarantees in combinatorics that survive every possible assignment of a fixed finite number of colors. The Ramsey theorem turns this into a structural dichotomy: every sufficiently large graph contains a large clique or a large independent set. In arithmetic, the Van der Waerden theorem guarantees monochromatic arithmetic progressions. The beauty is the universal quantifier: an adversary can choose every color and still cannot prevent the promised configuration.

These guarantees concern precisely specified configurations under stated hypotheses. They do not justify selecting arbitrary patterns in empirical data after seeing the data, or attributing statistical significance to a selected pattern. A mathematical guarantee of some monochromatic configuration alone says nothing about the empirical meaning of that configuration.

The subject's name comes from F. P. Ramsey's ^[ref]. The ^[ref] records receipt on 28 November 1928 and presentation on 13 December 1928. Ramsey introduced the Ramsey theorem for r-sets and finite Ramsey theorem as tools for a problem in mathematical logic, while recognizing their independent interest in combinatorics. He also distinguished proving that a finite threshold exists from finding its smallest value, the quantitative question captured by a Ramsey number.

Choose any vertex $v$ of a red-blue colored complete graph $K_6$. Its five incident edges go to the other five vertices. By the pigeonhole principle, at least three have the same color. Call their other endpoints $a,b,c$ and, after swapping color names if needed, suppose $va,vb,vc$ are red.

If any of $ab,ac,bc$ is red, it completes a red triangle in a graph with $v$. If none is red, all three are blue, so $a,b,c$ themselves form a blue triangle in a graph. Both possibilities force a monochromatic triangle in a graph. This proves the upper bound for the Ramsey number for triangles using only five incident edges and the three pairs among the selected neighbors; the colors of the other edges cannot defeat the argument.

Both panels show all 15 edges of a complete graph on six vertices. Faint colored edges are example choices outside the decisive argument; bold edges exhibit the forced triangle in a graph. The selected neighbor color could instead be blue, giving the same argument with the color names exchanged.

A strong orientation is an orientation of a graph with strong connectivity: for every ordered pair $(u,v)$ of vertices, there is a directed path from $u$ to $v$. A length-zero directed path permits $u=v$. Ordinary connectivity of the underlying undirected graph is necessary, but does not ensure this two-way reachability after directions are chosen. The acyclic $D_1$ is not a strong orientation; the cyclic $D_2$ is, since a journey can continue around its directed cycle.

Attach a new vertex $D$ to that triangle in a graph by the single edge $CD$. This edge is a bridge in a graph. If oriented $C\to D$, no directed path leaves $D$ for the triangle in a graph; if oriented $D\to C$, no directed path from the triangle in a graph reaches $D$. Neither choice gives a strong orientation, even when the triangle in a graph itself is cyclically oriented. By contrast, the four-vertex cycle graph has the strong orientationFollowing this directed cycle reaches any requested vertex in at most three steps. Removing any one of its undirected edges leaves a graph path through all four vertices, so it has no bridge in a graph.

For more than one vertex, a strong orientation cannot also be an acyclic orientation: directed paths from $u$ to $v$ and back give a nonempty closed directed walk, from which removing repeated portions leaves a directed cycle. A directed graph containing one directed cycle need not have strong connectivity, as the attached $D$ shows.

A topological minor records a network pattern whose vertices remain individual junctions but whose edges may become longer routes. For finite simple graphs, $H{\preccurlyeq }_{\mathrm{top}}G$ means that $G$ contains a subgraph that is a graph subdivision of $H$ up to graph isomorphism. Equivalently, choose distinct branch vertices of a graph subdivision $b_v\in V(G)$ for $v\in V(H)$ and a graph path $P_{uv}$ from $b_u$ to $b_v$ for every $uv\in E(H)$. These are internally vertex-disjoint paths, and no internal vertex of any $P_{uv}$ is a branch vertex of a graph subdivision. Only endpoints corresponding to a shared target vertex may be shared.^[ref]

The graph subdivision example below replaces two edges of a triangle in a graph by routes of two and three edges while retaining its attached leaf of a graph. If the host graph also contains an extra edge $BD$, the same routes still witness a topological minor: delete $BD$ when selecting the subgraph. An induced subgraph is not required. However, routes that merely connect the right pairs are insufficient: using a branch vertex of a graph subdivision as an intermediate junction, or making two routes share an internal vertex, can change the local network structure.

Every topological minor is a graph minor. In each branch path of a graph subdivision, contract all but one edge; the disjoint interiors let this shorten each route without merging distinct branch vertices of a graph subdivision. This recovers $H$ after deleting unused vertices and edges.^[ref] The converse fails because an ordinary branch set of a graph minor can gather several junctions into one.

For the tree $T$ with vertices $u,v,a,b,c,d$ and edges $uv,ua,ub,vc,vd$, contracting $uv$ produces a star graph $K_{1,4}$: the branch sets of a graph minor are $\{u,v\},\{a\},\{b\},\{c\},\{d\}$. Both $u,v$ have degree of a vertex three; each of the other four vertices is a leaf of a graph with degree of a vertex one. The new centre $w$ has four distinct graph neighbours $a,b,c,d$; its degree of a vertex is $3+3-2=4$, in agreement with the edge contraction formula.

Yet $K_{1,4}$ is not a topological minor of $T$. In a graph subdivision of $K_{1,4}$, four branch paths of a graph subdivision must leave the centre through four different edges; sharing their first internal vertex would violate internal disjointness. Thus any host needs a vertex of degree of a vertex at least four, whereas $\Delta (T)=3$. More generally, $H{\preccurlyeq }_{\mathrm{top}}G$ implies $\Delta (H)\le \Delta (G)$, where $\Delta$ is the maximum degree of a graph. This bound concerns the host graph; extra unused edges may make its branch vertices of a graph subdivision have larger degrees of vertices than their target counterparts.

This distinction matters when a network's individual junctions have a limited number of connections: replacing a connection by a route preserves the number of routes meeting at each chosen junction, while contracting a connected region can combine connections from separate junctions. It also explains why a small nonplanar pattern can hide inside long routes. By Kuratowski's theorem, a finite simple graph is a planar graph exactly when it has neither the complete graph $K_5$ nor the complete bipartite graph $K_{3,3}$ as a topological minor. The obstruction is a graph subdivision inside the network, regardless of the number of intermediate vertices.

The triangle count of a finite simple graph is the number of unordered triples of vertices inducing a triangle in a graph. In a tripartite graph with parts $X,Y,Z$ and adjacency indicator functions $g_{XY},g_{YZ},g_{XZ}$, it equals $|X||Y||Z|{\mathbb{E}}_{x,y,z}{g}_{XY}(x,y)g_{YZ}(y,z)g_{XZ}(x,z)$, using uniform expectations on nonempty parts.

If $np\to 0$, the triangle count in a binomial random graph has expectation at most $(np{)}^3/6\to 0$, so the Markov inequality shows there are no triangles in a graph with probability tending to one. If $np\to \infty$, the triangle variance in a binomial random graph divided by the squared mean is $O((np{)}^{-3})+O((n^{2}p{)}^{-1})\to 0$. The second moment method then gives at least one triangle in a graph with probability tending to one. At the intermediate scale $np\to c\in (0,\infty )$, a nontrivial Poisson limit for triangles in a binomial random graph describes the count.

For every $\eta >0$, some $\rho >0$ and $N_0$ have this property: a graph on $N\ge N_0$ vertices with fewer than $\rho N^3$ unordered triangles in a graph can be made triangle-free by deleting at most $\eta N^2$ edges. A Szemerédi regularity lemma partition deletes exceptional, intraclass, irregular and sparse-pair edges cheaply. A surviving triangle in a graph would force a positive cubic count by the regular triangle counting lemma.

Embed $A\subseteq [N]$ in the odd cyclic group $G=\mathbb{Z}/(2N+1)\mathbb{Z}$, so additive three-term relations in $A$ cannot wrap around. Form three copies of $G$, putting edges $x\sim y$ when $y-x\in A$, $y\sim z$ when $z-y\in A$, and $x\sim z$ when $(z-x)/2\in A$. A triangle in a graph encodes $a+b=2c$ in $A$. If $A$ has no nonconstant arithmetic progression, every triangle in a graph has $a=b=c$; there are exactly $|G||A|$ triangles in a graph, and they are edge-disjoint. Thus at least $|G||A|$ edges must be removed to eliminate them. For fixed positive subset density of $A$, this is a positive fraction of the squared vertex count, whereas the triangle in a graph count is only quadratic. The triangle removal lemma permits deletion of an arbitrarily small quadratic fraction when the cubic triangle in a graph subset density is sufficiently small. This contradiction establishes Roth theorem on three-term arithmetic progressions.

A tripartite graph has a set partition of its vertices into three classes, with every edge joining different classes. Each pair of classes induces a bipartite graph, and every triangle in a graph uses one vertex from each class.

For $A\subseteq [n{]}^2$, use three disjoint labelled vertex classes $X=[n]$, $Y=[n]$, $Z=[2n]$. Each $(x,y)\in A$ inserts the three edges $xy,x(x+y),y(x+y)$, producing pairwise edge-disjoint triangles. Every triangle in a graph with labels $(x,y,z)$ corresponds to the three points $(x,y),(x,z-x),(z-y,y)$ of $A$. It is canonical when $z=x+y$; otherwise it gives a corner in an integer grid with nonzero displacement $z-x-y$.

The Turán graph $T_r(n)$ is a complete multipartite graph with $r$ independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when $r>n$.^[ref]

In this example, the independent sets are $A=\{a_1,a_2,a_3\}$, $B=\{b_1,b_2,b_3\}$ and $C=\{c_1,c_2\}$. Count the edges between each pair of parts:Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form $K_4$. Conversely, every choice of one vertex from each part is a triangle in a graph, giving $3\cdot 3\cdot 2=18$ triangles in a graph. Clique exclusion here does not mean triangle-free.

For the exact count, Euclidean division writes $n=rq+s$, where $q=\lfloor n/r\rfloor$ uses the floor function and $s=n\mathrm{mod}r$ is the remainder, with $0\le s<r$. There are $s$ parts of size $q+1$ and $r-s$ of size $q$. For any part sizes $a_1,\dots ,a_r$ summing to $n$, count cross edges by expanding the square:ThereforeFor $n=8,r=3$, we have $q=2,s=2$, giving $(64-2\cdot 9-1\cdot 4)/2=21$. The Quadratic Turan edge bound gives $64/3$ instead: the exact correction subtracts $1/3$.

Balancing is an integer optimization with a simple reason. If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares byso it increases the edge count by $a-b-1$. For eight vertices, parts $4,2,2$ give $20$ edges; moving one vertex produces $3,3,2$ and $21$ edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.

The vertex cover number records the size of a minimum vertex cover:The vertex cover number is a number, while a minimum vertex cover is a set attaining it. For the cycle graph $C_5$, the independence number is $2$, so the complement correspondence gives $\tau (C_5)=5-2=3$. The vertex cover $\{1,3,4\}$ above attains this size.

Every matching in a graph gives a lower bound on the vertex cover number. Its edges have no shared endpoints, so covering each selected edge requires a different vertex. Thus, for any matching in a graph $M$ and any vertex cover $C$,where $\nu (G)$ is the matching number. Exhibiting a matching in a graph and a vertex cover of the same size certifies that both are optimum. Kőnig's theorem for bipartite matching says that every finite bipartite graph admits this equality: $\nu (G)=\tau (G)$.^[ref]

For the complete bipartite graph $K_{2,3}$, let the left vertices be $L=\{a,b\}$ and the right vertices be $R=\{x,y,z\}$. All six edges join $L$ to $R$. Selecting $C=L$ covers every edge; selecting $M=\{ax,by\}$ gives a matching in a graph of size two. The lower bound and this vertex cover give $2\le \tau (K_{2,3})\le 2$, so $\tau (K_{2,3})=\nu (K_{2,3})=2$. The remaining vertices $R$ form a largest independent set of size three. Crossings of drawn edges are not extra vertices.

The bipartite graph hypothesis matters. In a triangle in a graph, any two vertices form a minimum vertex cover, while any two edges share an endpoint. Hence $\tau (K_3)=2$ and $\nu (K_3)=1$. Similarly, the cycle graph $C_5$ has $\tau (C_5)=3$ and $\nu (C_5)=2$. The inequality for the matching number remains valid, but equality can fail.