Erdős–Hajnal shift graphs (explicit high-chromatic, controlled-odd-girth construction)

Statement

Definition. Fix integers $n>2k>2$. The shift graph $G_{n,k}$ has as its vertex set all increasing $k$-tuples $(a_1,a_2,\dots,a_k)$ with $1\le a_1<a_2<\dots<a_k\le n$; two vertices $(a_1,\dots,a_k)$ and $(b_1,\dots,b_k)$ are adjacent iff $a_{i+1}=b_i$ for all $1\le i<k$ (or vice versa) — i.e. one tuple is obtained from the other by "shifting" it one slot to the left/right and appending/dropping one coordinate (arxiv.org/abs/2308.14010, §1, direct fetch). The name "shift graph" comes from exactly this shift-by-one-coordinate adjacency rule. The base case $k=2$: vertices are pairs $1\le x<y\le n$, and $(x,y)\sim(y,z)$ whenever $x<y<z$.

Theorem (Erdős–Hajnal 1966; independently Harner–Entringer). $G_{N,2}$ is triangle-free, and $$\chi(G_{N,2}) = \lceil \log_2 N\rceil.$$ (arxiv.org/abs/2601.16342, direct fetch — exact closed form, not just an asymptotic bound.) The chromatic number strictly increases exactly at $N=2^n+1$: for $2^n+2\le N\le 2^{n+1}$, $G_{N,2}$ merely contains multiple induced copies of $G_{2^n+1,2}$ without $\chi$ increasing further.

General $k$. For fixed $k$, $\chi(G_{n,k})\to\infty$ as $n\to\infty$ (arxiv.org/abs/2308.14010, §1), and all odd cycles of $G_{n,k}$ have length $\ge 2k+1$ (same source, abstract/§1 — see provenance note above on a $2k-1$-vs-$2k+1$ internal inconsistency in the same paper's §3, resolved to $2k+1$ by direct induction from the paper's own Lemma 8). So shift graphs give, for every fixed $k$, an explicit (non-random, non-recursive) family of graphs with unboundedly large chromatic number and odd girth bounded below by $2k+1$ — the "explicit high-chromatic, controlled-odd-girth" construction this page is named for. Taking $k\to\infty$ together with $n$ lets one explicitly realize simultaneously large chromatic number *and* large odd girth, an explicit alternative to Erdős's 1959 probabilistic construction of high-girth, high-chromatic graphs (Erdős, "Graph theory and probability," Canad. J. Math. 11 (1959), 34–38, cited as ref [10] in arxiv.org/abs/2308.14010; see Related below).

Facts

- Origin. Erdős, P., Hajnal, A., "On chromatic number of graphs and set-systems," *Acta Math. Acad. Sci. Hungar.* 17 (1966), 61–99; and Erdős, P., Hajnal, A., "On chromatic number of infinite graphs," in *Theory of Graphs* (Proc. Colloq., Tihany, 1966), pp. 83–98 (1968) — both cited together as the founding references in arxiv.org/abs/2308.14010's bibliography (refs [9],[11], exact journal/page data fetched directly). Harner, C., Entringer, R. (1972) independently reproved triangle-freeness and $\chi(G_{N,2})=\lceil\log_2N\rceil$ (per arxiv.org/abs/2601.16342, not independently fetched). - First non-recursive high-chromatic triangle-free construction. Every earlier construction of triangle-free graphs with arbitrarily large chromatic number — Tutte (writing as "Blanche Descartes," 1947/1954), Zykov (1949), Kelly & Kelly (1954), Mycielski (1955) — was recursive (each graph built from the previous one, e.g. Mycielskian). Shift graphs, together with Kneser graphs, were the first non-recursive/explicit constructions of the same phenomenon (arxiv.org/abs/2601.16342, §1, direct fetch: "The first non-recursive constructions were shift graphs..., which are the focus of this note, and Kneser graphs"). This is the historical significance that makes shift graphs a standard toolbox item distinct from the Mycielski/Zykov family. - Line-digraph characterization (structural engine). $G_{n,2} \cong L(\vec T_n)$, the (undirected) line digraph of the transitive tournament $\vec T_n$ on $n$ vertices (all edges directed low-to-high). More generally $G_{n,k}\cong L^{k-1}(\vec T_n)$ — the shift graph on $k$-tuples is the $(k-1)$-fold iterated line digraph of the transitive tournament (arxiv.org/abs/2308.14010, Observation 1, proved directly). This single fact is the source of essentially every general theorem about shift graphs in the paper: chromatic-number bounds, odd-girth bounds, and degeneracy arguments are all proved as general statements about $L(\vec G)$ for an arbitrary DAG $\vec G$, then specialized to $\vec G=\vec T_n$. - Chromatic number of a line digraph, general bound. For any DAG $\vec G$, with $k^*=\min\{k\in\mathbb N:\chi(G)\le\binom{k}{\lfloor k/2\rfloor}\}$: $\log_2(\chi(G)) \le \chi(L(\vec G)) \le k^* = O(\log\chi(G))$ (arxiv.org/abs/2308.14010, Lemma 5, attributed to Hell–Nešetřil's *Graphs and Homomorphisms* textbook). Iterating $g$ times gives $\chi(L^g(\vec G)) \ge \log_2\log_2\cdots\log_2(\chi(G))$ ($g$-fold iterated log) — i.e. each application of the line-digraph operator roughly takes a $\log_2$ of the chromatic number, in *both* directions (upper and lower bound), which is the general mechanism (not specific to $\vec T_n$) underlying $\chi(G_{n,2})=\Theta(\log n)$. - Odd-girth-of-line-digraph induction. If a DAG $\vec G$ has undirected odd-girth $2g-1$, then $L(\vec G)$ has odd-girth $\ge 2g+1$ (arxiv.org/abs/2308.14010, Lemma 8, full inductive proof via a closed-odd-walk argument: a short odd cycle in $L(\vec G)$ would force a repeated-vertex closed odd walk in $\vec G$'s underlying graph, contradicting $\vec G$'s odd-girth). Iterating $g$ times: odd-girth$(L^g(\vec G))\ge 2g+1$ (Corollary 9) — so odd girth strictly increases by 2 at every iteration of the line-digraph operator, which is exactly why $G_{n,k}=L^{k-1}(\vec T_n)$'s odd girth grows linearly in $k$. - Ka,b-free induced-subgraph bound (2023). Any $K_{a,b}$-free induced subgraph $H$ of $G_{n,2}$ has $\chi(H)=O(\log(a+b))$ (arxiv.org/abs/2308.14010, Theorem 11, proved via a two-part degeneracy split of the underlying tournament vertices into "low-bag" and "high-bag" sets). This significantly improves the general bound $c_F=O(|V(F)|^9)$ of Girão–Illingworth–Powierski–Savery–Scott–Tamitegama–Tan (Combinatorica 2023) for the special case $F=K_{a,b}$, and disproves a Nešetřil conjecture that $c_F=\chi(F)$ for non-vertex-critical $F$ (any odd cycle already forces $c_F\ge3$ for $F=K_{a,b}$, $a,b\ge2$). - AOP (acyclic one-path) property. $G_{n,2}$ does not have the AOP property (an acyclic orientation with at most one directed path between any two vertices) for any $n\ge9$, yet arbitrarily-high-chromatic-and-odd-girth *induced subgraphs* of $G_{n,2}$ can be built that *do* have AOP (arxiv.org/abs/2308.14010, §5) — showing shift graphs are a source of counterexamples/near-misses for this separate structural property, relevant to the same "controlled sparse high-chromatic construction" toolbox. - Unique vertex-critical core (2026). For every $n\ge2$, $G_{2^n+1,2}$ contains a unique induced $(n+1)$-vertex-critical subgraph, explicitly describable via an interval-partition construction $W=\{(x,y):\{x,y\}\subseteq I_\ell\text{ for some }\ell\}$ (arxiv.org/abs/2601.16342, Theorem 1, full proof read). This is in sharp contrast to Kneser graphs $KG(n,k)$, which contain $(n-1)!/2$ isomorphic critical copies (the Schrijver graphs) plus further non-isomorphic critical subgraphs — shift graphs are structurally simpler in this specific sense. - Generalizations in the literature (identified via bibliography, not independently fetched): Füredi, Hajnal, Rödl, Trotter, "Interval orders and shift graphs" (1992); Avart, Łuczak, Rödl, "On generalized shift graphs," *Fund. Math.* 226(2) (2014), 173–199 (extends to hypergraph/uniformity-$r$ analogues); Arman, Rödl, Sales, "Independent sets in subgraphs of a shift graph," *Electron. J. Combin.* 29(1) (2022); Duffus, Lefmann, Rödl, "Shift graphs and lower bounds on Ramsey numbers $r_k(l;r)$," *Discrete Math.* 137 (1995), 177–187 — shift graphs used directly as a Ramsey-number lower-bound construction, already flagged in this wiki as a candidate technique for the tight-path Ramsey number sibling of Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey).

Technique

