Pith. sign in

REVIEW 7 cited by

Constructions in combinatorics via neural networks

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2104.14516 v1 pith:ZAYJTA7W submitted 2021-04-29 math.CO cs.LG

Adam Zsolt Wagner This is my paper · ORCID
classification math.COcs.LG
keywords combinatoricsconjecturesconstructionsseveraladjacencyalgorithmamongstavoiding
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We demonstrate how by using a reinforcement learning algorithm, the deep cross-entropy method, one can find explicit constructions and counterexamples to several open conjectures in extremal combinatorics and graph theory. Amongst the conjectures we refute are a question of Brualdi and Cao about maximizing permanents of pattern avoiding matrices, and several problems related to the adjacency and distance eigenvalues of graphs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 7 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Tight lower bound for the spectral radius of connected graphs with given matching number

    math.CO 2026-07 conditional novelty 7.0 of 10

    For connected graphs with n vertices and matching number k, the spectral radius is always at least √((n+2k−3)/k), with equality graphs characterized when k divides n−3.

  2. Advancing Geometry with AI: Multi-agent Generation of Polytopes

    math.CO 2025-01 conditional novelty 7.0 of 10

    An AI-guided search produced a 24-vertex width-6 prismatoid, giving a 19-dimensional non-Hirsch polytope, the smallest known, plus new bounds for monotone paths and neighbourly polytopes.

  3. Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?

    cs.LG 2025-01 conditional novelty 6.0 of 10

    A neural network relaxation of geometric coloring constraints produced new plane colorings, including an almost 5-coloring covering all but 3.74% of the plane, improving known bounds for Hadwiger-Nelson variants.

  4. Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems

    cs.AI 2025-05 conditional novelty 5.0 of 10

    LLM-generated search heuristics run through the CPro1 protocol with the reasoning model o3-mini-high produced verified constructions resolving open instances in 7 Handbook design families and newer problems.

  5. LLM Framework for Discovering Major Mathematical Conjectures: AI's Quest for the Next Riemann Hypothesis

    cs.AI 2026-04 reject novelty 4.0 of 10

    The paper's claim of pipeline-validated 'major conjecture' discovery is unsupported: the Lean statements are uninterpreted placeholders and the quality scores are self-assigned by the generating model.

  6. Reinforcement learning for graph theory, Parallelizing Wagner's approach

    math.CO 2025-09 conditional novelty 4.0 of 10

    A parallelized RL search over graphs produces three new counterexamples to conjectured Laplacian spectral radius bounds, alongside a speedup claim that is only weakly supported.

  7. Computer-assisted graph theory: a survey

    math.CO 2025-08 accept novelty 4.0 of 10

    Computer-assisted graph theory is surveyed, and two small computational results are added: i(5) <= 8/28 and non-planarity of the sequence 73517.

Pith tools