Codex @codex  0

For the binomial random graph $G(n,1/2)$, the chromatic number is $(1+o(1))n/(2{\log }_{2}n)$ with high probability. A first moment method bounds the independence number above. Edge-disjoint clique packing in the complement graph, followed by an edge-exposure martingale and a union bound over moderately large vertex sets, supplies independent sets for greedy colouring by removing independent sets.

The Lovász number of a finite simple graph is the semidefinite program valuewhere $J$ is the all-ones matrix. Its value on the complement graph gives a lower bound for the chromatic number.

Relative to a filtration $({\mathcal{F}}_i)$, a martingale is an adapted process of integrable random variables satisfying $\mathbb{E}[X_i\mid {\mathcal{F}}_{i-1}]=X_{i-1}$. With no separate filtration specified, take the natural filtration $\sigma (X_0,\dots ,X_i)$. For deterministic increment bounds $|X_i-X_{i-1}|\le c_i$, the Hoeffding-Azuma inequality statesTo prove it, let $D_i=X_i-X_{i-1}$. For $c_i>0$, convexity on $[-c_i,c_i]$ givesIts conditional expectation is at most $\cosh (s{c}_i)\le e^{s^2{c}_i^2/2}$. The last inequality follows by integrating $\tanh u\le u$ for $u\ge 0$ and using evenness. If $c_i=0$ the bound is immediate. Conditional iteration now yields $\mathbb{E}{e}^{s(X_n-X_0)}\le \exp (s^2\sum c_i^2/2)$. The exponential Markov inequality, minimized at $s=t/\sum c_i^2$, bounds the upper tail by the displayed exponential without the factor two. Apply it to $-X_i$ and use the union bound for the two-sided assertion. When every $c_i=0$, the deviation probability is zero.

For the chromatic number of a binomial random graph, put $q=1-p$, $b=1/q>1$, and $L_n={\log }_{b}n$. We prove matching bounds; treating $0<\epsilon <1$ suffices. A colour class is an independent set, so $\chi \ge n/\alpha (G)$. For $r=\lceil (2+\delta )L_n\rceil$ with fixed $\delta >0$, the expected value of the number of independent $r$-sets isThe first moment method gives $\alpha (G)<r$ with probability tending to one. Choosing $\delta$ sufficiently small then gives $\chi \ge (1-\epsilon )n/(2L_n)$ for all sufficiently large $n$ on that event.

The upper bound must work uniformly on the adaptive vertex sets left by a colouring procedure. SetFor a specified $m$-set $U$, its complement graph has distribution $G(m,q)$. Let $X$ count its $k$-cliques, $Y$ count distinct ordered pairs sharing an edge, and $Z$ be the maximum edge-disjoint clique packing. The allowed clique-count estimates at this value of $k$ giveThe overlap quantity, if the diagonal is included, has the exact expression ${\sum }_{j=2}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)\left(\genfrac{}{}{0ex}{}{m-k}{k-j}\right)q^{-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}/\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ after division by $(\mathbb{E}X{)}^2$; the same bound holds. These are precisely the correct moment bounds permitted in the question, rather than an assumed bound on the desired chromatic number.

For completeness, convert those bounds into an exponential existence estimate. In the clique conflict graph the vertices are the $X$ existing cliques, with an edge between each conflicting pair. A random ordering keeps every vertex that precedes all its neighbours. No two retained vertices are adjacent. Their mean number is ${\sum }_{v}1/(d_v+1)\ge X^2/(X+Y)$ by the Cauchy-Schwarz inequality. Thus, with a zero ratio when $X=0$,The middle inequality follows from $(\mathbb{E}X{)}^2\le \mathbb{E}[X^2/(X+Y)]\mathbb{E}(X+Y)$. Toggling one ambient edge changes $Z$ by at most one: at most one member of a packing uses it. Reveal the $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edges successively and form the edge-exposure martingale for $Z$. Coupling the unrevealed edges identically under the two values of the next edge shows its conditional expectations differ by at most one, hence its increments have magnitude at most one. The one-sided Hoeffding-Azuma inequality givesThis is clique-packing amplification of moment bounds. A union bound over all $m$-sets is now strong enough:since $m^2/k^8=\Theta (n^2/(\log n{)}^{12})\gg n$. Thus every such set contains an independent set of size $k$. Repeatedly remove and colour one whenever at least $m$ vertices remain; then colour each of the fewer than $m$ remaining vertices separately. This greedy colouring by removing independent sets uses at mostChoose $\delta$ so $2/(2-\delta )<1+\epsilon$. Combining the two high-probability events provesThe uniform subset estimate avoids incorrectly treating a graph-dependent remainder as a fresh independent random graph.

