we-solve (beta)

Math-1347 · mathematics · Graph theory

Fractional Hadwiger

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $G$ be a finite nonempty simple graph. Its chromatic number $\chi(G)$ is the least number of independent vertex sets partitioning $V(G)$. Its Hadwiger number $h(G)$ is the largest $t$ for which there are $t$ pairwise disjoint nonempty connected vertex sets, every pair joined by an edge. Such sets are branch sets of a complete minor.

Define the fractional chromatic number $\chi_f(G)$ by assigning nonnegative real weights $x_I$ to independent sets and minimizing $\sum_Ix_I$ subject to $\sum_{I\ni v}x_I\ge1$ for every vertex $v$. For the fractional Hadwiger number, a bramble is a family $\mathcal B$ of nonempty connected vertex sets such that every two touch: they either intersect or an edge joins them. Assign nonnegative real weights $y_B$ satisfying $\sum_{B\ni v}y_B\le1$ at each vertex. Let $h_f(G)$ be the maximum of $\sum_{B\in\mathcal B}y_B$ over all such brambles and weights. Since $G$ is finite, these optimization problems involve finitely many possible vertex sets.

The source asks for the validity, for every such $G$, of each of the following inequalities: \[ \chi_f(G)\le h(G),\qquad \chi(G)\le h_f(G),\qquad \chi_f(G)\le h_f(G). \] These are separate assertions. In the fractional minor parameter the touching condition is imposed on the entire positive-weight support, rather than merely on some pairs or in expectation; omitting it would define a different quantity.

Short English statement

Compare ordinary and fractional coloring requirements with ordinary and fractional complete-minor parameters in each of three proposed inequalities.

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1347-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1347

Chromatic number beyond clique-minor size: The definition contains three separate fractional inequalities. The paper refutes chi_f(G)<=h(G); it does not settle chi(G)<=h_f(G) or chi_f(G)<=h_f(G).

Colin de Verdière chromatic obstruction: The definition contains three separate fractional inequalities. The paper refutes chi_f(G)<=h(G); it does not settle chi(G)<=h_f(G) or chi_f(G)<=h_f(G).

Linear list-coloring in clique-minor size: The list-coloring theorem implies chi_f(G)<=C h(G), a constant-factor weakening of the first of three fractional Hadwiger clauses; the other two clauses are not settled.

This page records partial support. Complete resolution of the catalogue question is not established by this record.

Fractional Hadwiger

OpenAI's claim

Chromatic number beyond clique-minor size: The counterexample paper claims arbitrarily large finite graphs with $\chi_f(G)>h(G)$, hence also $\chi(G)>h(G)$; no independent vertex set in an example contains three vertices.

Colin de Verdière chromatic obstruction: The manuscript claims finite graphs whose fractional chromatic number is greater than $\mu(G)+1$, and therefore whose ordinary chromatic number violates the same bound; such examples exist at arbitrarily large orders.

Linear list-coloring in clique-minor size: The paper claims a universal constant $C$ with $\chi_{\mathrm{list}}(G)\le C h(G)$ for every finite nonempty graph; the factor is independent of the graph and its order.

Mathematical statement of the claimed result

Mathematical claim 1.
There are finite simple graphs $G$ of arbitrarily large order $m$ with independence number $\alpha(G)\le2$ and maximum size of a pairwise-touching matching less than $m/100$. The resulting corollary states \[h(G)<26m/75+2/3<m/2\le\chi_f(G)\le\chi(G),\] where $h(G)=\max\{t:K_t\text{ is a minor of }G\}$ and $\chi_f,\chi$ are fractional and ordinary chromatic numbers. Thus the exact inequalities $\chi\le h$ and $\chi_f\le h$ fail; no conclusion about replacing $h$ by a fractional minor parameter is supplied.
Mathematical claim 2.
The claimed counterexamples are finite simple graphs of arbitrarily large order $m$ with \[\alpha(G)\le2,\qquad\mu(G)+1<m/2\le\chi(G),\] where $\mu(G)$ is the Colin de Verdière spectral graph invariant. The fractional-coloring corollary strengthens the obstruction to \[\chi_f(G)\ge m/\alpha(G)\ge m/2>\kappa(G)+1\ge\mu(G)+1\ge h(G).\] Here $\kappa$ is its strong-Arnold-property-free spectral relaxation, and $h$ is the largest complete-minor order. In particular both $\chi\le\mu+1$ and $\chi_f\le h$ are refuted. A further corollary gives $\chi_{\mathrm{list}}(G)\le C(\mu(G)+1)$ with an absolute $C$.
Mathematical claim 3.
For every finite nonempty simple graph $G$ there is an absolute integer $C\ge1$, independent of $G$, such that \[\chi_{\mathrm{list}}(G)\le C h(G),\qquad h(G)=\max\{t:K_t\text{ is a minor of }G\}.\] The list chromatic number is the least $k$ for which every assignment of $k$ available colors per vertex permits a proper coloring. Consequently $\chi(G)\le Ch(G)$. The constant-factor bound does not imply the conjectured coefficient $1$.

Outline of the argument

Chromatic number beyond clique-minor size: The graph construction uses Boolean moment representations and paired frames to control compatible vertex distributions. Entropy projection, fingerprints for independent sets, and a capacitated-cut argument transfer the distributional constraints to finite graphs. The resulting obstruction limits clique-minor size, while the small independence number gives a larger fractional chromatic number.

Colin de Verdière chromatic obstruction: Allowed channel images are thinned while preserving the primal distribution, supplying enough compatible pairs for the conflict estimates. A Boolean moment argument restricts low-rank matrix representations. Entropy and finite sampling then produce graphs for which every well-signed matrix with a single negative eigenvalue has too much rank to support the proposed chromatic inequality.

Linear list-coloring in clique-minor size: For small minor-free graphs, a random global partition of colors gives each vertex many eligible bins. Stable-set sampling repeatedly reduces fractional chromatic complexity among eligible vertices. If the reduction failed, separator and connectivity arguments would assemble disjoint clique models into the excluded minor; the resulting small-graph bound feeds the global list-coloring argument.

Formal verification

Family 157 describes Lean coverage for the list-coloring upper bound with a universal multiple of clique-minor size; neither chromatic counterexample is part of this selection.

Chromatic number beyond clique-minor size: No manuscript-specific Comparator is listed in the pinned inventory.

The documented selection does not cover the entire manuscript assertion relevant here.

Colin de Verdière chromatic obstruction: No manuscript-specific Comparator is listed in the pinned inventory.

The documented selection does not cover the entire manuscript assertion relevant here.

Linear list-coloring in clique-minor size: The manuscript links ListHadwiger.lean.

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →