PaperlayerView exact revision on arXiv

Source-linked AI summary

The Problem Is the Problem: Towards Scalable Mathematical Discovery

Zeyu Zheng, Shengtong Zhang, Jeremy Avigad, Prasad Tetali, Sean Welleck

arXiv:2608.16977v1cs.AImath.CO

TL;DR

AI-assisted mathematics still leaves the choice of worthwhile problems largely to researchers, despite scarce reasoning and review resources. FAR searches literature in an expert-specified direction, attempts recovered problems, and recommends promising artifacts for review; in a combinatorics pilot, authors found correct proofs, counterexamples, and answers to open questions among reviewed outputs.

  • Problem

    Current AI-for-mathematics systems usually attempt researcher-supplied problems, leaving problem selection and dispersed literature-based discovery insufficiently supported.

  • Method

    FAR uses an expert-specified research direction to recover candidate problems from literature, attempt them, and recommend promising results for scarce expert review.

  • Results

    In a combinatorics pilot, FAR recovered 6,453 candidate statements, filtered 4,717 into an attemptable pool, and selected 77 artifacts for author-team review.

  • Takeaways & Limitations

    Author review found correct AI-assisted mathematical artifacts spanning proofs, counterexamples, and answers to open-ended questions.

  • Takeaways & Limitations

    The cascade failed to detect an existing record of an Erdős--Straus proof, which it therefore treated as a new result.

Abstract

from arXiv · show

AI systems are increasingly capable of contributing to mathematical research. In research practice, frontier-model reasoning is a limited resource, and expert mathematical review is even more sharply constrained. Allocating these scarce resources well is therefore central to making AI-assisted mathematical discovery efficient. In most current AI-for-math workflows, human effort is concentrated at the beginning and end, in selecting suitable research problems and later reviewing the resulting artifacts. These two stages are becoming bottlenecks for research-level mathematics. We address them by proposing a new human-AI discovery paradigm. The human input is no longer a single problem selected in advance, but a research direction in which the experts have interest and expertise. The system then searches a broad literature corpus for candidate problems in that direction. Inspired by search and recommender systems, we build Find, Attempt, and Recommend (FAR), a literature-to-review cascade that automates the search for suitable problems and focuses human attention on artifacts that have passed several stages of filtering. In a combinatorics pilot, the pipeline starts from 5,245 combinatorics papers, recovers 6,453 candidate conjectures or open problems, and filters them to 4,717 apparently well-posed and still-open conjectures. Subsequent reasoning and automated triage stages surface 598 potential resolutions and select 77 items for author-team review. Among them, we identify many interesting discoveries, including results on conjectures and questions of Davies--Jenssen--Perkins--Roberts, Erdős--Straus, Ikenmeyer--Pak--Panova, and Lund--Saraf--Wolf. These results demonstrate the effectiveness of this new mode of human-AI collaboration for mathematical discovery.

1 INTRODUCTION

The paper proposes FAR, a human–AI workflow that lets experts specify a research direction while AI systems find, attempt, and recommend mathematical problems for review. A combinatorics pilot demonstrates a literature-to-review funnel and studies effort allocation for scarce reasoning and expert-review resources.

  • 1 INTRODUCTION: FAR builds a problem pool from mathematical literature, attempts to resolve open conjectures, and recommends promising conjecture–resolution pairs for expert review.The workflow shifts expert input from selecting individual problems to specifying a research direction.
  • 1 INTRODUCTION: The paper frames scalable mathematical discovery as effort allocation over interesting problems, using frontier-model reasoning and expert review efficiently.The workflow treats both reasoning and mathematical review as scarce resources whose value depends on which conjectures receive them.
  • 1 INTRODUCTION: 4,717 apparently well-posed and still-open conjectures remain after FAR extracts 6,453 candidates from 2,742 combinatorics papers.The pipeline first identifies 5,245 combinatorics papers from 51,110 mathematics papers.
  • 1 INTRODUCTION: 598 potential resolutions emerge from a broad attempt run over all 4,717 conjectures, and 77 items are selected for internal author-team review.These stages form the pilot’s literature-to-review funnel.
  • 1 INTRODUCTION: Allocation strategies are derived for different objectives, and their optimal choices differ between maximizing successful artifacts and maximizing importance.The strategies are compared with a uniform baseline.
  • 1 INTRODUCTION: Author-reviewed outputs span proofs, counterexamples, and answers to open-ended questions from the combinatorics literature.The resulting write-ups are collected in Appendix C.

2 MOTIVATION AND RELATED WORK

Current AI-for-math systems mainly begin after a problem is specified, while mathematical research also requires finding worthwhile problems within a broader direction. The proposed approach shifts AI assistance to literature-based problem discovery, using retrieval, staged recommendation, and limited-attempt allocation to focus review.

  • Motivation and related work: AI-for-math systems largely address construction, algorithm search, or proof search after a mathematical objective has been specified, leaving problem selection comparatively underserved.Examples include FunSearch and AlphaEvolve (Novikov et al., 2025) and AlphaProof Nexus (Tsoukalas et al., 2026).
  • Our approach: The system starts from a mathematician-specified research direction, searches the literature for candidate problems, attempts them at scale, and returns a small set of artifacts for expert review.This moves AI assistance earlier than workflows that begin with a single selected problem.
  • Problem sources: Mathematical problems are dispersed through research literature rather than concentrated in comprehensive, primary infrastructure, limiting the coverage of selective resources such as the Open Problem Garden, AIM Problem Lists, and Formal Conjectures.A conjecture may appear in a numbered statement, question, or surrounding research context across the literature.
  • Search and recommendation: The pipeline treats problem discovery as candidate retrieval and applies recommendation-style cascades that progressively filter candidates by provenance, well-posedness, current status, and review value.This adapts search and recommender-system ideas to organize large-scale mathematical problem selection (Liu et al., 2022).
  • Related work: Unlike automated conjecturing, which creates new conjectures, the approach surfaces and attempts existing mathematical questions from the literature.Related work includes automated theory formation, the Ramanujan Machine, TxGraffiti, LeanConjecturer, STP, and Moonshine.
  • Effort allocation: Limited reasoning and review effort can be modeled as a bandit problem in which each conjecture is an arm and a single pull yields an assessed outcome such as no reliable result, a known resolution, or a candidate proof or counterexample.The experiments pull each arm once, corresponding to the initialization stage of the UCB algorithm (Bubeck & Cesa-Bianchi, 2012; Lattimore & Szepesvári, 2019).

3 METHOD

FAR is a literature-to-review cascade that takes a research direction and literature corpus, progressively narrowing open problems through increasingly costly stages. It allocates stronger automated reasoning and scarce expert review to the most promising conjecture-resolution pairs.

  • Pipeline: FAR progressively narrows a large literature collection through increasingly costly stages, directing later computation and limited expert attention toward fewer, higher-priority items.The cascade mirrors search and recommender systems, with expert review as the scarcest resource and mathematicians selecting which recommended artifacts to inspect.
  • Finding: FAR finds relevant papers, extracts unresolved mathematical statements, and checks their validity and open status to form an attemptable pool P.The corpus may be arXiv, a topic-specific collection, or another large-scale literature source; candidates are labeled open, solved, or invalid using later-work searches and status evidence.
  • Finding: The finding stage favors recall by using the cheapest model across the corpus and permissively extracting candidate conjectures, while later filtering removes spurious or non-concrete statements.It excludes nonspecific future work and statements resolved within their source papers, because overlooked statements cannot be recovered later.
  • Attempt: Each conjecture in P receives an attempt, pairing it with its source paper and the pipeline’s most capable model to produce an outcome in Y.Uniformly assigning one attempt per conjecture initializes the effort allocation, while the narrowed pool permits more resources per problem.
  • Recommend: The recommend stage filters outcomes in Y by correctness and publication significance, retaining only artifacts A that pass every judging agent and are substantial enough to publish.A fresh literature search also removes outcomes that are already known; expert review then checks the remaining artifacts and writes up those that hold.

4 A PILOT RUN IN COMBINATORICS

The combinatorics pilot applies FAR to a large literature corpus, narrowing thousands of extracted candidates to a smaller set of apparently open conjectures and reviewable resolutions. It also shows that model-estimated difficulty and importance scores support allocation of limited attempts, although the best strategy depends on the objective.

  • Pilot outcomes: 4,717 conjectures formed the attemptable pool, yielding 1,050 claimed resolutions, 598 that passed judging, and 77 graded publishable.The corpus began with 51,110 mathematics papers; labeling retained 5,245, extraction found 6,453 candidates, and checking retained 4,717 conjectures from 2,206 papers.
  • Pilot outcomes: All 15 artifacts selected for author review were mathematically correct, although one Erdős divisor-difference result had been settled shortly before the run.That prior resolution was not found by any search in the cascade.
  • Score validation: Difficulty and importance scores both correlated positively with their target outcomes, with Mann-Whitney p < 10−40 for difficulty and p = 0.008 for importance.The targets were the fraction of attempts without accepted resolutions and the publishable fraction of accepted resolutions, respectively; Figure 4 visualizes these relationships.
  • Score validation: The scores were strongly correlated with each other (Spearman rank correlation 0.83), but difficulty still separated accepted from unaccepted attempts among equally important conjectures.Over 60% of conjectures lay strictly above the score diagonal, while almost none lay strictly below.
  • Allocation strategies: Ranking by estimated publishability probability ˆp was best for artifact count, while importance-weighted ranking narrowly lost to ˆp and whole-pool rankings underperformed for the best-artifact objective.For the best-artifact objective, retaining only the most important conjectures and ranking them by ˆp worked best; at larger budgets, whole-pool rankings fell behind uniform random selection.

5 SELECTED REVIEWED RESULTS

Manual review found no mathematical errors in fifteen pilot artifacts. Three author- or domain-checked results appeared new: one proves a conjecture, one refutes a conjecture, and one answers an open-ended question.

  • Previously known or contextualized results: Other reviewed artifacts were mathematically correct but not novel: one established F(n; t)/n → 1/2, a result already recorded by Bloom (2026), while another linked a known finite-geometry construction to Lund et al. (2018)’s conjecture.The latter construction disproves the conjecture for every odd q, has density 1/2+o(1), and was verified exhaustively for q ≤13.
  • New results: Three checked results were new so far as the authors could determine: a proof of many-one GapP-completeness, a triangle-free graph counterexample, and a density-one result for binomial-coefficient divisibility.The results respectively prove a conjecture, refute one, and answer an open-ended question.
  • Many-one GapP-completeness for binary symmetric group characters: The artifact proves Ikenmeyer et al. (2024)’s conjecture by reducing a difference of exact-cover counts to one symmetric-group character value.It uses a two-row partition, whose character value is expressed as N_µ(s)−N_µ(s−1).
  • Maximum versus average independent set size in triangle-free graphs: The artifact refutes Davies et al. (2018)’s conjecture with C5 □K_m,m, where the ratio tends to 24/13 and a C13(1, 5) variant lowers it to 32/19.The product is triangle-free and (m + 2)-regular, with α = 4m and an exactly computable expected independent-set size.
  • Divisibility among binomial coefficients: The returned artifact shows d∗(n) = 1 for every fixed n ≥2, answering the Erdős & Straus (1977) divisibility question.Its construction uses Kummer’s theorem, Legendre’s formula, and the Chinese remainder theorem to produce the required density.

6 CONCLUSION · A PROMPT TEMPLATES AND OPERATIONAL DETAILS

FAR frames mathematical discovery as a literature-to-review cascade that recovers open problems, attempts resolutions, and routes promising artifacts to experts. Its operational prompts specify structured extraction, rigorous resolution attempts, literature-aware judging, and significance-based grading.

  • 6 CONCLUSION: 6 CONCLUSION: FAR recovered 6,453 candidate statements, checked 4,717 into an attemptable pool, and returned 77 artifacts graded substantial enough to publish.The supplied passage begins reporting that 15 of these artifacts were further singled out, but the sentence is truncated before completing that result.
  • A PROMPT TEMPLATES AND OPERATIONAL DETAILS: A PROMPT TEMPLATES AND OPERATIONAL DETAILS: The implementation releases prompts alongside schema validators and retry logic.
  • A.1 FINDING RELEVANT OPEN PROBLEMS: A.1 FINDING RELEVANT OPEN PROBLEMS: FAR first filters papers by research direction, then extracts explicit unresolved mathematical statements into structured conjecture records.The pilot direction was combinatorics; prompts require identifying whether papers belong to that direction and extracting labels, text, and sections for open conjectures.
  • A.1 FINDING RELEVANT OPEN PROBLEMS: A.1 FINDING RELEVANT OPEN PROBLEMS: Candidate status checks use current web information to classify problems as open, solved, or invalid and assign importance and difficulty scores.Solved candidates require credible resolving evidence, while invalid candidates are not concrete open problems in the source.
  • A.2 ATTEMPTING FOR CANDIDATE RESOLUTIONS: A.2 ATTEMPTING FOR CANDIDATE RESOLUTIONS: The prover reconstructs each formal statement, tests examples and counterexamples, repairs formulation defects, and produces a rigorous proof or disproof.It must distinguish KNOWN, NEW, FIX, and NONE outcomes and present reasoning in locally checkable form with verified theorem hypotheses.
  • A.3 JUDGING AND GRADING: A.3 JUDGING AND GRADING: Judges accept only complete, rigorous resolutions of the correct statement, while final quality control checks literature novelty and publishable significance.The final classifier assigns KNOWN, TYPE1, TYPE2, or TYPE3; only TYPE2 and TYPE3 artifacts proceed to expert review.
  • A.3 JUDGING AND GRADING: A.3 JUDGING AND GRADING: The significance rubric distinguishes minor unpublishable results, standalone-paper contributions, and major advances or well-known conjecture resolutions.These categories correspond to TYPE1, TYPE2, and TYPE3, respectively, with deliberately rough boundaries and conservative choices when uncertain.

B ANALYSIS DETAILS … C.2.2 THE AFFINE-PLANE COLORING

The appendix reports score-validity and allocation analyses, then details reviewed mathematical solutions, including a counterexample to an exactness conjecture for Paley graphs and a counterexample showing that not all uniform trees are n-good. The affine-plane coloring supplies the obstruction for the latter result.

  • B.1 SCORE VALIDITY; B.2 ALLOCATION CURVES: The appendix supports Section 4.3 with score-validity associations, Wilson intervals, and allocation-curve tables evaluated over random pool partitions.Figure 6 uses uniform bins of width 0.1; Tables 2–4 report objectives f1, f2, and f3.
  • C.1.1 INTRODUCTION; C.1.4 PROOF OF THE MAIN THEOREM: The Paley result is exact at q = 3125: N_min(3125) = 377, so G_3125 belongs to G(1, 2, 377) but not G(1, 2, 378).A finite-field computation gives 8N(b,c) = 3016 and N(b,c) = 377 for the extremal pair.
  • C.1.2 THE CHARACTER COUNT; C.1.3 TRACES OF ELLIPTIC CURVES; C.1.4 PROOF OF THE MAIN THEOREM: The Paley proof converts the adjacency count into a quadratic-character sum whose obstruction is an elliptic curve y^2 = x(x − b)(x − c), then excludes equality using elliptic-curve trace classification.Hasse’s bound permits only a possible trace 110 in the equality case, while Waterhouse’s consequence forbids a nonzero trace divisible by 5 over F_5^5.
  • C.2 A 4-UNIFORM TREE THAT IS NOT 5-GOOD; C.2.1 INTRODUCTION: The smallest nontrivial 4-uniform tree, the two-edge tree T on seven vertices, is not 5-good, refuting the conjecture that every r-uniform tree is n-good.For this case the lower-bound expression is 8, but the Ramsey number is 9; the broader 3-uniform case remains open.
  • C.2.1 INTRODUCTION: The counterexample sits in the unresolved divisibility window: at (r, m, n) = (4, 7, 5), the possible Ramsey values are {8, 9}, and the theorem places the value at 9.The corresponding window has width one step, whereas the analogous (3, 5, 4) case has value 6.
  • C.2.2 THE AFFINE-PLANE COLORING: The lower bound is witnessed by coloring the fourteen affine planes of F_3^2 red and all other 4-subsets blue.Affine planes meet in 0 or 2 points, never in the single point required by the two edges of T, while every five points contain an affine plane.
  • C.2.2 THE AFFINE-PLANE COLORING: Affine planes are exactly the fourteen four-element cosets in F_3^2, equivalently the 4-subsets whose vector sum is zero.This characterization establishes the red-edge family used in the obstruction coloring.

C.2.3 THE LOWER BOUND

The constructed red/blue coloring avoids both forbidden configurations: red edges never meet in exactly one vertex, and every 5-subset contains a red 4-subset, excluding a blue K(4).

  • THE LOWER BOUND: Any two distinct red edges meet in 0 or 2 vertices, so the coloring contains no red copy of T.A red copy of T would require two red edges meeting in exactly one vertex.
  • THE LOWER BOUND: Every 5-subset contains a red 4-subset, so the coloring contains no blue K(4).A blue K(4) would require a 5-set whose every 4-subset is blue.
  • THE LOWER BOUND: The coloring avoids both forbidden configurations, providing the lower-bound construction.Lemmas C.2.4 and C.2.5 establish the two exclusions together.

C.2.4 PROOF OF THE MAIN THEOREM · C.3 MAXIMUM VERSUS AVERAGE INDEPENDENT SET SIZE IN TRIANGLE-FREE GRAPHS

The proof establishes R(T, K(4)_5; 4) = 9 and shows the tree T is neither 5-good nor 6-good. Separately, C_5 □ K_m,m disproves a conjectured near-2 ratio between maximum and average independent-set sizes in triangle-free graphs, attaining 24/13.

  • C.2.4 PROOF OF THE MAIN THEOREM: The proof’s remaining input is Loh’s (2009, Theorem 1) hypertree embedding theorem, which removes dependence on the uniformity r.It states that every r-uniform hypergraph with weak chromatic number greater than k contains every r-uniform tree with k edges.
  • C.2.4 PROOF OF THE MAIN THEOREM: The upper bound follows because either the red hypergraph has weak chromatic number greater than 2 and contains T, or a two-color weak coloring yields a blue K(4)_5.A color class has at least 5 vertices, and all its 4-subsets are blue.
  • C.2.4 PROOF OF THE MAIN THEOREM: R(T, K(4)_5; 4) = 9, completing the main theorem’s exact Ramsey-value determination.The proof combines the upper bound with equation 8.
  • C.2.4 PROOF OF THE MAIN THEOREM: The calculation gives χw(K(4)_5) = 2 and s(K(4)_5) = 2, so the relevant bound equals 8 rather than 9.The only two-class partition of a 5-set has sizes 3 + 2.
  • C.2.4 PROOF OF THE MAIN THEOREM: Because 9 ≠ 8, T is not 5-good; by Budden & Clifton (2022, Theorem 10), it is also not 6-good.Theorem C.2.1 therefore settles a previously open value noted by Budden & Penland (2017).
  • C.3 MAXIMUM VERSUS AVERAGE INDEPENDENT SET SIZE IN TRIANGLE-FREE GRAPHS: The Cartesian products C5 □ K_m,m are triangle-free and (m + 2)-regular, yet their maximum-to-average independent-set ratio tends to 24/13 = 1.846 . . . .This ratio is bounded away from the conjectured factor 2 − o_d(1) for large minimum degree d.
  • C.3 MAXIMUM VERSUS AVERAGE INDEPENDENT SET SIZE IN TRIANGLE-FREE GRAPHS: Thus, Davies et al. (2018)’s conjecture that large minimum degree forces a factor 2 − o_d(1) is false.The construction supplies a counterexample with a limiting ratio of 24/13.

C.3.1 INTRODUCTION · C.3.2 THE CONSTRUCTION · C.3.3 EXACT COUNTING BY M ¨OBIUS INVERSION

The paper constructs the triangle-free graph family G_m = C_5 □ K_{m,m}, exactly counts its independent sets via Möbius inversion, and uses the resulting ratio α(G_m)/α_{G_m}(1) → 24/13 to refute Davies et al. (2018, Conjecture 2) and its minimum-degree extension.

  • C.3.1 INTRODUCTION: 24/13 is the limiting ratio α(G_m)/α_{G_m}(1) for triangle-free, (m + 2)-regular graphs G_m on 10m vertices, disproving Davies et al. (2018, Conjecture 2) and its minimum-degree extension.The construction has α(G_m) = 4m and minimum degree m + 2 → ∞, while 24/13 = 1.846... < 2.
  • C.3.1 INTRODUCTION: The examples do not refute Davies et al. (2018, Conjecture 1), the first assertion of Conjecture 4, or the general-fugacity Conjecture 3, and they lie outside the sparse-independence regime relevant to R(3, k).Their independence ratio is 2/5, while the general bound already forces a ratio of at least 7/5 in this range.
  • C.3.2 THE CONSTRUCTION: G_m = C_5 □ K_{m,m} is triangle-free and (m + 2)-regular on 10m vertices because Cartesian-product degrees add and the product of triangle-free graphs is triangle-free.The two factors are C_5 and K_{m,m}; each fiber over K_{m,m} induces a copy of C_5.
  • C.3.2 THE CONSTRUCTION: Independent sets of G_m correspond to fiberwise independent sets of C_5 whose unions on the two sides of K_{m,m} are disjoint.The matching between adjacent fibers preserves the C_5 coordinate, imposing disjointness between the selected sets on opposite sides.
  • C.3.2 THE CONSTRUCTION: The construction gives α(G_m) = 4m: every fiber contributes at most two vertices, and opposite sides can realize disjoint independent pairs of C_5.Choosing {0, 2} on every fiber over L and {1, 3} over R attains 4m.
  • C.3.3 EXACT COUNTING BY M ¨OBIUS INVERSION: Möbius inversion on the Boolean lattice 2^Z5 converts containment counts into generating functions for m-tuples whose unions are attained exactly.This removes the overcounting that occurs when a single independent set is included for every pair of supersets containing its two side-unions.
  • C.3.3 EXACT COUNTING BY M ¨OBIUS INVERSION: Classifying independent sets by their ordered pair of side-unions yields an exact identity for the independence polynomial as a signed sum indexed by disjoint pairs (X, Y).Substitution collapses the expression to explicit signed terms of the form (F_X F_Y)^m.

C.3.4 THE DOMINANT PAIRS … C.7.3 THE LAW OF A UNIFORM MATCHING

The paper develops several combinatorial, number-theoretic, complexity-theoretic, and probabilistic results, including sharp asymptotic bounds, density-one theorems, GapP-completeness, and a separation between matching variance and residual matching number.

  • C.3.4 THE DOMINANT PAIRS: The dominant-pair analysis shows max f(X)f(Y)=24, attained by exactly 10 ordered complementary pairs, while every other disjoint pair has value at most 16; consequently the ratio tends to 24/13.For each dominant pair, P(y)=(1+y)^3(1+2y), and the constant 13/6 has a per-vertex interpretation from the two induced subgraphs.
  • C.3.4 THE DOMINANT PAIRS: The C5 analysis also extends to other triangle-free graphs and clique-fiber constructions, yielding limiting ratios 32/19 for C13(1,5), 2 for q=2, and 12/7 for q=3, with disjoint unions preserving the ratio.For fixed minimum degree d=m+2, disjoint unions realize the same ratio on arbitrarily many vertices.
  • C.5 DIVISIBILITY AMONG BINOMIAL COEFFICIENTS / C.5.1 INTRODUCTION / C.5.2 A BINOMIAL COEFFICIENT FREE OF SMALL PRIMES / C.5.3 A CONGRUENCE FORCING THE DIVISIBILITY / C.5.4 THE DENSITY OF THE CONGRUENCE SET: For every fixed n≥2, the set of large m admitting an admissible k with A(n,k)|A(m,k) has natural density d*(n)=1.The construction uses a single k for each prime cutoff B, chosen so the relevant binomial coefficient has no prime factor below B; the resulting congruence set has density tending to 1.
  • C.5.1 INTRODUCTION: The density-one theorem leaves open whether all sufficiently large m work and gives no information about the least admissible k for a given m.To obtain density 1−ε, the proof uses one k=k_B of size e^O(n(B)) and only covers m≥n+k_B.
  • C.6 MANY-ONE GapP-COMPLETENESS FOR BINARY SYMMETRIC GROUP CHARACTERS / C.6.1 INTRODUCTION / C.6.2 CHARACTERS OF TWO-ROW SHAPE / C.6.3 A DIFFERENCE OF TWO EXACT COVER COUNTS / C.6.4 THE DIGIT GADGET / C.6.5 MEMBERSHIP IN GapP / C.6.6 PROOF OF THE MAIN THEOREM: COMPUTECHARBINARY is GapP-complete under polynomial-time many-one reductions, even when the output partition λ has at most two parts.The reduction encodes an arbitrary GapP function as the difference of two subset-sum counts at consecutive targets, realized through a base-Q digit gadget for exact covers; membership follows because character values are differences of #P counts.
  • C.7 MATCHING VARIANCE VERSUS THE RESIDUAL MATCHING NUMBER / C.7.1 INTRODUCTION / C.7.2 THE CONSTRUCTION / In particular: The matching construction breaks the implication σ^2=O(λ): with a_n=⌊n^1/4⌋, the graphs H_n have λ(H_n)→∞, σ^2(H_n)→∞, and σ^2(H_n)≥c·(53/2)λ(H_n)^3/2.Thus no absolute C satisfies σ^2(G)≤Cλ(G), and no bound σ^2=O(λ^β) is possible for λ=Ω(1) unless β≥3/2.
  • C.7.3 THE LAW OF A UNIFORM MATCHING: The construction’s mechanism is that the leaf count divides the residual matching number but not the matching variance, while the uniform-matching analysis begins with a parity-constrained law for the number of clique vertices missed.For a uniform matching, S≡n (mod 2), and the matching decomposes into a clique matching plus choices of uncovered leaves.

C.7.4 THE DISTRIBUTION OF THE FREE SET · C.7.5 A VARIANCE LOWER BOUND

Under the stated assumptions, the free-set size S has a unimodal, non-heavy-tailed distribution concentrated on the scale L, yielding matching-order bounds on E[S] and λ(G_n,a), followed by a variance lower bound. The variance result follows by converting the largest-atom bound into a general lower bound for integer-valued random variables.

  • C.7.4 THE DISTRIBUTION OF THE FREE SET: The weights (w_s) are strictly log-concave, and hence unimodal, along the admissible parity progression.The proof fixes a mode s_0 and uses the monotonicity of ρ to control the distribution on either side of that mode.
  • C.7.4 THE DISTRIBUTION OF THE FREE SET: The mode s_0 is bounded above by 2L + 2, constraining the distribution’s peak to the relevant L-scale.For admissible s ≥ 2L, successive weights decrease; maximality then rules out a mode above 2L + 2.
  • C.7.4 THE DISTRIBUTION OF THE FREE SET: E[S] ≤ 5L and λ(G_n,a) ≤ 5√n.The expectation bound is obtained by geometrically controlling weights beyond a threshold near 2L, then using λ(G_n,a)=E[S]/a.
  • C.7.4 THE DISTRIBUTION OF THE FREE SET: The distribution of S has no heavy atom, which forces Var[S] to be large and excludes bounded λ.This lemma is identified as the technical heart of the distributional argument, linking atom control to both variance and the scale of λ.
  • C.7.4 THE DISTRIBUTION OF THE FREE SET: E[S] ≥ L/4 and λ(G_n,a) ≥ √n/4.The lower bound comes from showing substantial probability remains above an admissible threshold near L/2.
  • C.7.5 A VARIANCE LOWER BOUND: For any integer-valued X with largest atom θ, an elementary interval-counting argument yields a variance lower bound in terms of θ.An interval of radius u contains at most 2u + 1 integers, allowing tail probabilities to be integrated around the mean.
  • C.7.5 A VARIANCE LOWER BOUND: Var[S] ≥ L/8000.The corollary applies the largest-atom estimate for S to the general variance lemma under equation 21 and sufficiently large n.

C.7.6 PROOF OF THE MAIN THEOREM … C.8.3 PROOF OF THE MAIN THEOREM

The paper proves a growing separation between σ2(Gn,a) and λ(Gn,a), yielding graphs with unbounded ratio, and establishes exe(G1,n)=Θ(n log n) for a five-vertex ordered graph.

  • C.7.6 PROOF OF THE MAIN THEOREM: σ2(Gn,a)/λ(Gn,a) ≥ 2 · 10^-7a, proving the main theorem’s quantitative separation.This follows by dividing the bounds on σ2(Gn,a) and λ(Gn,a).
  • C.7.6 PROOF OF THE MAIN THEOREM: Choosing a = an = ⌊n^1/4⌋ gives λ(Hn) ≥ √n/4 → ∞ and σ2(Hn)/λ(Hn) = Ω(n^1/4), contradicting any universal bound σ2(G) ≤ Cλ(G).The contradiction follows because such a bound would force an ≤ 5C/c for every n.
  • C.8 AN ORDERED HYPERGRAPH EXTREMAL FUNCTION OF ORDER n log n: For the five-vertex ordered graph G1, the paper proves exe(G1,n)=Θ(n log n), matching the order of the corresponding ordered graph extremal function.This resolves Klazar’s question up to implied constants.
  • C.8.1 INTRODUCTION: Ordered Berge-type containment uses increasing vertex injections and distinct host hyperedges, while reducing to ordinary ordered subgraph containment for graphs.The extremal functions satisfy gex(F,n) ≤ exe(F,n) ≤ exi(F,n).
  • C.8.3 PROOF OF THE MAIN THEOREM: The proof controls each G1-free simple ordered hypergraph through an auxiliary G1-free ordered graph formed by recording one previously unrecorded vertex pair per processed hyperedge.A copy of G1 in the auxiliary graph would pull back to four distinct hyperedges forming a forbidden copy in the hypergraph.
  • C.8.2 CLIQUES IN A G1-FREE ORDERED GRAPH: Every edge of a G1-free ordered graph has at most two common neighbors to its right, so the graph contains at most 4e(B) cliques of size at least two.A clique is determined by its two smallest vertices and a subset of at most two common neighbors.
  • C.8.3 PROOF OF THE MAIN THEOREM: Unassigned hyperedges are distinct cliques of the auxiliary graph, so at most 4e(B) exist; together with singleton and assigned edges, this yields the theorem’s upper bound.The lower bound is immediate because ordered graphs form a subclass of ordered hypergraphs.

C.9.1 INTRODUCTION · C.9.2 ELIMINATING THE SUBDIVISION VERTICES · C.9.3 COMPARISON IN THE LOEWNER ORDER

The paper proves that the number of adjacency eigenvalues below −2 in any partially stretched graph is eventually constant, identifying it as the negative inertia of a limiting n × n matrix. The proof eliminates subdivision vertices exactly and compares the resulting matrices in the Loewner order, with parity determining the Laplacian or signless-Laplacian perturbation.

  • C.9.1 INTRODUCTION: The −2 threshold is structurally natural because deleting vertices of degree at least 3 leaves paths and cycles whose eigenvalues lie in [−2, 2].Interlacing therefore bounds the numbers of eigenvalues above 2 and below −2 by |Q| uniformly in t.
  • C.9.1 INTRODUCTION: Parity can cause genuine finite-t oscillations because subdivision changes the lengths of cycles through stretched edges.One example has 1, 0, and 1 eigenvalues below −2 across successive subdivisions before the count stabilizes.
  • C.9.1 INTRODUCTION: Theorem C.9.1 proves that m_Gt(−∞, −2) eventually equals n−(K∞) for every finite graph G and stretched-edge set S.The threshold is effective; if r = n−(K∞) ≥ 1, equality holds for t ≥ 2 with t > 2∆(G)/γ, where γ is the smallest absolute value of a negative eigenvalue of K∞.
  • C.9.1 INTRODUCTION: When every edge is stretched, the eventual count is |Q|, where Q consists of vertices of G with degree at least 3.This recovers the value predicted by Kumar et al. (2025) and makes the negative-side interlacing bound tight for sufficiently large t.
  • C.9.2 ELIMINATING THE SUBDIVISION VERTICES: Eliminating the internal subdivision vertices reduces A(G_t) + 2I, without changing negative inertia, to an n × n Schur-complement matrix K_t.The internal blocks are positive definite, so Haynsworth’s inertia additivity formula applies; each stretched edge contributes diagonal terms (t − 1)/t and an endpoint coupling (−1)^t/t.
  • C.9.2 ELIMINATING THE SUBDIVISION VERTICES: The special case t = 2 and S = E(G) links the count below −2 to signless-Laplacian eigenvalues of G exceeding 4.The nonzero adjacency eigenvalues of the subdivision graph are ±√q, where q is a nonzero eigenvalue of D + A(G), and −√q < −2 exactly when q > 4.
  • C.9.3 COMPARISON IN THE LOEWNER ORDER: For every t ≥ 2, K_t ⪰ K∞ and ||K_t − K∞|| ≤ 2∆(G)/t in spectral norm.The difference is positive semidefinite because it is scaled from the Laplacian of (V(G), S) for even t or the signless Laplacian for odd t.

C.9.4 PROOF OF THE MAIN THEOREM … C.13.4 EVERY k-KERNEL IS LARGE

The paper proves a spectral stabilization theorem, refutes two finite-geometric conjectures, constructs high-girth signed graphs with extremal signed circular chromatic number, disproves a counting conjecture for critical triple systems, and establishes sharp lower bounds for k-kernels in strongly connected digraphs.

  • C.9.4 PROOF OF THE MAIN THEOREM: For all t > max{2, 2∆(G)/γ}, the number of negative eigenvalues satisfies n−(Kt) = n−(K∞), yielding mGt(−∞, −2) = n−(K∞).The lower bound uses the spectral gap γ and Weyl’s perturbation inequality, while the upper bound follows from eigenvalue monotonicity.
  • C.10 SMALL UNIONS OF LINES CLOSING A ROUTE TO THE NIKODYM BOUND: For every odd prime power q, the half-tangent family has q2(q + 1)/2 lines, at most q + 1 lines in any plane, and union density 1/2 + o(1), refuting both Lund et al. (2018) conjectures.The construction selects tangent directions using a quadratic character; its union has exactly q2(q + 1)/2 points, so the conjectured near-full coverage fails.
  • C.10.1 INTRODUCTION / C.10.2 THE HALF-TANGENT FAMILY / C.10.3 LINES CONTAINED IN A PLANE / C.10.4 THE UNION: The half-tangent construction uses the anisotropic form Q(x, y) = x2 −νy2: exactly (q + 1)/2 square directions produce q2(q + 1)/2 tangent lines, each meeting the paraboloid only at its tangency point.A plane contains at most q + 1 selected lines because its intersection with the paraboloid has at most q + 1 points, while the tangent-plane case is handled separately.
  • C.11.2 STATEMENT AND SMALL CASES / C.11.3 NEUTRAL COLOR PAIRS / C.11.4 THE RANDOM CONSTRUCTION: For every k ≥2 and girth g, a probabilistic construction gives a finite simple graph with χ(G) = k, girth at least g, and χs_c(G) = 2k.The proof combines a blocking-pair property for colors below ratio 2k with Erdős deletion, producing a k-partite graph whose surviving edges exclude all such colorings.
  • C.12 COUNTING 4-CRITICAL LINEAR TRIPLE SYSTEMS / C.12.1 INTRODUCTION / C.12.2 THE CONSTRUCTION / C.12.3 RECOVERING THE EDGE COLORING: For infinitely many n, there are at least exp(cn2 log n) pairwise nonisomorphic 4-critical linear triple systems on n vertices, disproving the R¨odl–Siggers conjecture for (k, r, l) = (4, 3, 2).A dense 4-critical graph is lifted through a recoverable proper edge coloring; each resulting minimal non-3-colorable subhypergraph is 4-critical and the encoding is injective.
  • C.13 STRONGLY CONNECTED DIGRAPHS WITH NO SMALL k-KERNEL / C.13.1 INTRODUCTION / C.13.2 THE CONSTRUCTION / C.13.3 A SMALL k-KERNEL / C.13.4 EVERY k-KERNEL IS LARGE: For every k ≥2 and m ≥1, a strongly connected digraph on mk + k + 2 vertices has smallest k-kernel of size exactly m + 1.The construction attaches a common return tail to m directed arms leaving a hub; the set {y}∪{ai,k} is a k-kernel, and every k-kernel has at least m + 1 vertices.
  • C.13.1 INTRODUCTION: The k-kernel construction implies κk(G) > |V(G)|/(k + 1) + c for every constant c, while placing the asymptotic coefficient between 1/k and 1/(k −1).For k = 3, the example with m = 50 has κ3(G3,50) = 51 on 155 vertices, versus 155/4 = 38.75.

C.13.5 PROOF OF THE MAIN THEOREM … C.14.3 GLUING THE LOCAL IDENTITIES OVER A HYPERTREE

The sections prove an unbounded connectivity construction for strongly connected digraphs and establish F-positivity of chromatic symmetric functions for all hypertrees. The hypertree proof uses a nonnegative local coloring decomposition and glues its terms into (P, ω)-partition enumerators.

  • C.13.5 PROOF OF THE MAIN THEOREM: For fixed k ≥ 2, the constructed digraph Gk,m is strongly connected, has mk + k + 2 vertices, and satisfies κk(Gk,m) = m + 1.Its connectivity-to-size parameter tends to infinity as m → ∞, since (m − 1)/(k + 1) can exceed any prescribed c.
  • C.14 F -POSITIVITY OF CHROMATIC SYMMETRIC FUNCTIONS OF HYPERTREES: The paper proves Taylor’s conjecture that the chromatic symmetric function XH of every hypertree H is F-positive, without requiring hyperedges to have prime size.Taylor (2015) established the prime-size case and conjectured that primality was unnecessary; the new proof removes that hypothesis.
  • C.14.1 INTRODUCTION: The introduction frames the result by contrasting universal graph F-positivity with hypergraph counterexamples and states that the theorem expresses XH as a sum of n! fundamental quasisymmetric functions counted with multiplicity.The proof’s central idea is to decompose the nonconstant colorings of each hyperedge into weakly increasing orders with prescribed strict steps.
  • C.14.2 A WEIGHTED LOCAL DECOMPOSITION FOR ONE HYPEREDGE: For one hyperedge, the weighted local identity represents the indicator of nonconstant colorings as a nonnegative combination of conditions indexed by all linear orders and nonempty strict-step sets.The weights are nonnegative because descent-set counts differ from ±1 with the required parity, while constant colorings contribute zero and every nonconstant coloring contributes one in total.
  • C.14.3 GLUING THE LOCAL IDENTITIES OVER A HYPERTREE: The local identity is pointwise in the coloring, which permits multiplying it over all hyperedges and summing over collections Ω of local orders and strict-step sets.For each hyperedge, the selected coloring conditions impose weak inequalities along its order and strict inequalities at the chosen steps.
  • C.14.3 GLUING THE LOCAL IDENTITIES OVER A HYPERTREE: The hypertree hypothesis makes the graph TΩ formed by threading each hyperedge along its chosen order into a tree, allowing its weak and strict edges to define a poset PΩ and labeling ωΩ.The incidence graph is a tree, distinct hyperedges meet in at most one vertex, and TΩ has |V| − 1 edges.
  • C.14.3 GLUING THE LOCAL IDENTITIES OVER A HYPERTREE: Each generating function KΩ equals Γ(PΩ, ωΩ), so it is a nonnegative integral combination of fundamental quasisymmetric functions, and summing these terms proves F-positivity.The equivalence follows because the (PΩ, ωΩ)-partition inequalities exactly recover the weak and strict conditions imposed on every hyperedge.

C.14.4 PROOF OF THE MAIN THEOREM … C.15.3 THE UPPER BOUND

The paper proves nonnegative-integral coefficients in the quasisymmetric decomposition and settles the growth of Fano subsquares in Latin squares as Θ(n^4), using an explicit affine construction and a matching upper bound.

  • C.14.4 PROOF OF THE MAIN THEOREM: Theorem C.14.1 proves that every coefficient a_S is a nonnegative integer.Equation 37 first gives nonnegative rational coefficients, while a coloring interpretation shows each coefficient is integral.
  • C.15 QUARTICALLY MANY FANO SUBSQUARES IN LATIN SQUARES: For every n ≥56, a Latin square of order n has more than (n/28)^4 subsquares isotopic to the Fano square S7, while an n^4 upper bound also holds.The lower bound is obtained by an affine lift, and the upper bound is proved by encoding each subsquare with three rows and one column.
  • C.15.1 INTRODUCTION: The result answers Wanless’s question affirmatively for p = 7, resolving whether Fano subsquares can occur more than cubically often.For p = 7, the relevant subsquares are precisely multiplication tables of the unique Steiner quasigroup of order 7.
  • C.15.1 INTRODUCTION: Consequently, the extremal number of order-7 subsquares satisfies ζ(n, 7) = Θ(n^4).The construction’s lower bound combined with Browning et al. (2015)’s quartic upper bound settles the order of growth.
  • C.15.2 THE CONSTRUCTION: For a power of two q ≥4, the construction defines a Latin square L_q of order 7q using addition off the diagonal and an affine rule λu + (1 + λ)v on the diagonal.Here λ ∈ F_q \ {0, 1}, and the construction exploits the near-F_2-linearity of the Fano square.
  • C.15.2 THE CONSTRUCTION: Each F_2-linear map ϕ: V → F_q and r ∈ F_q yields a distinct subsquare isotopic to S7, producing q^4 such subsquares.The row, column, and symbol sets are translated graphs determined by (ϕ, r), and distinct pairs give distinct row sets.
  • C.15.2 THE CONSTRUCTION: The lower bound extends from orders 7q to every n ≥56 by embedding L_q into a Latin square of order n, giving ζ*(n, S7) > (n/28)^4.Choose q as the largest power of two with 14q ≤ n, then use Evans’ embedding theorem.
  • C.15.3 THE UPPER BOUND: The upper bound follows because four recorded vertices—three rows and one column—generate all twenty-one vertices of any S7 subsquare, so at most n^4 subsquares exist.The generating rule is that two vertices in different parts determine the third vertex of their Latin-square triple.

C.15.4 PROOF OF THE MAIN THEOREM

The main theorem establishes quartic bounds for ζ∗(n, S7), with a stronger lower bound along n = 7q when q is a power of two. It implies ζ(n, 7) = Θ(n4), although the correct constant remains undetermined.

  • Proof of the main theorem: For every n ≥56, (n/28)4 < ζ∗(n, S7) ≤ n4.These bounds are provided by Corollaries C.15.6 and C.15.9.
  • Proof of the main theorem: Along n = 7q with q a power of two, the stronger lower bound ζ∗(n, S7) ≥ (n/7)4 holds.
  • Proof of the main theorem: The correct constant remains undetermined.
  • Proof of the main theorem: Because every subsquare isotopic to S7 has order 7, the theorem yields ζ(n, 7) = Ω(n4), while Browning et al. (2015, Theorem 8) gives ζ(n, 7) = O(n4).Together, these bounds establish ζ(n, 7) = Θ(n4).
Loading 2608.16977v1…