Matching works

12 works

math.CO — Combinatorics

Flow reconfiguration with one modulus for all graphs, and Cereceda's conjecture for bipartite 2-degenerate graphs

Contributed by Dave Goel

This paper answers a question of Esperet, Hendrey, Lagoutte, Marseloo, Norin and Steiner on flow reconfiguration and makes inroads into Cereceda's recolouring conjecture for d=2d=2. Parts I and II are about flows. For a finite multigraph GG and an integer k≥2k\ge 2, let Mk(G)M_k(G) be the graph on the nowhere-zero Zk\mathbb{Z}_k-flows of GG, and Ik(G)I_k(G) the graph on the integer flows FF of GG with 1≤∣F(e)∣≤k−11\le|F(e)|\le k-1 on every edge; two flows are adjacent if the support of their difference is a cycle. We prove that Mk(G)M_k(G) and Ik(G)I_k(G) are connected for every finite bridgeless loopless multigraph GG if k=40k=40, if k=48k=48, or if kk is a multiple of 44 with k≥52k\ge 52. This answers their Problem 1.2. The same holds for k=66k=66, for every prime power pNp^N with N≥6N\ge 6, and for a set of moduli of natural density one; these results do not cover every k≥40k\ge 40. A master theorem for finite abelian groups gives the connectivity of the flow graph F(G,Γ)F(G,\Gamma) for every abelian group Γ\Gamma of order 4040, and a binary form of it for every abelian group of exponent dividing 44 and order at least 3232, in particular F25\mathbb{F}_2^5 (Esperet et al. proved F28\mathbb{F}_2^8). Part III is about colourings: two proper kk-colourings of a graph GG are adjacent if they differ at exactly one vertex. Cereceda conjectured that this graph has diameter O(n2)O(n^2) for every dd-degenerate graph on nn vertices and k=d+2k=d+2; the case d=2d=2 is open. For four colours we prove the diameter bound 2n(n+1)2n(n+1) for every bipartite graph of degeneracy at most 22, with the order n2n^2 sharp in this class, also at girth 66; the bound 5n(n+1)5n(n+1) when an independent set of vertices of degree at most 22 is added; and, with a computer-verified certificate, 4n(n+1)4n(n+1) for every graph of cone width at most 22, a class that contains all graphs of treewidth at most 22 and some graphs of treewidth 33 with triangles.

Author comments: First version: October 23, 2026. This is the expanded version, with many other results, of the paper "The Cereceda (2007) conjecture holds for bipartite 2-degenerate graphs", which is at https://hexagonmath.org/2611.00260 on Hexagon. The ancillary files of this paper (programs and data) are at https://doi.org/10.5281/zenodo.23603238 on Zenodo.

A mix of human-written and AI-generated textHuman understanding: some partsCereceda conjecturedegenerate graphsflow reconfigurationgraph recolouringnowhere-zero flow
Nov 16, 2026181 pages
PDFView work

math.CO — Combinatorics

The independence number of the generalized Johnson graph J(13,5,3)J(13,5,3)

Contributed by Mustafa Stanikzai

Let J(13,5,3)J(13,5,3) be the graph on the 5-element subsets of a 13-element set, two subsets being adjacent when they share exactly 3 elements. We prove that α(J(13,5,3))=33\alpha(J(13,5,3)) = 33. The graph is an explicit unit-distance graph in R12\mathbb{R}^{12}, so χ(R12)≥⌈1287/33⌉=39\chi(\mathbb{R}^{12}) \ge \lceil 1287/33 \rceil = 39; earlier bounds from explicit finite graphs give at most 38. A recent preprint of Davies gives much larger bounds, none from an explicit finite graph. An explicit independent set gives α≥33\alpha \ge 33. For the upper bound, a symmetry reduction splits the problem into 200 clique subproblems, and a certifying solver refutes each one with a proof log that the checker VeriPB accepts. An uncertified computation reproduces the value α(J(13,6,4))=46\alpha(J(13,6,4)) = 46 reported by Exoo and Ismailescu, which gives χ(R12)≥38\chi(\mathbb{R}^{12}) \ge 38.

Author comments: 16 pages. Programs, certificates and proof logs: https://doi.org/10.5281/zenodo.24145863 Changes from version 1: 28 cross-references to lemmas, propositions, claims, definitions and corollaries were printed with the word "Theorem" (for example "Theorem 2.4" for Lemma 2.4). They now carry the correct names. The reference numbers were already correct. Statements, proofs, results and bibliography are unchanged.

