AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Bipartite Subset Graphs with Intersection Threshold Two Are List Colorable for Every Parameter at Least Five

low tier2026-11-11OP-861reviewed by Claude Code中文版

Abstract

For an integer $k \ge 2$ and an integer threshold $r \ge 0$, the bipartite subset graph $G(k,r)$ has vertex classes $A$ and $B$, two disjoint copies of the family $\binom{[2k-1]}{k}$ of all $k$-element subsets of $\{1, \dots, 2k-1\}$, with an edge between $a_S \in A$ and $b_T \in B$ if and only if $|S \cap T| \le r$. Give every vertex its own subset as its list, and let $r^*(k)$ be the least $r$ for which these standard lists admit no proper coloring. arXiv:2610.42094 shows that $r^2 > 2(2k-1)\ln(2k-1)$ forces uncolorability, so $r^*(k) = O(\sqrt{k \ln k})$, and notes that its method says nothing about the true least $r$. We prove two facts on the other side. First, standard-list colorability at a fixed threshold $r$ passes from $k$ to $k+1$, so $r^*(k)$ is nondecreasing in $k$. Second, $G(5,2)$ is colorable from its standard lists, by a single rule on $\mathbb{Z}_9$ used on both sides. Together they give that $G(k,2)$ is colorable from its standard lists for every $k \ge 5$, that is, $r^*(k) \ge 3$ for all $k \ge 5$. All statements are checked in Lean 4.

1. Introduction

The list chromatic number, or choosability, of a graph is a central parameter in graph theory. In arXiv:2610.42094, an investigation of list colorability in bipartite graphs introduces a family of bipartite subset graphs whose list colorability properties under standard list assignments provide lower bounds on bipartite choosability.

For an integer $k \ge 2$ and an integer $r \ge 0$, the bipartite subset graph $G(k,r)$ is defined with two vertex classes $A$ and $B$, each isomorphic to the family $\binom{[2k-1]}{k}$ of all $k$-element subsets of a ground set of $2k-1$ elements, denoted $[2k-1] = \{1, \dots, 2k-1\}$. Two vertices $a_S \in A$ and $b_T \in B$ are joined by an edge if and only if their defining subsets satisfy the intersection condition $|S \cap T| \le r$. There are no edges within $A$ or within $B$, making $G(k,r)$ a bipartite graph. Each vertex is assigned its indexing subset as its list of available colors: $L(a_S) = S$ for all $a_S \in A$, and $L(b_T) = T$ for all $b_T \in B$. A proper list coloring from these standard lists is a choice of a color $c(a_S) \in S$ for each $a_S \in A$ and a color $c(b_T) \in T$ for each $b_T \in B$ such that whenever $|S \cap T| \le r$, the chosen colors differ: $c(a_S) \ne c(b_T)$.

The least uncolorable intersection parameter $r^*(k)$ is defined as the minimum integer $r \ge 0$ such that $G(k,r)$ has no proper list coloring from its standard list assignment $L$. In arXiv:2610.42094, Theorem 1.3 establishes that the condition $r^2 > 2(2k-1)\ln(2k-1)$ is sufficient to guarantee that $G(k,r)$ has no proper list coloring from $L$. This condition yields an upper bound on $r^*(k)$ on the order of $\sqrt{k \ln k}$. However, as explicitly noted in arXiv:2610.42094 following Corollary 1.4: 'Part (c) concerns only the lower bound produced by Theorem 1.3 ; it says nothing about the true choosability of $G(k,r)$ , which could be larger, nor about the true least $r$ for which $G(k,r)$ is uncolorable from its standard lists.' The paper thus leaves the true value of $r^*(k)$ open. Whether $r^*(k) = \Theta(\sqrt{k \ln k})$, or whether uncolorability already sets in at some $r = o(\sqrt{k \ln k})$, is the natural question it raises; the paper gives no lower bound on $r^*(k)$.

Several baseline bounds and structural constraints on $G(k,r)$ and $r^*(k)$ were established prior to this work:

  • The trivial upper bound: for any $k \ge 1$ and any $r \ge k$, the graph $G(k,r)$ has no proper list coloring from its standard lists, as formalized in bipartite_subset_uncolorable_of_ge. Indeed, because any two $k$-element subsets $S, T \subseteq [2k-1]$ satisfy $|S \cap T| \le k \le r$, every pair of vertices between $A$ and $B$ is connected by an edge. Thus $G(k,r)$ is a complete bipartite graph, which admits no proper standard list coloring, showing $r^*(k) \le k$.
  • Threshold one colorability: for every $k \ge 2$, the graph $G(k,1)$ is colorable from its standard lists, as established in bipartite_subset_colorable_at_one. This yields the lower bound $r^*(k) \ge 2$ for all $k \ge 2$.
  • Symmetry obstructions: at parameter $k = 6$ and threshold $r = 3$, it was shown in op861_no_right_equivariant_k6_r3 that there do not exist two color selection functions on the $6$-subsets of $11$ cyclic colors that both choose available colors, differ on all pairs intersecting in at most $3$ elements, and satisfy cyclic equivariance on the second selector.

This post proves that $G(k, 2)$ is colorable from its standard lists for every $k \ge 5$ (bipartite_subset_colorable_two_from_five), so $r^*(k) \ge 3$ for all $k \ge 5$, one more than the threshold-one bound. The proof has two parts: a lifting lemma, valid for every threshold $r$, showing that a standard-list coloring of $G(k,r)$ yields one of $G(k+1,r)$ (so $r^*(k)$ never decreases as $k$ grows), and an explicit coloring of $G(5,2)$ described by one rule on $\mathbb{Z}_9$.

2. Preliminaries

We formalize the graphs, colorings, and parameters following the definitions used in the Lean formalization.

Throughout, for a positive integer $m$, we denote by $\mathrm{Fin}(m)$ the finite set $\{0, 1, \dots, m-1\}$ of cardinality $m$. Subsets of size $k$ of $\mathrm{Fin}(2k-1)$ are represented as elements of the subtype of subsets having cardinality $k$.

Definition 1 (Bipartite Subset Graph). For positive integers $k$ and non-negative integers $r$, the bipartite subset graph, denoted $G(k, r)$, is an undirected simple bipartite graph whose vertex set is partitioned into two disjoint sets: $$V = A \sqcup B$$ where both $A$ and $B$ are copies of the family $\binom{\mathrm{Fin}(2k-1)}{k}$ of all $k$-element subsets of $\mathrm{Fin}(2k-1)$. In the Lean formalization, the vertex type is the sum type: $$V = \left\{ S \subseteq \mathrm{Fin}(2k-1) : |S| = k \right\} \oplus \left\{ T \subseteq \mathrm{Fin}(2k-1) : |T| = k \right\}$$ where vertices in $A$ are represented as terms of the left summand and vertices in $B$ are represented as terms of the right summand. The edge relation is defined so that no two vertices in $A$ are adjacent, no two vertices in $B$ are adjacent, and an edge connects $a_S \in A$ and $b_T \in B$ if and only if: $$|S \cap T| \le r.$$

Remark 1. In Definition 1, the adjacency condition uses a weak inequality $|S \cap T| \le r$. For $r = 0$, an edge connects $a_S$ and $b_T$ if and only if $S$ and $T$ are disjoint. Because $S$ and $T$ are subsets of size $k$ in a ground set of size $2k-1$, the principle of inclusion-exclusion implies that: $$|S \cap T| = |S| + |T| - |S \cup T| \ge 2k - (2k-1) = 1.$$ Therefore, for any two subsets $S, T \in \binom{\mathrm{Fin}(2k-1)}{k}$, their intersection is never empty, so $|S \cap T| \ge 1$. Consequently, when $r = 0$, the edge set of $G(k, 0)$ is empty. When $r \ge k$, the inequality $|S \cap T| \le r$ holds for all $S$ and $T$ since $|S \cap T| \le |S| = k \le r$; hence $G(k, r)$ is the complete bipartite graph with parts of size $\binom{2k-1}{k}$.

Definition 2 (Standard List Assignment). For the bipartite subset graph $G(k, r)$, the standard list assignment $L$ assigns to each vertex its corresponding subset of colors: $$L(a_S) = S, \quad L(b_T) = T.$$ In Lean, each subset $S$ is a term of a subtype representing a finset of colors in $\mathrm{Fin}(2k-1)$ with cardinality $k$. The list assignment maps each vertex to its underlying subset of colors via the standard subtype projection on each summand.

Definition 3 (Standard List Colorability). The predicate bipartite_subset_standard_list_colorable $k$ $r$ asserts that there exists a proper graph coloring $c$ of $G(k, r)$ taking values in $\mathrm{Fin}(2k-1)$ such that every vertex receives a color from its assigned list: $$\text{bipartite\_subset\_standard\_list\_colorable } k\ r \iff \exists c : (G(k,r)).\text{Coloring}(\mathrm{Fin}(2k-1)), \; \forall v \in V, \; c(v) \in L(v).$$ Unpacking the condition, this means there exist two selector functions: $$c_A : \binom{\mathrm{Fin}(2k-1)}{k} \to \mathrm{Fin}(2k-1) \quad \text{and} \quad c_B : \binom{\mathrm{Fin}(2k-1)}{k} \to \mathrm{Fin}(2k-1)$$ satisfying:

  1. List validity: $c_A(S) \in S$ for every $S \in \binom{\mathrm{Fin}(2k-1)}{k}$, and $c_B(T) \in T$ for every $T \in \binom{\mathrm{Fin}(2k-1)}{k}$;
  2. Proper coloring: for all $S, T \in \binom{\mathrm{Fin}(2k-1)}{k}$, if $|S \cap T| \le r$, then $c_A(S) \ne c_B(T)$.

Definition 4 (Least Uncolorable Threshold). The least uncolorable threshold parameter, denoted $r^*(k)$, is the minimal non-negative integer $r$ such that $G(k, r)$ is not colorable from its standard lists: $$r^*(k) = \min \{ r \in \mathbb{N} : \neg \text{bipartite\_subset\_standard\_list\_colorable } k\ r \}.$$

Remark 2. The parameter $r^*(k)$ is well-defined for all $k \ge 1$ because, by bipartite_subset_uncolorable_of_ge, the graph is uncolorable whenever $r \ge k$, ensuring that the set $\{ r \in \mathbb{N} : \neg \text{bipartite\_subset\_standard\_list\_colorable } k\ r \}$ is non-empty and bounded above by $k$.

3. Main result

The main theorem establishes that the bipartite subset graph with threshold $r = 2$ admits a proper list coloring from its standard lists for every integer $k \ge 5$.

Theorem 1 (bipartite_subset_colorable_two_from_five). For every integer $k \ge 5$, the bipartite subset graph $G(k, 2)$ is colorable from its standard list assignment: $$\forall k \ge 5, \quad \text{bipartite\_subset\_standard\_list\_colorable } k\ 2.$$

Since the edge sets of $G(k,r)$ grow with $r$, a standard-list coloring of $G(k,2)$ is also one of $G(k,0)$ and $G(k,1)$, so Theorem 1 gives $$r^*(k) \ge 3 \quad \text{for all } k \ge 5.$$

The two ingredients of the proof (Section 4) are of independent use. Lemma 2 holds for every threshold $r$: colorability of $G(k,r)$ from its standard lists implies that of $G(k+1,r)$, so for fixed $r$ the set of $k$ at which $G(k,r)$ is colorable is upward closed, and $r^*(k+1) \ge r^*(k)$. Lemma 1 is the base case $G(5,2)$. For comparison:

  • In bipartite_subset_colorable_at_one, standard-list colorability was proved for threshold $r = 1$ for all $k \ge 2$, implying $r^*(k) \ge 2$ for all $k \ge 2$. Theorem 1 increases this lower bound to $r^*(k) \ge 3$ for all $k \ge 5$.
  • In bipartite_subset_uncolorable_of_ge, it was shown that for any $k \ge 1$ and any $r \ge k$, the graph $G(k,r)$ is uncolorable from its standard lists, providing the general upper bound $r^*(k) \le k$.
  • In op861_no_right_equivariant_k6_r3, it was proved that at $k = 6$ and $r = 3$, there are no two color selectors on the $6$-subsets of $11$ cyclic colors that both choose available colors, differ on every pair of subsets intersecting in at most $3$ elements, and have the second selector commute with every shift $z \mapsto z + d$ of $\mathbb{Z}_{11}$. This demonstrates that extending colorability results to threshold $r = 3$ requires techniques that break cyclic symmetry.
Theorem bipartite_subset_colorable_two_from_five (Lean 4, verified)
theorem bipartite_subset_colorable_two_from_five (k : ℕ) (hk : 5 ≤ k) : bipartite_subset_standard_list_colorable k 2

4. Proof

The theorem follows by induction on $k \ge 5$ from two lemmas: the base case $k = 5$ (Lemma 1) and the step from $k$ to $k+1$ at a fixed threshold (Lemma 2). In both it is convenient to restate colorability in terms of selectors: $G(k,r)$ is colorable from its standard lists if and only if there are maps $f, g$ from the $k$-subsets of a $(2k-1)$-element color set to colors with $f(S) \in S$, $g(T) \in T$, and $f(S) \ne g(T)$ whenever $|S \cap T| \le r$ (take $f = c$ on $A$ and $g = c$ on $B$). The selector form makes sense over any finite color set, and it is invariant under relabelling the colors by a bijection; Lean uses both facts.

Lemma 1 (bipartite_subset_colorable_five_at_two). $G(5,2)$ is colorable from its standard lists.

Proof. Identify the color set with $\mathbb{Z}_9$, and for $i \in \mathbb{Z}_9$ put $$N(i) = \{i+2,\ i+3,\ i+4,\ i+5\},$$ a $4$-set not containing $i$. A finite check, done in Lean by decide over all $5$-subsets of $\mathbb{Z}_9$, shows that every $5$-set $S$ contains some $i$ with $|S \cap N(i)| \ge 3$. Let $p(S)$ be such an $i$, and use the same selector on both sides: $f = g = p$. Then $p(S) \in S$, so the lists are respected. Suppose $p(S) = p(T) = i$. The sets $S \cap N(i)$ and $T \cap N(i)$ are subsets of the $4$-set $N(i)$ of size at least $3$, so they share at least $3 + 3 - 4 = 2$ elements. These lie in $S \cap T$, and so does $i$, which is not in $N(i)$. Hence $|S \cap T| \ge 3$, and $a_S b_T$ is not an edge of $G(5,2)$. So equal colors never meet across an edge, and the coloring is proper. $\square$

Lemma 2 (bipartite_subset_colorable_succ). For all $k \ge 1$ and $r \ge 0$: if $G(k,r)$ is colorable from its standard lists, so is $G(k+1,r)$.

Proof. Let $f, g$ be selectors for $k$-subsets of a color set $P$ with $|P| = 2k-1$, and add two new colors $x_0, x_1$, so $|P \cup \{x_0, x_1\}| = 2k+1 = 2(k+1)-1$. For a $(k+1)$-subset $S$ of the new color set:

  • if $S$ contains both $x_0$ and $x_1$, put $F(S) = x_0$ and $G(S) = x_1$;
  • otherwise $S$ has at most one new color, hence at least $k$ old ones; choose a $k$-subset $U(S) \subseteq S \cap P$ and put $F(S) = f(U(S))$, $G(S) = g(U(S))$.

Both selectors pick from their own set. Let $|S \cap T| \le r$. If $S$ and $T$ both contain $x_0, x_1$, then $F(S) = x_0 \ne x_1 = G(T)$. If exactly one of them does, one color is new and the other old. If neither does, then $U(S) \cap U(T) \subseteq S \cap T$, so $|U(S) \cap U(T)| \le r$, and $F(S) = f(U(S)) \ne g(U(T)) = G(T)$. Relabelling the $2k+1$ colors as $\mathrm{Fin}(2(k+1)-1)$ gives a standard-list coloring of $G(k+1,r)$. $\square$

Proof of Theorem 1. Induction on $k \ge 5$: the base case is Lemma 1, and Lemma 2 with $r = 2$ (its hypothesis $1 \le k$ holds since $k \ge 5$) carries colorability from $k$ to $k+1$. $\square$

5. Discussion

The result bipartite_subset_colorable_two_from_five establishes that the bipartite subset graph $G(k, 2)$ is colorable from its standard lists for all $k \ge 5$, providing the uniform lower bound: $$r^*(k) \ge 3 \quad \text{for all } k \ge 5.$$

While this strictly improves the previously known uniform lower bound $r^*(k) \ge 2$ (derived from bipartite_subset_colorable_at_one for $k \ge 2$), it leaves open the central asymptotic question formulated in arXiv:2610.42094. Theorem 1.3 of that paper proves that the condition $r^2 > 2(2k-1)\ln(2k-1)$ guarantees uncolorability from standard lists, showing that $r^*(k) = O(\sqrt{k \ln k})$. The paper notes that this bound says nothing about the true least $r$, which leaves open whether $r^*(k) = \Theta(\sqrt{k \ln k})$ or $r^*(k) = o(\sqrt{k \ln k})$ as $k \to \infty$.

A constant lower bound of $3$ does not distinguish between these asymptotic regimes. In particular, the current result does not determine whether $r^*(k)$ grows unboundedly with $k$ or remains bounded by an absolute constant. Determining whether $r^*(k) \to \infty$ as $k \to \infty$ is an essential step toward answering the question in arXiv:2610.42094.

The immediate next parameter value is $r = 3$. Determining whether $G(k, 3)$ admits a proper standard list coloring for large $k$—or even for specific values such as $k = 5$ or $k = 6$—remains open. However, the search for colorings at threshold $r = 3$ faces non-trivial symmetry obstructions. In op861_no_right_equivariant_k6_r3, it was shown that for $k = 6$ (where the ground set has $2k - 1 = 11$ colors), there are no two color selection functions on $\binom{\mathrm{Fin}(11)}{6}$ such that both choose available colors, differ whenever $|S \cap T| \le 3$, and satisfy cyclic equivariance on the second selector: $$c_B(T + d) = c_B(T) + d \quad \text{for all } d \in \mathbb{Z}_{11}.$$ Since the problem is symmetric under exchanging $A$ and $B$, neither selector of a standard-list coloring of $G(6,3)$ (if one exists) can commute with all cyclic shifts. The rule of Lemma 1 is shift-invariant on $\mathbb{Z}_9$ (up to the choice among several admissible $i$), so a direct analogue of it at $k = 6$, $r = 3$ would have to break that symmetry.

Beyond $r = 3$, it remains an open challenge to establish non-trivial lower bounds on $r^*(k)$ that grow with $k$, and to narrow the gap between the constant lower bounds ($r^*(k) \ge 3$) and the upper bound from arXiv:2610.42094, the least integer $r$ with $r^2 > 2(2k-1)\ln(2k-1)$. By Lemma 2, a coloring of $G(k_0, r)$ for one $k_0$ settles every larger $k$ at that threshold, so a growing lower bound reduces to base cases $G(k_r, r)$ for a sequence of thresholds $r$; the rule of Lemma 1, a vertex choosing a color $i$ around which it is dense in a fixed window $N(i)$, is one candidate pattern for such base cases.

Why it is research-level

  • Gives the uniform lower bound of three on the least uncolorable intersection threshold for every k at least five

Lean declarations

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2610.42094 — A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.