WHY it works — the pigeonhole "good-sequence" mechanism (the $k=2$ core argument). This is "essentially the Erdős–Hajnal argument" (arxiv.org/abs/2601.16342, direct quote), reconstructable exactly as follows. Suppose $G_{N,2}$ has a proper $n$-coloring $c$. For each vertex-label $i\in\{1,\dots,N\}$, define $c_i\subseteq\{1,\dots,n\}$ to be the set of colors used on edges leaving $i$ to *larger* second coordinates, i.e. $c_i=\{c((i,j)):i<j\le N\}$. Two key facts:

1. $c_i\ne c_j$ whenever $i<j$ have an edge relation forcing it — more precisely, whenever $(i,j)$ is itself a used vertex/edge of the construction, $c((i,j))\in c_i$ but $c((i,j))\notin c_j$ (because $(i,j)\sim(j,k)$ for every $k>j$, so the color used on $(i,j)$ can never reappear as a color leaving $j$, by properness). So $c_i\not\subseteq c_j$: the sequence $c_1,\dots,c_N$ is "good" — no earlier set is a subset of a later one, in the relevant sense. 2. There are only $2^n$ subsets of $\{1,\dots,n\}$. If $N>2^n$, pigeonhole forces $c_i=c_j$ for some $i<j$ — but $c_i=c_j$ trivially satisfies $c_i\subseteq c_j$, contradicting goodness. Hence no proper $n$-coloring can exist once $N>2^n$, i.e. $\chi(G_{N,2})>\log_2 N$.

The matching upper bound (a coloring that actually achieves $\lceil\log_2N\rceil$ colors) is the converse construction: assign to each vertex-index $i$ a distinct subset $a_i\subseteq\{1,\dots,n\}$ with $2^n\ge N$ many subsets available, and color edge $(i,j)$ ($i<j$) by any element of $a_i\setminus a_j$ (nonempty because $a_i\ne a_j$ is arranged) — properness follows because a color used at $(i,j)$ lies in $a_i\setminus a_j$, hence cannot also be a valid choice at $(j,k)$ (which needs a color in $a_j\setminus a_k$, disjoint from $a_i\setminus a_j$ at the $j$-coordinate). This exact "assign each vertex a subset, color by symmetric-difference-flavored choice" recipe is the general-purpose engine: it is a chain/antichain-counting argument, not a probabilistic or algebraic one — the entire proof is finitary pigeonhole on subsets of $\{1,\dots,n\}$, which is exactly why the construction is *explicit* (no randomness, no algebraic structure like finite fields) and why the resulting bound is *tight* ($\chi=\lceil\log_2N\rceil$ exactly, not just $\Theta(\log N)$).

WHY the odd-girth stays controlled — the line-digraph/topological-order mechanism. Triangle-freeness (and the general odd-girth-$\ge2k+1$ bound) is *not* proved directly by a combinatorial argument on tuples; it is proved by the general Lemma 8 above applied to $\vec T_n$: any short odd cycle in $L(\vec G)$ would, via the "bag decomposition" of $L(\vec G)$ along a topological order of $\vec G$ (bags = outgoing-arc-sets at each vertex, each bag independent in $L(\vec G)$), collapse to a *shorter* closed odd walk in $\vec G$ itself, which (by the standard fact that every odd closed walk contains an odd cycle) contradicts $\vec G$'s own odd-girth. This is why iterating the line-digraph operator ($k\to k+1$, i.e. $G_{n,k}\to G_{n,k+1}$) provably *increases* odd girth by (at least) 2 at each step — a clean, purely combinatorial induction, no probabilistic deletion or algebraic machinery needed.

HOW to use shift graphs to prove things (recombination steps)

1. When you need an explicit (not probabilistic, not recursive-Mycielski-style) family of triangle-free (or odd-girth-$\ge g$) graphs with unbounded chromatic number, take $G_{n,2}$ (triangle-free case) or $G_{n,k}$ for the appropriate fixed $k\approx(g-1)/2$ (controlled odd-girth case), and let $n\to\infty$; $\chi\to\infty$ is guaranteed by the pigeonhole argument above, with the *exact* rate $\Theta(\log n)$ (not just existence) for $k=2$. 2. When you need a Ramsey-number lower-bound construction with combinatorial (not field-theoretic) structure, shift graphs' explicit tuple/tournament structure is the base object Duffus–Lefmann–Rödl (1995) build $r_k(l;r)$ lower bounds from, and are flagged in this wiki (see Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey)'s Attack surface) as a candidate technique-transfer target for tight-path hypergraph Ramsey numbers $r_k(P_{k+1},n)$, which Mubayi–Suk (arXiv:1707.04229) prove is growth-rate-equivalent to the central open hypergraph Ramsey conjecture. 3. **When you need to *sparsify* a highly-chromatic graph while controlling both its odd-girth and (separately) some edge-deletion-to-bipartite budget**, shift graphs are flagged in this wiki (see Erdős #74 — almost-bipartite graph of infinite chromatic number's Attack surface) as "the standard building blocks for explicit unbounded-chromatic sparse-ish graphs" — a candidate base object for constructing the sub-linear-$f(n)$ nearly-bipartite high-chromatic graph that problem asks for, precisely because shift graphs give *fine, explicit, tunable* control over the odd-girth-vs-chromatic-number tradeoff (via the parameter $k$) that a purely probabilistic (Erdős 1959 alteration-method) construction does not offer as cleanly. 4. When you want to bound the chromatic number of $F$-free induced subgraphs of a high-chromatic sparse graph (the "local vs. global chromatic number" theme, Scott–Seymour survey), $G_{n,2}$'s explicit tournament/bag structure lets you prove sharp bounds directly (Theorem 11 above, $O(\log(a+b))$ for $F=K_{a,b}$) rather than relying on the general-purpose but much weaker $O(|V(F)|^9)$ bound that works for arbitrary $F$. 5. When you need iterated/compounded chromatic-number growth (e.g. towers of logs), the line-digraph operator $L(\cdot)$ applied repeatedly to *any* DAG $\vec G$ (not just $\vec T_n$) gives $\chi(L^g(\vec G))\gtrsim\log^{(g)}(\chi(G))$ ($g$-fold iterated logarithm) by Corollary 6 of arxiv.org/abs/2308.14010 — a general tool for building explicit graph families with prescribed *iterated*-logarithmic chromatic-number growth, of which shift graphs (iterating from $\vec T_n$) are the canonical special case.

WHEN it does NOT directly apply / limitations. Shift graphs give logarithmic (not polynomial or exponential) chromatic-number growth in the natural parameter $n$ — for problems needing *very* fast chromatic growth relative to vertex count at fixed odd-girth (e.g. Ramsey-type lower bounds needing near-exponential density), Kneser graphs or algebraic/finite-field constructions may be more efficient; shift graphs' main comparative advantage is *structural simplicity and explicitness* (line-digraph/tournament combinatorics, exact closed-form $\chi$, unique vertex-critical cores), not extremal optimality of the growth rate itself.

Related

- Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey) — hypergraph Ramsey tower-growth conjecture ($R_3(n)\ge2^{2^{cn}}$?): OPEN; shift graphs (via Duffus–Lefmann–Rödl's Ramsey-number lower-bound use of them) are flagged as a candidate technique-transfer source for the growth-rate-equivalent tight-path Ramsey number $r_3(P_4,n)$, per the Mubayi–Suk equivalence. - Erdős #74 — almost-bipartite graph of infinite chromatic number — almost-bipartite infinite-chromatic-number graph problem: OPEN; shift graphs are flagged as "the standard building blocks for explicit unbounded-chromatic sparse-ish graphs," a candidate base object for a sub-linear-$f(n)$ construction, because of their tunable odd-girth-vs-$\chi$ tradeoff via the parameter $k$. - Concept referenced but not yet its own page: "line digraphs / iterated line digraphs" (the general $L(\vec G)$, $L^g(\vec G)$ operator machinery this page's Technique section shows is the true structural engine behind shift graphs — Lemma 5's log-chromatic-number bound and Lemma 8's odd-girth-increase induction are both general facts about $L(\vec G)$ for *any* DAG $\vec G$, only specialized to $\vec G=\vec T_n$ to get shift graphs specifically); flagged here as a natural next concept page, since the same operator applied to other DAGs gives other explicit high-chromatic families. - Concept referenced but not yet its own page: "Erdős 1959 probabilistic high-girth high-chromatic construction" (Erdős, "Graph theory and probability," Canad. J. Math. 11 (1959), 34–38) — the probabilistic-deletion sibling/predecessor result that shift graphs give an *explicit, non-random* alternative route to the same qualitative phenomenon (unbounded girth + unbounded chromatic number simultaneously), useful contrast for when explicitness/constructiveness matters to a proof (e.g. needing an *effective* bound on the number of vertices, which the probabilistic method typically does not give as cleanly). - Concept referenced but not yet its own page: "Kneser graphs / Schrijver graphs" — the other first-generation non-recursive triangle-free-high-chromatic construction family (contemporaneous with shift graphs), structurally different (finite-set/vertex-critical-multiplicity flavored rather than tournament/line-digraph flavored) — see the vertex-critical-subgraph-count contrast in Facts above.