A mix of human-written and AI-generated textHuman understanding: all partschromatic number of Euclidean spacegeneralized Johnson graphindependence numbermaximum cliqueproof loggingunit-distance graph
Nov 12, 202616 pages
PDFView work

math.CO — Combinatorics

The Cereceda (2007) conjecture holds for bipartite 2-degenerate graphs

Contributed by Dave Goel

For a graph GG and a positive integer kk, the kk-recolouring graph Rk(G)\mathcal{R}_{k}(G) has the proper kk-colourings of GG as vertices, two of them adjacent when they differ at exactly one vertex. A graph is dd-degenerate if each of its non-empty subgraphs has a vertex of degree at most dd. The Cereceda (2007) conjecture states that, for fixed dd and k≥d+2k \ge d+2, the diameter of Rk(G)\mathcal{R}_{k}(G) is O(n2)O(n^2) for every dd-degenerate graph GG on nn vertices. For d=2d = 2, the conjecture was known to hold for k≥5k \ge 5 by a result of Cereceda; for k=4k = 4, the best bound known for all 22-degenerate graphs is O(n3)O(n^3), due to Bousquet and Heinrich. We prove that the diameter of R4(G)\mathcal{R}_{4}(G) is at most 2n(n+1)2n(n+1) for every bipartite 22-degenerate graph GG on nn vertices; hence the conjecture holds for these graphs. We also show that the order n2n^2 cannot be improved for this class, even for graphs of girth 66. For the upper bound, we fix an ordering of the vertices in which each vertex has at most two later neighbours. In nn stages, we transform any proper 44-colouring into the colouring in which every vertex has the least colour not used by its later neighbours, recolouring each vertex at most twice per stage. Both of our bounds have also been proved in the Lean proof assistant.

Author comments: An expanded version of this paper, with many other results, is posted on Zenodo: https://doi.org/10.5281/zenodo.23603237

A mix of human-written and AI-generated textHuman understanding: some partsCereceda conjecturebipartite graphsdegenerate graphsgraph recolouringreconfiguration
Nov 10, 202617 pages
PDFView work

math.GT — Geometric Topology

The dodecahedron web and its instanton homology

Contributed by Peter Kronheimer, Tomasz Mrowka

For the planar dodecahedron web D, the octahedral diagram of instanton homology reduces the possible values of the SO(3) instanton homology to 60 and 64. The remaining choice is determined by three coefficients of a secondary map. We give a proposed proof that all three vanish and that the dimension is 64. We express the coefficients as counts of instantons on specified foam cobordisms with one-parameter families of metrics. The index calculation requires these instantons to have negative action. An estimate uniform under neck stretching excludes them when the perturbations are sufficiently small. The construction includes local Floer complexes with zero differential, the marking calculation for excision, and a simultaneous choice of regular perturbations compatible with the families. Exact matrices and the supporting foam calculations are provided separately.

Primarily AI-generated textHuman understanding: some partsInstanton homologyTait colorings
Nov 03, 202659 pages
PDFView work

math.CO — Combinatorics

Claw-free perfect graphs are chromatic-choosable.

Contributed by Narayanan Narayanan, Suchismita Mishra, Umesh Shankar

We prove that every claw-free perfect graph GG satisfies ch⁡(G)=χ(G)=ω(G)\ch(G)=\chi(G)=\omega(G). More strongly, if SS is a clique of simplicial vertices of GG and k≥ω(G)k\ge\omega(G), every proper precoloring of SS extends to a proper coloring of GG from arbitrary lists of size kk on V(G)∖SV(G)\setminus S. The proof has three coloring steps: a mixed-list theorem for cobipartite graphs, a precoloring-extension theorem for elementary graphs built on Galvin's kernel method and a homogeneous-pair exchange argument, and a polynomial method (Combinatorial Nullstellensatz) argument for graphs of interval type in which a Vandermonde factor is transferred across each incomplete pair. The three coloring steps are assembled along the structure theorems of Chv\'atal--Sbihi, Maffray--Reed and Chudnovsky--Seymour, using double clique cutsets for composition. As a consequence, every perfect line graph is chromatic-choosable, recovering the theorem of Peterson and Woodall. Our precoloring extension theorem also resolves a conjecture posed by Chudnovsky and Seymour.

A mix of human-written and AI-generated textHuman understanding: all partsClaw-free perfect graphs.Graph coloringList Coloring Conjecture
Nov 02, 202633 pages
PDFView work

math.CO — Combinatorics

Local independent sets and colourings of triangle-free graphs

Contributed by Matthew Bowen, András Máthé, Oleg Pikhurko

This AI-assisted draft constructs, for every sufficiently large DD, a local rule of radius O((ln⁡D)2)O((\ln D)^2) that produces, on any triangle-free graph GG of maximum degree at most DD, a random independent set that includes each vertex with probability at least (1−oD(1))ln⁡D/D(1-o_D(1))\ln D/D. Further properties of the rule yield, for every fixed ε>0\varepsilon>0 and all sufficiently large DD, a randomised LOCAL algorithm that colours any such finite graph GG with at most (1+ε)D/ln⁡D(1+\varepsilon)D/\ln D colours, with high probability, in Oε(ln⁡D)+(ln⁡ln⁡∣V(G)∣)O(1)O_\varepsilon(\ln D)+(\ln\ln |V(G)|)^{O(1)} communication rounds. Applying known transference principles for Borel graphs, we obtain the same asymptotic bound on the number of colours for measurable and Baire-measurable colourings, and for Borel colourings of graphs with finite asymptotic separation index.

Primarily AI-generated textHuman understanding: some partsChromatic numberLOCAL algorithmdescriptive combinatoricsindependent settriangle-free graphs
Oct 31, 202629 pages
PDFView work

math.LO — Logic

Nonpathological extensions of FσF_\sigma ideals and fractional coloring

Contributed by Carlos López-Callejas

The random graph ideal is pathological, answering a question of López-Abad et al. We prove this by constructing a positive hereditarily pathological restriction using Kneser graphs. For an FσF_\sigma ideal I\mathcal I and any lower semicontinuous submeasure φ\varphi with FIN⁡(φ)=I\operatorname{FIN}(\varphi)=\mathcal I, we show that the nonpathological envelope φ^\widehat\varphi generates an ideal that depends only on I\mathcal I and, when proper, is the least nonpathological FσF_\sigma extension of I\mathcal I. Thus, I\mathcal I is nonpathological if and only if FIN⁡(φ)=FIN⁡(φ^)\operatorname{FIN}(\varphi)=\operatorname{FIN}(\widehat\varphi). We also characterize nonpathological FσF_\sigma ideals both as intersections of summable ideals and as intersections of matrix ideals, answering both converses asked by Filipów and Tryba. The least nonpathological FσF_\sigma extension of the random graph ideal is proper and is described by the fractional cochromatic numbers of its finite induced subgraphs.

A mix of human-written and AI-generated textHuman understanding: all partsF-sigma idealsKatětov orderfractional coloringleast nonpathological extensionsmatrix idealsnonpathological submeasurespathological idealsrandom graphsummable ideals
Oct 29, 202638 pages
PDFView work

math.PR — Probability

Existence of the qq-Colorability Threshold for Sparse Random Graphs

Contributed by P. M. Aronow, Patrick Lopatto

For a fixed integer q≥3q \ge 3, we call a graph qq-colorable if its vertices admit qq colors with adjacent vertices colored differently. We prove that there exists dq>0d_q > 0 such that the random graph on nn vertices with independent edge probability d/nd/n is qq-colorable with probability tending to one for fixed 0≤d<dq0 \le d < d_q and to zero for fixed d>dqd > d_q, as n→∞n \to \infty. The same holds for the uniform random graph with ⌊cn⌋\lfloor cn \rfloor edges, for fixed c≥0c \ge 0, with threshold dq/2d_q/2 in cc. For fixed ϵ∈(0,1)\epsilon \in (0, 1), the first loss of colorability under independent uniform additions of pairs of distinct vertices lies with probability at least 1−ϵ1 - \epsilon in a deterministic window of Oq,ϵ(n(log⁡n)−3/2)O_{q, \epsilon}(n(\log n)^{-3/2}) steps, where log⁡\log is natural. The proof uses interpolation to establish convergence and bounds the expected number of pairs needed to destroy colorability of the last colorable graph by identifying random vertices and controlling the growth of classes equal in every coloring.

Primarily AI-generated textHuman understanding: some parts
Oct 29, 2026105 pages
PDFView work

cs.AI — Artificial Intelligence

BLLM: Beyond the LLM with Deep Human-Mind-AI

Contributed by Deep Bhattacharjee, Ushashi Bhattacharya

A system that improves itself keeps every change that passes a check, so a check that makes errors lets mistakes pile up. We compute the least checking that keeps such a system sound. It is an entropy of the costs of the changes, and an endless chain of improvements stays sound at finite cost exactly when that entropy is finite. A stack of checked layers costs more than its layers would cost alone. We also compute how many guesses a proposer needs before a right one appears: human authors come close to this least number, and language models need 1.5 to 4.3 times as many. Anaxia, an engine built on these laws, rebuilt the published 2016 counterexample to Steinberg's conjecture from the rules of a colouring problem alone. The engine is a work in progress, and its rules and search are being revised and extended for the open problems it has not yet settled.

A mix of human-written and AI-generated textHuman understanding: some partsautomated discoveryentropyrecursive self-improvementverification
Oct 20, 202675 pages
PDFView work

math.CO — Combinatorics

Every odd antihole is strongly chromatic-choosable

Contributed by Deep Bhattacharjee, Ushashi Bhattacharya

A hole in a graph is an induced cycle of length at least four, and an antihole is the complement of a hole. Odd holes and odd antiholes are the graphs that, by the strong perfect graph theorem, force the chromatic number above the clique number. Fiujlaali and McDonald studied the odd antiholes inside kk-critical graphs of maximum degree Δ\Delta, proved that such an antihole has at most 2(Δ−k)+72(\Delta-k)+7 vertices, and conjectured that this bound is attained only when the graph is the antihole itself, provided the graph has no odd hole. They reduced this to a statement about list colouring: for every ℓ≥3\ell\ge3, the odd antihole on 2ℓ−12\ell-1 vertices has chromatic number ℓ\ell, and the only assignments of lists of ℓ−1\ell-1 colours from which it cannot be coloured are those in which all lists are equal. This is their Conjecture~9, and they proved it when all the lists lie in a common set of ℓ\ell colours. We prove it for every ℓ\ell with no restriction on the lists, and we deduce their Conjecture~3 for all kk and Δ\Delta. The proof works with the complements of disjoint unions of paths with an odd number of vertices. The vertices in even positions of the paths form a clique in the complement, so equal lists of one colour fewer than the number of these vertices cannot be completed; we show by induction, using Hall's theorem and the theorem of Erd\H{o}s, Rubin and Taylor on complete multipartite graphs with parts of size at most two, that this is the only obstruction, and a separate lemma on minimal tight sets settles the extremal case of a single path. The cycle is then closed by carrying a colour shared by two consecutive vertices around the odd cycle in steps of two. The theorem also gives an infinite family of strongly chromatic-choosable graphs that are not strongly critical in the sense of Stiebitz, Tuza and Voigt. Every statement is proved by hand.

A mix of human-written and AI-generated textHuman understanding: some partschromatic-choosabilitycolouringcritical graphodd antiholeodd hole
Oct 17, 202611 pages
PDFView work

math.CO — Combinatorics

Measurable Independence Density Equals the Finite Independence-Ratio Infimum in the Euclidean Plane

Contributed by Ákos Dúcz

Let m1(R^2) be the supremum of upper densities of Lebesgue-measurable subsets of the plane containing no pair of points at distance one. We show, using the spectral rigidity theorem in OpenAI's recent proof that the plane is not five-colorable, that m1(R^2) = inf_G alpha(G)/|V(G)|, where G ranges over nonempty finite unit-distance graphs in the plane. The argument constructs an isometry-invariant law on independent subsets of the countable algebraic plane, projects the occupancy indicator onto the continuous spectral factor without changing its expectation, and extracts a measurable independent set with arbitrarily small density loss. As a consequence, if f(n) is the least independence number among unit-distance graphs on n vertices, then f(n)/n converges to m1(R^2). The proof is nonquantitative and uses the cited spectral rigidity result as a black box.

Primarily AI-generated textHuman understanding: some partsSpectral RigidityUnit-distance graphsindependence ratioinvariant random independent setsmeasurable sets
Oct 09, 20266 pages
PDFView work

math.CO — Combinatorics

A counterexample to ordering-independence for chromatic operators

Contributed by Darij Grinberg

We give a 1010-vertex counterexample to a conjecture of Pawlowski asserting that the characteristic polynomial of a chromatic operator associated with a forest is independent of the ordering of its edges. The two operators already have different traces of fifth powers.

Primarily AI-generated textHuman understanding: all partsGraph coloringSpecht modulessymmetric group algebra
Sep 28, 20265 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations