Skip to content
Cyborg Mathematics

Field

Graph theory and Erdős problems

A graph is a set of dots, called vertices, joined by lines. This group holds the exhaustive check of an Erdős conjecture on trees, the links I added to teorth/erdosproblems, the GitHub repository of Erdős problem data that Terence Tao maintains, and counts of dependency charts and network shapes.

4 results · 2 articles

Results

Numbered by their place in the strongest-first list

  1. 01

    An Erdős conjecture, open at the time, checked on every tree three sizes past the earlier limit

    A tree here is a set of dots, called vertices, joined by lines, all in one piece and with no loops. Erdős problem 993, a conjecture of Alavi, Malde, Schwenk and Erdős, says that in every tree the number of ways to pick k vertices with no two joined rises and then falls as k grows. I extended the computer check from every tree with up to ▲ vertices to every tree with up to . That is more trees, about ▲ times as many as all the smaller sizes together, and none broke the conjecture. I posted the check on the problem’s forum in August 2026. Two AI-assisted proofs were listed there in September, and in October a Lean version of the one covering every forest was accepted by both proof checkers of Palomar, a public registry of computer-checked proofs. Neither paper has been refereed, and teorth/erdosproblems, the community database of Erdős problems on GitHub, still records the problem as open. If that proof holds, my check is an independent computation that agrees with it on every tree up to vertices.

    Checked outside this site

    • Public recordPosted, dated, on the problem’s public forum on erdosproblems.com, Thomas Bloom’s site, . the forum thread
    • ArchiveCode and counts archived, . Zenodo DOI
    • MergedTerence Tao, who maintains the teorth/erdosproblems repository of problem data on GitHub, merged my pull request adding the problem’s OEIS tree-count link; a merge records the link and is not an endorsement of the check, . PR #375
    Graphs and Erdős
  2. 02Preprint, not refereed

    My OEIS counts of dependency charts, and the conjecture from them that Roberto Blanco Gómez proved

    A dependency chart (a labeled DAG) is a set of tasks in which some tasks wait on others and nothing waits on itself, even indirectly. I counted the charts in which each task waits on at most two others, up to tasks, and at most three, up to . These were the first OEIS entries for these counts, and the only earlier table, from 2017, stopped at . I listed a pattern in their remainders as a conjecture in OEIS A397711, and in October 2026 Roberto Blanco Gómez proved it in a preprint posted on Zenodo, not yet refereed.

    Checked outside this site

    • PreprintRoberto Blanco Gómez’s proof, not yet refereed by a journal, . Zenodo preprint
    • OEIS editorSean A. Irvine approved his note of the proof on my entry, . OEIS A397711
    • OEIS editorSean A. Irvine approved the entry itself, . OEIS A397711
    SequencesGraphs and Erdős
  3. 05

    A published upper bound on the domination number of the twelfth Fibonacci cube, improved and now stated in the OEIS

    A dominating set in a network is a set of points that every point is in or next to, and the domination number is the size of the smallest one. For the twelfth Fibonacci cube, a network of points, the domination number was known to lie between and (Azarija, Klavžar, Rho and Sim, 2018). I found a dominating set of size , checked by three separate programs, so it is at most . A month-long solver run that tried to settle the lower end stopped without an answer, and I published it as a documented attempt.

    Checked outside this site

    • OEIS editorMichael De Vlieger approved the comment and the attached dominating set, . OEIS A291295
    • ArchiveThe set, its checker and the solver run archived, . Zenodo DOI
    SequencesGraphs and Erdős

Articles

Notes on the numbers marked ▲

  • Largest tree size, in vertices, at which every tree had been checked before my work: 29. Earlier checks reached this size: the forum user JakeMallen reported it on the problem's forum in January 2026, and Brett Reynolds posted code and a preprint in March 2026. My check starts where theirs ended.
  • How many times as many trees the three new sizes hold as all smaller sizes together: 19. Rounded from 18.999. This compares the three new sizes with all the trees up to 29 vertices together. The 32-vertex size alone has about 20 times as many trees as the 29-vertex size.