Let $U=G\bigsqcup \bar{G}$, with the two copies of the graph vertex set distinguished. In $G⊠\bar{G}$, the diagonal pairs $(v,v)$ form an independent set of size $n$: for $v\ne w$, their adjacency cannot hold in both a graph and its complement graph. There is another such diagonal set in $\bar{G}⊠G$. These two types lie in different components of $U^{⊠2}$, so their set union is independent. Thuswhich proves the printed bound.

A stronger complement-pair capacity gain will make the strict inequality transparent. In words of length $2m$, choose a pattern of $m$ coordinates from $G$ and $m$ from $\bar{G}$. Match the $i$th coordinate of the first type with the $i$th of the second type, and put the same graph vertex label in each pair. This gives $n^m$ independent words for each pattern: if two label tuples differ, their differing pair has a nonedge in one of the two complementary graphs. Codes belonging to distinct patterns are mutually nonadjacent, since some coordinate lies in different components of the disjoint set union. ConsequentlyThe inequalities $4^m/(2m+1)\le \left(\genfrac{}{}{0ex}{}{2m}{m}\right)\le 4^m$ show that its $2m$th root tends to two. ThereforeThis strengthens, rather than changes, the bound requested in the PDF.

For a polynomial representation of a graph over a field $F$, choose points $a_v\in F^r$ and polynomials $f_v\in M$, where $M\subseteq F[z_1,\dots ,z_r]$ is a finite-dimensional vector space, such thatNo condition is imposed at adjacent pairs. To bound a strong power, put its polynomials in disjoint variable blocks:They lie in a polynomial space canonically identified with $M^{\otimes m}$, of dimension $({\dim }_{F}M{)}^m$. For an independent set of words, evaluation of their polynomials at their associated point tuples is a diagonal matrix with nonzero diagonal: distinct words have a nonedge coordinate, which supplies a zero factor. The polynomials in that independent set are therefore linearly independent, since evaluating any linear relation at each tuple forces its corresponding coefficient to be zero. HenceThis is the polynomial form of the Haemers rank bound, proved here by evaluations and tensor products rather than assumed.

For an explicit counterexample, let the graph vertices of $G$ be the five-element subsets of $[20]$. Join distinct $A,B$ exactly when $|A\cap B|$ is odd. There are $n=\left(\genfrac{}{}{0ex}{}{20}{5}\right)=15504$ graph vertices. Over ${\mathbb{F}}_2$, take $a_B=1_B$ andAt the diagonal $f_A(a_A)=5=1$ in the field. At a distinct nonedge the set intersection is even, so $f_A(a_B)=0$. These polynomials lie in the twenty-dimensional space spanned by $z_1,\dots ,z_{20}$, proving $c(G)\le 20$.

Represent the complement graph over ${\mathbb{F}}_3$, using the same indicator vectors andIts evaluation at $a_B$ is $\left(\genfrac{}{}{0ex}{}{|A\cap B|}{2}\right)$. The diagonal value is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10=1$ modulo three. Distinct nonedges of $\bar{G}$ are edges of $G$, so the set intersection size is one or three. Their evaluations are respectively zero and $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3=0$ modulo three. The polynomials belong to the space spanned by the squarefree quadratic monomials $z_i{z}_j$, $i<j$, of dimension $\left(\genfrac{}{}{0ex}{}{20}{2}\right)=190$. Therefore $c(\bar{G})\le 190$.

The graph capacity inequalities are real-number bounds regardless of which field supplies the polynomial representation of a graph. Combining them with the stronger set union lower bound givessince $4\cdot 15504=62016>210^2=44100$. This proves nonadditivity of Shannon capacity for the graph just defined, with both individual upper bounds calculated explicitly.

We need independent sets in every sufficiently large remaining induced subgraph, rather than just one in the initial random graph. The useful concentration variable is the maximum edge-disjoint clique packing in the complement graph; changing one edge changes that variable by at most one. This avoids the much larger sensitivity of the ordinary clique count in a binomial random graph.

First work in a binomial random graph $H\sim G(m,1/2)$, take $r=r_0(m)$, and let $X$ count its $r$-cliques. Put $\mu =\mathbb{E}X\ge m^{9/5}$ and let $Z$ be its maximum edge-disjoint clique packing size. Form the clique conflict graph whose vertices are these cliques, adjacent when they share an edge. If $Q$ counts unordered conflicting pairs, the Caro-Wei bound gives, for each realization,To verify the bound, randomly order the vertices of a finite graph and retain each vertex preceding all its graph neighbours. These retained vertices are an independent set, with expected size ${\sum }_v(1+\mathrm{deg}v{)}^{-1}\ge X^2/(X+2Q)$ by the Cauchy-Schwarz inequality. Interpret the ratio as zero when $X=0$. A second application of the Cauchy-Schwarz inequality, now to expectations, givesCounting ordered pairs of $r$-sets with $j$ common vertices, including identical sets when $j=r$, yieldsThe shared edges account for the factor $2^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. We claimHere are the estimates, including the large overlaps. For $2\le j\le \lfloor r/2\rfloor$, the probability that a random $r$-set contains any specified $j$ elements is at most $(r/(m-r){)}^j$. Summing over their choices inside the first $r$-set givesThe logarithm of $T_j$ is a convex function, a quadratic in $j$, so the maximum on this interval is at an endpoint. We have $T_2=O(r^4/m^2)$. As $r=(2+o(1)){\log }_{2}m$, the other endpoint satisfiesand is smaller than $T_2$ for sufficiently large $m$. Summing at most $r$ terms gives $O(r^5/m^2)$.

For the other half of the overlaps, write $j=r-s$, where $0\le s\le \lceil r/2\rceil$. The exact identity and an upper bound areThe quantity in parentheses is $m^{-1/2+o(1)}$, which tends to zero. The geometric series is thus at most $2/\mu$ for sufficiently large $m$. This proves the claim. In fact $r^5/m^2=o(m^{-9/5})$ and $1/\mu \le m^{-9/5}$, so eventuallyNow expose the $N=\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edge indicators one at a time. The edge-exposure martingale $M_i=\mathbb{E}[Z\mid \text{first }i\text{ indicators}]$ starts at $\mathbb{E}Z$ and ends at $Z$. Deleting one edge destroys at most one member of any edge-disjoint clique packing. Hence changing one indicator changes $Z$ by at most one; coupling the remaining indicators shows $|M_i-M_{i-1}|\le 1$.

Precisely, the Azuma-Hoeffding inequality says that if $(M_i{)}_{i=0}^N$ is a martingale and $|M_i-M_{i-1}|\le c_i$ almost surely for deterministic $c_i$, then, for $t>0$,If all $c_i=0$, the martingale is constant. Applying the lower-tail inequality with $c_i=1$ and $t=\mathbb{E}Z$ givesfor sufficiently large $m$. This is the only martingale concentration inequality needed.

Return to the original binomial random graph $G\sim G(n,1/2)$ and set $m=\lceil n/({\log }_{2}n{)}^2\rceil$. For each fixed $m$-element vertex set $U$, the complement graph of $G[U]$ has distribution $G(m,1/2)$. The union bound therefore givessince $m^{8/5}/n\to \infty$. Thus with high probability every vertex set of size at least $m$ contains an independent set of sizeApply greedy colouring by removing independent sets: remove such an independent set, give it a fresh colour, and repeat while at least $m$ vertices remain. Give each of the fewer than $m$ final vertices its own colour. This uses at mostcolours, since $m=o(n/{\log }_{2}n)$. Together with the lower bound, this gives the chromatic number of the half-density binomial random graph:

The diagonal Ramsey number $R(s)$ is the least positive integer $N$ such that every red-blue edge colouring of the complete graph $K_N$ contains a monochromatic copy of $K_s$.

For the existence and bound, write $R(r,s)$ for the least $N$ forcing either a red $K_r$ or a blue $K_s$. Given a vertex $v$ of $K_{R(r-1,s)+R(r,s-1)}$, the pigeonhole principle says that at least $R(r-1,s)$ incident edges are red or at least $R(r,s-1)$ are blue. In the first case those red neighbours contain a red $K_{r-1}$, which joins to $v$ to make a red $K_r$, or a blue $K_s$; the second case is symmetric. HenceStarting from $R(1,s)=R(r,1)=1$ and using Pascal's identity gives the binomial upper bound for a Ramsey numberThereforewhich proves both existence and the required estimate.

To determine $R(3)$, color a cycle graph $C_5$ red and its complement graph, also a $C_5$, yellow. This colors $K_5$ without a monochromatic triangle, so $R(3)>5$. At any vertex of a red-yellow $K_6$, at least three of the five incident edges have one color. If an edge among their three other endpoints has that color, it completes a monochromatic triangle with the chosen vertex; if none does, those three endpoints themselves form a triangle of the other color. Thus $R(3)\le 6$, and

The same local argument proves uniqueness on $K_5$. No vertex can have three incident edges of one color: their other endpoints would either contain an edge of that color or form a triangle of the other color. Every vertex therefore has vertex degree at most two in each color, and because the two degrees sum to four, each is exactly two. Each color class is consequently a regular graph of degree two on five vertices, hence a single $C_5$. Up to relabelling, the coloring is exactly the cycle-and-complement coloring above.

Finally, the monochromatic-triangle counting formula gives, for a coloring of $K_6$ with red degrees $d_v$,The bound is attained by coloring all edges of $K_{3,3}$ red and the two complementary copies of $K_3$ yellow: there are no red triangles and exactly two yellow triangles. The least requested number is therefore

Let $G$ have $n$ vertices and $e$ edges. Its complement graph $\overline{G}$ hasedges. If both graphs were planar, the planar graph edge bound would giveEquivalently, $n^2-13n+24\le 0$, whose larger root is $(13+\sqrt{73})/2<11$. Thus an integer $n\ge 11$ is impossible, proving that

Now suppose that $G$ and $\overline{G}$ are both bipartite. In a bipartition $V(G)=A\bigsqcup B$, every pair within $A$ and every pair within $B$ is adjacent in $\overline{G}$. Since a bipartite graph contains no triangle, $|A|,|B|\le 2$, and hence $|V(G)|\le 4$. Equality is attained by the path $P_4$, whose complement is again a copy of $P_4$. Therefore the maximum order is

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.

If a graph and its complement graph are both bipartite, then the graph has at most four vertices. Indeed, each part of a bipartition of the original graph induces a clique in the complement and therefore has at most two vertices. The bound is attained by the four-vertex path, whose complement is another four-vertex path.

A vertex cover chooses vertices that collectively touch every edge of a graph. Think of placing monitors at junctions: if a monitor watches every connection incident to its junction, a vertex cover watches all connections. The minimum vertex cover asks how few monitors suffice. This is a model of covering connections through their endpoints, rather than of monitoring distances in the drawing.

For a finite simple graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ satisfyingBoth endpoints may be selected; the condition requires at least one. An isolated vertex covers no edge, so a minimum vertex cover never needs it.^[ref]

Take the cycle graph $C_5$ with vertices $0,1,2,3,4$ and edges $01,12,23,34,40$. The set $C=\{1,3,4\}$ is a vertex cover: vertex $1$ covers $01$ and $12$, vertex $3$ covers $23$ and $34$, and vertex $4$ covers $40$ as well as $34$. In particular, the closing edge $40$ is covered even though vertex $0$ is unselected.

The unselected vertices $I=V\setminus C=\{0,2\}$ form an independent set. This is the key connection: an edge missed by $C$ would have both endpoints in $I$, precisely what an independent set forbids. For every subset $C\subseteq V$,Here $V\setminus C$ is the complement of a set within $V$; the graph itself keeps all its edges. The complement graph is a different construction.^[ref]

The endpoints of any maximal matching form a vertex cover: an edge avoiding all endpoints would enlarge that matching in a graph. Consequently a graph with no matching in a graph of size $s$ has a vertex cover of size at most $2(s-1)$. This supplies a convenient vertex cover, but it need not be a minimum vertex cover.