The Problem Is the Problem: Towards Scalable Mathematical Discovery

• Most current AI-for-math systems use a problem-level interface that attempts and checks a researcher-supplied goal, leaving the choice of which problems merit attempts outside the workflow.The paper formulates discovery as effort allocation over a pool of interesting problems to use model reasoning and expert review efficiently.Source: §1 · pp. 1–2
• FAR takes a broad mathematical topic, finds relevant open conjectures in a large literature corpus, attempts proofs or disproofs, and recommends promising conjecture-resolution pairs for expert review.The workflow replaces supplying a single problem in advance with experts specifying a research direction.Source: §1 · pp. 1–2
• 15 manually checked artifacts included counterexamples to Davies–Jenssen–Perkins–Roberts and Lund–Saraf–Wolf conjectures, a proof of Ikenmeyer–Pak–Panova’s symmetric-group character conjecture, and an answer to Erd˝os–Straus’s binomial-coefficient divisibility question.The 15 artifacts were selected based on the authors’ own interest.Source: §1 · p. 2
• 4,717 apparently well-posed, still-open combinatorics conjectures yielded 598 potential resolutions, with 77 items selected for author-team review.The pipeline began with 51,110 mathematics papers, identified 5,245 combinatorics papers, and extracted 6,453 candidate conjectures or open problems from 2,742 papers.Source: §1 · p. 2
• The authors frame solving-attempt allocation as constrained optimization and report that strategies can outperform a uniform baseline, with the best strategy depending on whether the objective is artifact count or importance.Frontier-model reasoning and expert mathematical review are scarce resources whose value depends on which conjectures receive them.Source: §1 · pp. 1–2

2.1 AI FOR MATHEMATICAL RESEARCH

• Recent systems advance construction search, formal proof search, and autonomous attempts, but problem selection and expert review remain narrow parts of the AI-for-math pipeline.Related work also explores mathematician-steered parallel workstreams (Zheng et al., 2026); Tao (2026) describes the broader transition as proof abundance.Source: §2.1 · p. 3
• Mathematicians specify a research direction, and the system searches literature for candidate problems to attempt, while experts retain responsibility for validating and reporting claims.The human-specified direction bounds the system’s initiative and aligns it with mathematicians’ interests and expertise.Source: §2.1 · p. 3

2.2 CONSTRUCTING AN ATTEMPTABLE POOL

• Because problems and their changing status are dispersed across literature, an attemptable pool requires recovering statements in context and checking that they remain well posed and unresolved.Candidates may appear as numbered statements, questions, remarks, unresolved cases, or sentences embedded in local notation.Source: §2.2 · p. 3
• Unlike automated conjecturing, which creates new questions, this approach recovers unresolved literature statements with source text, local context, and status evidence.The resulting pool P comprises source-grounded conjectures that appear well posed and still open; staged recommendation cascades narrow candidates for expert attention (Zhu et al., 2026).Source: §2.2 · p. 4

2.3 EFFORT ALLOCATION UNDER UNCERTAINTY

• Each conjecture in the attemptable pool is pulled once, yielding no reliable result, a known resolution, or a candidate proof or counterexample, before review narrows to fewer outputs.The effort-allocation problem reflects uncertainty about model difficulty; as models improve, previously unreachable conjectures may become reachable, and further bandit algorithms are left for future work.Source: §2.3 · pp. 4–5

3 METHOD

• FAR progressively narrows a literature corpus through increasingly costly stages, from finding attemptable open problems to attempting resolutions and recommending conjecture-resolution pairs for expert review.Later stages receive more compute per item.Source: §3 · p. 5

3.1 FINDING RELEVANT OPEN PROBLEMS

• The finding stage labels papers for relevance, extracts unresolved statements, and checks their validity and status to form a pool P of relevant problems that appear well posed and still open.Extraction is permissive beyond excluding nonspecific future work and problems already resolved in the source paper; checking marks candidates open, solved, or invalid using available evidence.Source: §3.1 · pp. 5–6

3.2 ATTEMPTING FOR CANDIDATE RESOLUTIONS

• Each conjecture in P receives one attempt, using its extracted statement and source paper; the strongest model searches for prior resolutions and labels outcomes KNOWN, NEW, FIX, or NONE.Only NEW outcomes—complete proofs or counterexamples—advance to recommendation; one attempt per conjecture allocates the attempt budget uniformly.Source: §3.2 · p. 6

3.3 RECOMMENDATION FOR EXPERT REVIEW

• Agents check each NEW outcome for correctness, then classify passing results as known, too minor, or substantial enough to publish; mathematicians review selected artifacts for correctness and novelty.An outcome passes only if every judging agent passes it; results judged substantial form set A for expert review.Source: §3.3 · pp. 6–7

4.1 SETUP

• The corpus began with 51,110 mathematics papers; labeling kept 5,245, extraction found 6,453 candidates, and checking left 4,717 conjectures from 2,206 papers for attempts.The pipeline is not tied to OpenAlex, the metadata and source-link collection used for this pilot.Source: §4.1 · p. 7

4.2 OUTCOMES

• 77 of 4,717 attempted conjectures remained publishable after 1,050 NEW claims yielded 598 judging passes and grading removed 75 known and 446 too-minor results.The authors reviewed 15 particularly interesting artifacts in the publishable set, and all 15 were mathematically correct; one had been settled shortly before the run by a route the cascade searches missed.Source: §4.2 · p. 7

4.3.1 VALIDITY OF THE AGENT’S DIFFICULTY AND IMPORTANCE SCORES

• Difficulty and importance scores positively tracked outcomes, with AUCs of 0.69 for no accepted resolution and 0.60 for publishable grading, respectively.The associations had p < 10^-40 and p = 0.008, respectively; difficulty still separated accepted from unaccepted resolutions among conjectures with the same importance score.Source: §4.3.1 · pp. 8–9, Figure 4 · p. 8
• The scores were strongly associated: their Spearman rank correlation was 0.83, and over 60% of conjectures scored strictly above the diagonal.The authors attribute this dependence partly to selection: among problems still open, important questions tend to remain open only while they are hard.Source: §4.3.1 · p. 9

4.3.2 WHERE TO SPEND A LIMITED BUDGET

• When attempt outcomes are unknown, estimated success probability can guide near-optimal selections for artifact count and total importance, while best-artifact allocation also uses an importance-based restriction.The estimated probability is the product of fitted resolution and publishability factors; artifact count ranks by that estimate, total importance ranks by importance times the estimate, and the best-artifact strategy first keeps a top fraction by importance.Source: §4.3.2 · pp. 9–10
• For publishable-artifact count, ranking by estimated success probability beat every strategy at every budget; for total importance it narrowly beat the prescribed importance-weighted ranking.For the best-single-artifact objective, the whole-pool rankings performed poorly and fell behind uniform random at larger budgets; restricting to the most important tenth and ranking by estimated success probability worked best among the tested fractions. Results depend on the scoring model, pool sources, and cascade models.Source: §4.3.2 · p. 11, Figure 5 · p. 11

5.1 A KNOWN RESULT GRADED AS NEW

• The artifact proved F(n; t)/n → 1/2, but this correct result was already known and the cascade missed a recent recorded proof.The recommend stage graded it as publishable; the Erdős problems site had recorded a proof four months before the run, and Tao noted a quick derivation from Elliott’s inequality.Source: §5.1 · pp. 11–12

5.2 A CONNECTION NOT PREVIOUSLY MADE

• For odd q, the artifact disproves Lund et al. (2018)’s conjecture with a line family whose union has density 1/2 + o(1).The family has q^2(q + 1)/2 lines, no plane contains more than q + 1, and the construction is the classical half-tangent partition of an elliptic quadric; its contribution is linking it to the conjecture.Source: §5.2 · p. 12

5.3 RESULTS WITH NO PRECEDENT FOUND

• The artifact proved Ikenmeyer et al. (2024)’s conjecture that binary symmetric-group character values are GapP-complete under many-one reductions.It reduces the difference of two exact-cover counts to one character value at a two-row partition and checks membership in GapP separately.Source: §5.3 · p. 12
• For the Davies et al. (2018) conjecture, C5 □ K_m,m gives a ratio tending to 24/13, lowered to 32/19 by C13(1, 5).The first graph is triangle-free and (m + 2)-regular; the construction yields α = 4m.Source: §5.3 · p. 12
• The artifact shows d*(n) = 1 for every fixed n ≥ 2, answering the question of Erdős & Straus (1977).Their passage notes that the n = 2 case seemed much harder to decide.Source: §5.3 · pp. 12–13

6 CONCLUSION

• FAR recovered 6,453 candidate statements, checked 4,717 into an attemptable pool, and returned 77 substantial artifacts, 15 of which authors reviewed and found correct.The conclusion also reports constrained-optimization strategies for allocating effort and says pre-reasoning difficulty and importance scores can support those strategies.Source: §6 · p. 13

A PROMPT TEMPLATES AND OPERATIONAL DETAILS

• The appendix provides implementation prompts, schema validators, and retry logic, with the pilot’s research direction set to combinatorics.The appendix also specifies extraction and status-checking prompts for identifying explicit unresolved statements and assessing whether candidates remain open.Source: A PROMPT TEMPLATES AND OPERATIONAL… · p. 18, §A.1 · p. 19

A.1 FINDING RELEVANT OPEN PROBLEMS

• Problem-finding prompts require an explicit unresolved mathematical statement, exclude generic future work and already-resolved results, and verify candidate status against current web information.The prompts also define structured outputs and importance and difficulty scores for candidates.Source: §A.1 · pp. 19–20

A.2 ATTEMPTING FOR CANDIDATE RESOLUTIONS

• Resolution prompts reconstruct the conjecture with its hypotheses and notation, test examples and counterexamples, and require rigorous proofs or disproofs, including minimal repairs for formulation defects.They also require a verification audit that checks the formalization, assumptions, theorem hypotheses, and conclusion against the target statement.Source: §A.2 · pp. 20–21

A.3 JUDGING AND GRADING

• The judge accepts only rigorous, complete resolutions of the correct statement, and conducts a thorough literature search for claimed new results before routing or grading them.Known and new outcomes go to the judge; only results accepted as new reach the grader.Source: §A.3 · pp. 22–23
• The judge assumes the accepted proof is correct unless literature search clearly contradicts it, then searches broadly for prior or stronger results and assesses difficulty, novelty, community interest, and likely venue.The search is meant to go beyond papers citing the original work to open-access notes, surveys, forums, and other sources, since catching missed references is a primary goal.Source: §A.3 · p. 23
• KNOWN means a similar or stronger result is already published; TYPE1 is new but minor, TYPE2 merits a standalone paper, and TYPE3 merits a top combinatorics journal.Only TYPE2 and TYPE3 items are put forward for expert review.Source: §A.3 · p. 24
• When uncertain between grades, the judge selects the lower grade and explains the uncertainty.Source: §A.3 · p. 24

B.1 SCORE VALIDITY

• Figure 6 plots difficulty and importance scores against the quantities they judge, with each bin showing its measured rate and 95% Wilson interval.The panels pair δ with difficulty and ι with importance at a uniform bin width of 0.1.Source: §B.1 · p. 25, Figure 6 · p. 25

B.2 ALLOCATION CURVES

• Tables 2–4 report expected artifact count, total importance, and maximum importance, respectively, using 1000 random five-part partitions and a uniform baseline.Each run fits both factors of the allocation score on four parts and ranks the remaining part; the five selections form the evaluated set.Source: §B.2 · p. 25, Table 2 · p. 25, Table 3 · p. 25

C.1.1 INTRODUCTION

• The Paley graph on 3125 vertices has property P(1, 2, 377), refuting Ananchuen & Caccetta’s (1995, Remark 2) conjecture that their threshold is exact.For k = 377, the conjectured window includes q = 3125.Source: §C.1.1 · p. 28

C.1.2 THE CHARACTER COUNT

• The character count gives 8N(b, c) = q + 1 + S(b, c) − R(b, c), with correction R(b, c) restricted to 0, 4, or 8.S(b, c) is minus the trace of the elliptic curve y^2 = x(x − b)(x − c).Source: §C.1.1 · p. 29, §C.1.2 · p. 29

C.1.3 TRACES OF ELLIPTIC CURVES

• For p > 3 and odd r, an elliptic curve over F_p^r whose trace is divisible by p must have trace zero.This consequence of Waterhouse’s classification is used to rule out the trace required by the equality case.Source: §C.1.3 · p. 30

C.1.4 PROOF OF THE MAIN THEOREM

• A quadratic-character count reduces the Paley-graph vertex count to an elliptic-curve trace, and excluding the equality case yields at least 377 vertices for every prescribed triple.The only obstruction would require trace 110 over F_5^5, which is forbidden by the trace classification for odd-degree fields of characteristic greater than 3.Source: §C.1.3 · p. 30, §C.1.4 · p. 31

C.2 A 4-UNIFORM TREE THAT IS NOT 5-GOOD

• The unique 4-uniform tree on seven vertices is not 5-good, as shown by a red/blue coloring of K(4)_8 whose red edges are the fourteen affine planes of F_3.This counterexample shows that r-uniform trees are not always optimal in the Ramsey problem against a complete r-uniform hypergraph.Source: §C.2 · p. 31

C.2.1 INTRODUCTION

• Budden & Penland (2017, Conjecture 6.2) conjectured that every r-uniform tree is n-good for every n ≥ r.The paper’s 4-uniform example supplies a counterexample to this proposed extension of the ordinary-tree result.Source: §C.2 · p. 31, §C.2.1 · p. 32
• The smallest nontrivial 4-uniform tree, with two edges meeting in one vertex, is not 5-good, refuting Budden & Penland (2017) Conjecture 6.2.The bounds place its Ramsey number at 9 rather than 8.Source: §C.2.1 · p. 33
• The bound gap has width j(k − 1) and closes exactly when (r − 1) divides (n − 1) or the tree is a single edge.For (r, m, n) = (4, 7, 5), the bounds are {8, 9} and the result is at the top; for (3, 5, 4), they are {6, 7} and the truth is at the bottom, with R(T (3); 4) = 6 (Budden & Penland, 2017).Source: §C.2.1 · p. 33

C.2.2 THE AFFINE-PLANE COLORING

• Coloring 4-subsets of F3^2 red when they are affine planes and blue otherwise gives a lower-bound coloring: planes meet in 0 or 2 points, never 1, and every 5 points contain one.Thus two red edges cannot meet as the two edges of the tree do.Source: §C.2.1 · p. 33, §C.2.2 · p. 33, Figure 7 · p. 34
• There are exactly 14 affine planes in F3^2, and a 4-subset is one exactly when its four vectors sum to 0.Each plane has size 4.Source: §C.2.2 · p. 33

C.2.3 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.Source: §C.2.3 · p. 34
• Every 5-subset of F_2^3 contains a red 4-subset, so there is no blue K(4) with |X| = 5.A blue K(4) on a 5-set would require all its 4-subsets to be blue.Source: §C.2.3 · p. 34

C.2.4 PROOF OF THE MAIN THEOREM

• The proof invokes the hypertree embedding theorem: weak chromatic number greater than k guarantees every r-uniform tree with k edges.Loh’s theorem removed dependence on uniformity r in answering a question of Bohman et al.Source: §C.2.4 · p. 34
• R(T, K_5^(4); 4) = 9, establishing the exact value from the lower-bound coloring and the proof’s upper bound.The upper bound rules out a red copy of T or a blue K_5^(4) in every coloring of K_9^(4).Source: §C.2.4 · pp. 34–35
• The tree is not 5-good: the Ramsey number is 9, while the criterion’s right-hand side is 8.The calculation uses χw(K_5^(4)) = 2, s(K_5^(4)) = 2, and |V(T)| = 7.Source: §C.2.4 · p. 35
• The result settles the r = 4 value left within Budden & Penland’s 8-to-9 bound, and the tree is also not 6-good.Budden & Clifton’s theorem states that a 4-uniform tree that is 6-good is also 5-good and 4-good.Source: §C.2.4 · p. 35

C.3 MAXIMUM VERSUS AVERAGE INDEPENDENT SET SIZE IN TRIANGLE-FREE GRAPHS

• The graphs C5 □ Km,m are triangle-free and (m + 2)-regular, yet their maximum-to-average independent-set-size ratio tends to 24/13, below 2.This disproves Davies et al. (2018)’s conjecture that a factor 2 − o(1) is forced when minimum degree is large; the two Km,m sides must choose independent sets from disjoint parts of the pentagon.Source: §C.3 · p. 35

C.3.1 INTRODUCTION

• 24/13 (1.846...) is the limiting ratio for Gm, refuting Davies et al. (2018, Conjecture 2) and the minimum-degree assertion of their Conjecture 4 for every fixed r ≥3.The graphs have minimum degree m + 2 →∞, so the ratio cannot satisfy a bound of the form 2 − od(1).Source: §C.3.1 · p. 36
• The examples leave Davies et al. (2018, Conjecture 1) and the first assertion of Conjecture 4 untouched, and say nothing about triangle-free graphs with α(G) = o(|V(G)|).Their ratio exceeds 4/3, and their independence number is 2/5 of the vertex count; the general bound already forces a ratio of at least 7/5 in this range.Source: §C.3.1 · p. 37
• Classifying independent sets by the two unions gives a signed sum over disjoint pairs of subsets of Z5; the dominant configuration has average size 13/6 per pair of opposite fibers.The maximizing pair consists of a nonadjacent pair in C5 and its complement.Source: §C.3.1 · p. 37

C.3.2 THE CONSTRUCTION

• Gm = C5 □ Km,m is triangle-free, (m + 2)-regular on 10m vertices, and has independence number 4m.Each fiber induces a C5, and independent sets chosen on opposite sides of Km,m must be disjoint; selecting {0, 2} on one side and {1, 3} on the other attains size 4m.Source: §C.3.2 · p. 37, Figure 8 · p. 38

C.3.3 EXACT COUNTING BY M ¨OBIUS INVERSION

• To avoid overcounting, the exact-counting argument requires each side’s union to equal its specified subset, then uses Boolean-lattice Möbius inversion to count such tuples.Counting tuples whose union is contained in X first provides the generating function from which inversion recovers those whose union is exactly X.Source: §C.3.3 · p. 38
• Partitioning independent sets by their ordered pair of side-unions yields an exact identity, which substitution reduces to an explicitly signed sum over disjoint pairs.For each fixed pair, the coefficient is obtained by assigning each remaining vertex to the first subset, the second, or neither.Source: §C.3.3 · pp. 38–39

C.3.4 THE DOMINANT PAIRS

• The dominant pairs have product 24, all other disjoint pairs have product at most 16, and the resulting graph ratio tends to 24/13.There are 10 ordered dominant pairs; each has mean 13/6 for the sum of the two independent-set sizes.Source: §C.3.4 · pp. 39–40
• The dominant-pair argument also yields a ratio limit of 32/19 for C13(1,5) □ Km,m, and clique-fiber constructions give Kq+1-free graphs with ratio limit ρq.For C13(1,5), the maximum product is 1728 on 52 ordered pairs, and each dominant pair has mean 19/4; disjoint unions preserve the ratio while allowing arbitrarily many vertices at fixed minimum degree.Source: §C.3.4 · p. 40

C.4 SETS WITH NO LARGE DIVISOR DIFFERENCE

• For each fixed integer t ≥ 1 and sufficiently large n, every t-admissible subset of [n] has size at most n/2 + 3n/√log log n.The exact value of F(n; t) remains open.Source: §C.4 · p. 41, §C.4.1 · p. 42

C.4.1 INTRODUCTION

• A t-admissible set contains no pair whose difference is at least t and divides either element; for t = 1, the odd numbers attain the maximum size ⌈n/2⌉.For t ≥ 2, Erdős’s construction shows the bound cannot hold with an error term of zero.Source: §C.4.1 · pp. 41–42

C.4.2 A SECOND MOMENT ESTIMATE

• Weighting integers by their prime factors in (t, n^1/3] gives mean κ = log log n + O_t(1), while the weight’s square deviation on each parity class is at most nκ/2 + O(|P|^2).Cauchy–Schwarz converts this weighted inequality into a bound of size n/√κ on the excess of even elements over omitted odd elements.Source: §C.4.1 · p. 42, §C.4.3 · p. 43

C.4.3 PROOF OF THE MAIN THEOREM

• For each odd prime p > t, the injection a ↦ a − p sends each even multiple a of p in A to an odd multiple excluded from A.Summing over p and applying Cauchy–Schwarz with the second-moment estimate yields the stated upper bound.Source: §C.4.3 · pp. 43–44

C.5.1 INTRODUCTION

• Restricting k to 1 ≤ k ≤ m − n makes the binomial-coefficient divisibility question nonvacuous; under this restriction, the density is 1 for each fixed n ≥ 2.Without a restriction, sufficiently large k makes the quotient an integer, so the question would be vacuous.Source: §C.5.1 · p. 45

C.5 DIVISIBILITY AMONG BINOMIAL COEFFICIENTS

• For every fixed n ≥ 2, the density of m admitting a k with A(n,k) dividing A(m,k), subject to 1 ≤ k ≤ m − n, exists and equals 1.For each B, the proof finds a single k such that the coefficient has no prime factor below B, forcing divisibility through congruence conditions on m.Source: §C.5 · p. 44, §C.5.1 · p. 45

C.5.1 INTRODUCTION

• For every fixed n ≥ 2, G_n has natural density 1, although the proof does not show that every sufficiently large m lies in G_n.The argument uses one admissible k of size e^O_n(B) to cover a set of density approaching 1; it gives no information about small k or the boundary case k = m − n.Source: §C.5.1 · p. 46, §C.5.4 · p. 49

C.5.3 A CONGRUENCE FORCING THE DIVISIBILITY

• For each prime q | N_B, the condition m mod q ∈ {i(q), …, q − 1} forces the full prime power q^a_q to divide the binomial coefficient.Although the divisibility concerns q^a_q, the required condition is only modulo q; the Chinese remainder theorem combines these conditions across primes.Source: §C.5.1 · p. 46, §C.5.3 · p. 47

C.5.2 A BINOMIAL COEFFICIENT FREE OF SMALL PRIMES

• Every prime divisor of N_B exceeds B, so each prime q dividing N_B occurs in exactly one of k_B + 1, …, k_B + n.The construction chooses k_B so that N_B has no prime factor below B; since q > B > n, it cannot divide two of those n consecutive integers.Source: §C.5.2 · p. 46, §C.5.1 · p. 46

C.5.4 THE DENSITY OF THE CONGRUENCE SET

• The congruence set T_B has density tending to 1 as B → ∞, and sufficiently large members of T_B belong to G_n.The proof obtains d(T_B) > 1 − ε and then uses k = k_B for its members m ≥ n + k_B.Source: §C.5.4 · pp. 48–49

C.6.1 INTRODUCTION

• COMPUTECHARBINARY is GapP-complete under polynomial-time many-one reductions, with the character partition λ always having at most two parts.The reduction maps each input x to partitions (λ_x, µ_x) of a common integer and computes the GapP function exactly.Source: §C.6.1 · p. 50

C.6.2 CHARACTERS OF TWO-ROW SHAPE

• For a two-row shape, the character value is the difference of subset-sum counts at consecutive targets.The counts N_µ(t) count subsets of the parts of µ with total size t.Source: §C.6.1 · p. 50, §C.6.2 · p. 51

C.6.1 INTRODUCTION

• The reduction encodes two exact-cover counts as subset-sum counts at consecutive targets using a large base, disjoint digit blocks, and two selector parts.The targets differ by 1, so the selector parts separate the two instances in the units digit while pre-filling the other instance’s digit block.Source: §C.6 · p. 49, §C.6.1 · p. 50, §C.6.3 · p. 51

C.6.3 A DIFFERENCE OF TWO EXACT COVER COUNTS

• An exact-cover instance is a finite set together with a list of nonempty subsets, and its value counts selections covering each element exactly once.Selections are subsets of the listed sets, which are treated as distinct even when they have equal content.Source: §C.6.3 · p. 51
• DIFF#EXACTCOVER is GapP-hard: a parsimonious reduction maps satisfying assignments of bounded-width CNF formulas to exact covers.The constructed exact covers correspond bijectively to satisfying assignments.Source: §C.6.3 · p. 52

C.6.4 THE DIGIT GADGET

• The digit gadget makes subset sums to s and s − 1 count exact covers of the two respective instances, using selector digits and carry-free base-Q encoding.The resulting equalities are Nµ(s) = ec(X, C) and Nµ(s − 1) = ec(X′, C′).Source: Table 5 · p. 53, §C.6.4 · pp. 53–54

C.6.5 MEMBERSHIP IN GapP

• COMPUTECHARBINARY belongs to GapP because the character formula expresses each value as a difference of two #P counts.The two counts enumerate signed permutations paired with partitions of the input parts into blocks of prescribed weights.Source: §C.6.5 · p. 54

C.6.6 PROOF OF THE MAIN THEOREM

• COMPUTECHARBINARY is GapP-complete, with hardness reductions producing inputs whose partition λ has at most two parts.The reduction maps each input x to partitions (λ_x, µ_x) and preserves the GapP function value as the character value.Source: §C.6.6 · p. 54

C.7 MATCHING VARIANCE VERSUS THE RESIDUAL MATCHING NUMBER

• Along cliques with private pendant leaves, σ²/λ grows at least linearly in the leaves per clique vertex while both parameters tend to infinity.The added leaves inflate fluctuations in the clique matching without inflating the residual matching number.Source: §C.7 · p. 55

C.7.1 INTRODUCTION

• Kahn’s theorem makes bounded variance and bounded residual matching number equivalent along the specified graph sequences, and asks whether λ = Θ(σ²).The question asks whether both ratios λ/σ² and σ²/λ are bounded.Source: §C.7.1 · p. 56
• The section disproves σ2 = O(λ), beyond Kahn’s recorded σ2 = O(λ4) bound for λ = Ω(1).Earlier Kahn examples had σ2 ≍ λ; the new construction decouples the parameters through the clique.Source: §C.7.1 · p. 56

C.7.2 THE CONSTRUCTION

• For n ≥ n0 and 4 ≤ a ≤ n^1/4, the constructed graphs satisfy 1/4√n ≤ λ(Gn,a) ≤ 5√n and σ2(Gn,a) ≥ c a√n.Gn,a is a clique Kn with a − 1 private leaves at each clique vertex; an uncovered clique vertex has a choices, including taking no leaf.Source: §C.7.2 · p. 56

In particular

• For H_n = G_{n,⌊n^1/4⌋}, λ(H_n) and σ2(H_n) diverge, while σ2(H_n) ≥ c/(2·5^(3/2)) λ(H_n)^(3/2), ruling out σ2 ≤ Cλ and any σ2 = O(λ^β) bound with β < 3/2.The family does not resolve the reverse bound λ = O(σ2); there λ/σ2 → 0, and the best stated bound remains λ ≤ ν − μ = O(σ8) when σ = Ω(1).Source: In particular · p. 57

C.7.3 THE LAW OF A UNIFORM MATCHING

• For a uniform matching, S has the parity of n, B conditional on S is Bin(S, (a − 1)/a), and ξ = (n − S)/2 + B with ν(FM) = S − B.Consequently, λ(Gn,a) = E[S]/a; the proof reduces the parameter estimates to the mean and variance of S.Source: §C.7.3 · p. 58

C.7.4 THE DISTRIBUTION OF THE FREE SET

• The weights ws are strictly log-concave and unimodal on the admissible parity class, with a mode s0 ≤ 2L + 2.The mode bound follows from the fact that ws+2 < ws for every admissible s ≥ 2L.Source: §C.7.4 · p. 59
• E[S] ≤ 5L and consequently λ(Gn,a) ≤ 5√n under equation 21 for large n.The proof bounds the upper tail using geometrically decreasing weights beyond T ≥ 2L.Source: §C.7.4 · p. 59
• The technical bound showing that S has no heavy atom forces its variance to be large and rules out bounded λ(Gn,a).This bound is identified as the technical heart of the argument.Source: §C.7.4 · p. 59
• E[S] ≥ L/4 and consequently λ(Gn,a) ≥ √n/4 under equation 21 for large n.The proof controls the lower tail using geometrically decreasing weights below T′ ≤ L/2.Source: §C.7.4 · p. 60

C.7.5 A VARIANCE LOWER BOUND

• For integer-valued X, Lemma C.7.12 converts a bound on its largest point mass into a lower bound on its variance.It defines θ as the maximum point mass, θ := maxk∈Z P(X = k).Source: §C.7.5 · p. 61
• Var[S] ≥ L/8000 under equation 21 for large n.The application uses the bound on the largest atom of S from Lemma C.7.10.Source: §C.7.5 · p. 61

C.7.6 PROOF OF THE MAIN THEOREM

• σ2(Gn,a)/λ(Gn,a) ≥ 2*10^-7a for n sufficiently large and 4 ≤ a ≤ n^1/4.The proof obtains this ratio by dividing the bounds on σ2(Gn,a) and λ(Gn,a).Source: §C.7.6 · p. 61
• For an = ⌊n^1/4⌋, the graphs Hn satisfy λ(Hn) ≥ √n/4 and σ2(Hn)/λ(Hn) ≥ Ω(n^1/4).Both λ(Hn) and σ2(Hn) tend to infinity; these bounds rule out any universal σ2(G) ≤ Cλ(G) bound for finite simple graphs.Source: §C.7.6 · p. 61

C.8 AN ORDERED HYPERGRAPH EXTREMAL FUNCTION OF ORDER n log n

• exe(G1, n) = Θ(n log n), matching the order of the corresponding ordered graph extremal function.The result resolves Klazar’s question up to implied constants; the earlier hypergraph bounds differed by a factor of log n(log log n)^3.Source: §C.8 · p. 62, §C.8.1 · p. 63

C.8.1 INTRODUCTION

• Processing each hyperedge by recording a previously unrecorded vertex pair yields a G1-free ordered graph that controls the G1-free hypergraph.A G1 copy in the recorded graph would pull back to four distinct hyperedges forming a copy in the hypergraph.Source: §C.8.1 · p. 63

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 has at most 4e(B) cliques of size at least two.A clique is determined by its two smallest vertices and a subset of their at most two common neighbors to the right.Source: §C.8.2 · p. 63

C.8.3 PROOF OF THE MAIN THEOREM

• The proof bounds hyperedges by counting at most n singleton edges, e(B) assigned edges, and 4e(B) unassigned edges in the auxiliary graph construction.The auxiliary graph has at most n vertices and is G1-free; each unassigned edge is a distinct clique of size at least two.Source: §C.8.3 · pp. 63–64
• Klazar’s bound gives exi(G1, n) ≤ 27 exe(G1, n), so the incidence extremal function also satisfies exi(G1, n) = Θ(n log n).The cited bound applies because G1 has no two separated edges, with p = 5 vertices and q = 4 edges.Source: §C.8.3 · p. 64

C.9.1 INTRODUCTION

• Kumar et al. (2025, Conjecture 20) asks whether m_Gt(−∞, −2) eventually stabilizes; eigenvalues converging to −2 may cross that threshold repeatedly.The count is uniformly bounded by the number of vertices of degree at least 3, but the boundary case where eigenvalue limits equal −2 prevents the earlier argument from settling it. The count measures how far the subdivided graph is from being a generalized line graph.Source: §C.9.1 · pp. 65–66
• For every G and S, m_Gt(−∞, −2) equals n_−(K∞) for all sufficiently large t.This identifies the conjectured eventual constant for arbitrary selected edge sets.Source: §C.9.1 · p. 66
• When every edge is subdivided, m_Gt(−∞, −2) is |Q| for all sufficiently large t, as predicted by Kumar et al. (2025).Here Q contains the vertices of degree at least 3; this makes explicit the negative-side tightness of the interlacing bound.Source: §C.9.1 · p. 66
• 1, 0, 1, 0, 1, 1, 1, 1, ... are the successive counts below −2 in the cycle-with-pendant-edge example, stabilizing at t = 5.The early oscillation follows cycle-length parity; the effective threshold bound only guarantees constancy for t ≥ 44 in this example.Source: §C.9.1 · p. 66

C.9.2 ELIMINATING THE SUBDIVISION VERTICES

• For t ≥ 2, eliminating the internal stretch vertices preserves negative inertia and reduces A(Gt) + 2I to the Schur complement Kt on the original vertices.The internal blocks are positive definite tridiagonal matrices, enabling Haynsworth’s inertia additivity formula; their inverse entries determine the Schur-complement contributions from each stretched edge.Source: §C.9.2 · pp. 67–68
• For t = 2 with S = E(G), m_G2(−∞, −2) equals the number of signless Laplacian eigenvalues of G exceeding 4.The nonzero adjacency eigenvalues of the subdivision graph are ±√q for nonzero signless Laplacian eigenvalues q, so −√q < −2 exactly when q > 4.Source: §C.9.2 · p. 68

C.9.3 COMPARISON IN THE LOEWNER ORDER

• Kt ⪰ K∞ and ∥Kt − K∞∥ ≤ 2∆(G)/t for every t ≥ 2.The positive-semidefinite difference is scaled by 1/t and uses the Laplacian of (V(G), S) for even t and its signless Laplacian for odd t.Source: §C.9.3 · p. 68

C.9.4 PROOF OF THE MAIN THEOREM

• For t > max{2, 2∆(G)/γ}, the negative eigenvalue count satisfies m_Gt(−∞, −2) = n−(K∞).The proof obtains n−(Kt) = n−(K∞) by combining upper and lower bounds; for S = E(G), this count equals the number of vertices of degree at least 3.Source: §C.9.4 · p. 69

C.10.1 INTRODUCTION

• The counterexample uses a classical half-tangent family, whose novel role here is to refute the line-union conjectures along odd prime powers; the Nikodym conjecture remains open.The construction shows that the constant 1 in Conjecture 1.4 cannot be replaced by more than 1/2, but does not address whether some absolute positive constant suffices.Source: §C.10.1 · p. 71

C.10.2 THE HALF-TANGENT FAMILY

• Selecting the (q + 1)/2 square directions of the anisotropic form Q(x, y) = x^2 − νy^2 yields q^2(q + 1)/2 tangent lines, each meeting the paraboloid only at its tangency point.Along the selected lines, Q(x, y) − z takes values in 0 or the nonzero squares, which determines the family’s union.Source: §C.10.2 · pp. 71–72, §C.10.1 · p. 71

C.10.3 LINES CONTAINED IN A PLANE

• Every plane contains at most q + 1 lines from the half-tangent family; a tangent plane contains exactly (q + 1)/2.A non-tangent plane contains at most one selected tangent line at each point of its intersection with the paraboloid, which has at most q + 1 points.Source: §C.10.3 · p. 73

C.10.4 THE UNION

• For every odd prime power q, a family of q^2(q + 1)/2 lines has at most q + 1 lines per plane and a union of the same size, refuting both Lund et al. (2018) conjectures.The conjectures fail for Conjecture 1.5 for every fixed 0 < ε < 1/2; this does not resolve the Nikodym conjecture itself.Source: §C.10.1 · p. 71, §C.10.4 · p. 74
• The half-tangent family refutes Conjecture 1.4 of Lund et al. (2018) and Conjecture 1.5 of Lund et al. (2018) for every fixed 0 < ε < 1/2.For Conjecture 1.4 its plane bound meets the hypothesis for C = 1/2 while its union misses the claimed near-total coverage; for Conjecture 1.5 the stated line-count and plane bounds hold but the union-size error is not O(q^5/2).Source: §C.10.4 · p. 74

C.11.1 INTRODUCTION

• For signed graphs, the signed circular chromatic number is switching invariant and lies between the ordinary circular chromatic number and twice that value; at prescribed girth, known examples approach but never attain 2k.Naserasr et al. (2020) give graphs with χ(G) = k and signed circular chromatic number greater than 2k − ε, prompting the question of whether the supremum is attained.Source: §C.11.1 · p. 75
• The signed-graph girth attainment question had not been settled for every k,g, and the construction adapts Erdős’s (1959) deletion argument to a random k-partite signed graph.Source: §C.11.1 · p. 75

C.11.2 STATEMENT AND SMALL CASES

• Every signature of a graph with χ(G) ≤ k has signed circular chromatic number at most 2k, so the theorem’s key challenge is constructing a matching lower-bound witness.A witness must exclude every admissible ratio below 2k at once; the construction also yields graphs where deleting any single edge does not lower the chromatic number.Source: §C.11.2 · p. 76
• For every k,g ≥ 2, a finite graph exists with χ(G) = k, girth at least g, and signed circular chromatic number 2k.The proof is probabilistic and does not exhibit an explicit graph; it does not address the separate question about approximating arbitrary rational values at prescribed girth.Source: §C.11.2 · p. 76, §C.11.4 · p. 78

C.11.3 NEUTRAL COLOR PAIRS

• When p/q < 2k, every k-tuple of colors contains a blocking pair because a neutral clique has size at most ⌊p/(2q)⌋ ≤ k − 1.Source: §C.11.3 · p. 77

C.11.4 THE RANDOM CONSTRUCTION

• For each coloring, at least m^2 cross pairs are blocking; random edge selection defeats cheap colorings, and deleting edges from short cycles yields a k-partite graph of girth at least g.The resulting graph retains χ(G) = k and signed circular chromatic number at least 2k.Source: §C.11.4 · pp. 77–78

C.12.1 INTRODUCTION

• For infinitely many n, there are at least exp(cn^2 log n) pairwise nonisomorphic 4-critical linear triple systems on n vertices.This disproves the conjectured exponential-in-n^2 upper bound for (k,r,l) = (4,3,2).Source: §C.12 · p. 79, §C.12.1 · p. 80

C.12.2 THE CONSTRUCTION

• The construction encodes proper edge colorings of a dense 4-critical graph into linear triple systems using gadgets that force palette vertices to share a color and vertex copies to receive distinct colors.A minimal non-3-colorable subsystem retains a triple encoding every graph edge’s color, making the encoding injective; the proof counts at least (2m)^e(G) proper edge colorings.Source: §C.12.1 · p. 80, §C.12.2 · p. 81
• For each β, the construction forms a linear triple system Jβ of O(m) vertices that cannot be 3-colored, using gadgets to enforce palette agreement and distinct colors for each vertex’s copies.A proper coloring would induce a proper 3-coloring of the 4-chromatic graph G, a contradiction.Source: §C.12.2 · pp. 81–82, Figure 13 · p. 82

C.12.3 RECOVERING THE EDGE COLORING

• The construction produces distinct 4-critical linear triple systems, each with at least e(G) edges, by extracting edge-minimal non-3-colorable subhypergraphs that encode distinct edge colorings.Each extracted system is 4-critical, and the encoding makes the map from edge colorings to labeled systems injective.Source: §C.12.3 · p. 83

C.12.4 PROOF OF THE MAIN THEOREM

• The proof yields systems on infinitely many distinct sizes q = Θ(m), after counting many labeled constructions on a common vertex set and comparing them with the number of labelings per isomorphism class.The construction bounds the common vertex set size by C0m, while linearity and the edge lower bound force q = Θ(m).Source: §C.12.4 · p. 83

C.13 STRONGLY CONNECTED DIGRAPHS WITH NO SMALL k-KERNEL

• The k-kernel examples use a hub and m directed arms returning through a common tail, whose length forces the hub out of every k-kernel and makes each arm require representation.The argument adapts an earlier acyclic construction by attaching a return path; the paper notes two later independent refutations.Source: §C.13 · p. 84, §C.13.1 · p. 85

C.13.1 INTRODUCTION

• For every k ≥ 3, the proposed |V(G)|/(k + 1) + O_k(1) bound fails for strongly connected digraphs, and the failure has a linear rather than constant margin.The coefficient c*_k is at most 1/(k − 1); whether 1/k is admissible remains open for k ≥ 3.Source: §C.13.1 · p. 85

C.13.2 THE CONSTRUCTION

• The strongly connected digraph Gk,m has mk + k + 2 vertices, with m arms of k vertices and a shared tail returning to the hub.Every vertex reaches the hub and the hub reaches every vertex, establishing strong connectivity.Source: §C.13.2 · p. 86, Figure 14 · p. 86

C.13.3 A SMALL k-KERNEL

• The set {y} ∪ {ai,k : 1 ≤ i ≤ m} is a k-kernel of Gk,m of size m + 1.It is stable, and its vertices cover every vertex within directed distance at most k.Source: §C.13.3 · p. 86

C.13.4 EVERY k-KERNEL IS LARGE

• Every k-kernel of Gk,m has at least m + 1 vertices, since it must meet each arm and the tail while stability excludes the hub.No vertex outside the tail can reach y within k steps, and no vertex outside each arm or the hub can reach that arm’s far end within k steps.Source: §C.13.4 · pp. 86–87

C.13.5 PROOF OF THE MAIN THEOREM

• For fixed k ≥ 2, G_{k,m} is strongly connected with mk + k + 2 vertices and κ_k(G_{k,m}) = m + 1, while (m − 1)/(k + 1) grows without bound.Thus, for any c, m can be chosen so that (m − 1)/(k + 1) > c.Source: §C.13.5 · p. 87
• For k ≥ 2 and t ≥ 1, H_{k,t} is strongly connected on kt + 2k + 2 vertices with κ_k(H_{k,t}) = t + 1.This hub-and-arms family has the same 1/k coefficient as Theorem C.13.1 but loses 1 in the additive constant.Source: §C.13.5 · p. 87

C.14.2 A WEIGHTED LOCAL DECOMPOSITION FOR ONE HYPEREDGE

• For every hyperedge size r, the indicator of a nonconstant coloring is a nonnegative rational combination of weak-ordering conditions with prescribed strict steps.The weights are nonnegative because every subset of [r − 1] occurs as a permutation descent set; the local identity holds coloring by coloring.Source: §C.14 · p. 88, §C.14.2 · p. 90

C.14.1 INTRODUCTION

• For every finite hypertree H, its chromatic symmetric function X_H is F-positive, proving Taylor (2015)’s conjecture.The theorem expresses X_H as a sum of n! fundamental quasisymmetric functions counted with multiplicity.Source: §C.14 · p. 88, §C.14.1 · p. 89

C.14.3 GLUING THE LOCAL IDENTITIES OVER A HYPERTREE

• On a hypertree, gluing the local identities makes each K_Ω a (P_Ω, ω_Ω)-partition enumerator and hence a nonnegative integral combination of fundamental quasisymmetric functions.The chosen local orders form a tree, whose weak and strict edges define the poset and labeling used for the partition enumerator.Source: §C.14.3 · pp. 92–93
• The colorings counted by KΩ are precisely the (PΩ, ωΩ)-partitions: weak and strict oriented edges impose the corresponding inequalities, recovering equation 36 for each hyperedge.The last assertion follows from equation 39.Source: §C.14.3 · p. 93

C.14.4 PROOF OF THE MAIN THEOREM

• Theorem C.14.1 proves that each coefficient aS is a nonnegative integer, and the same construction and theorem apply to hyperforests.The proof interprets the coefficients as coloring counts; the weighted decomposition does not recover Taylor’s combinatorial interpretation, and connectedness is needed only in two lemmas.Source: §C.14.4 · p. 93

C.15.1 INTRODUCTION

• The open problem asks whether Latin squares can contain supercubic numbers of subsquares of fixed order; for order 7, it is the question of whether ζ∗(n, S7) grows faster than cubically.The order-7 case reduces to subsquares isotopic to S7, and the paper answers it affirmatively.Source: §C.15.1 · p. 95
• Random Latin squares almost surely have no proper order-7 subsquare, so the positive result requires an explicit construction.The cited probability is 1 − O(1/n).Source: §C.15.1 · p. 95

C.15 QUARTICALLY MANY FANO SUBSQUARES IN LATIN SQUARES

• ζ(n, 7) = Θ(n^4), and for every n ≥56 some Latin square has more than (n/28)^4 subsquares isotopic to S7.The construction supplies the quartic lower bound, while the cited prior upper bound yields the growth order.Source: §C.15 · p. 94, §C.15.1 · p. 95

C.15.2 THE CONSTRUCTION

• For powers of two q ≥4, an affine lift over Fq gives a Latin square of order 7q with q^4 pairwise distinct subsquares isotopic to S7.The construction uses q^3 F2-linear maps V → Fq and q translations; an affine parameter ensures the diagonal cells close correctly.Source: §C.15.1 · p. 95, §C.15.2 · pp. 96–97

C.15.3 THE UPPER BOUND

• Any three rows and one column of an S7 subsquare determine its full incidence structure, so recording them gives at most n^4 possibilities and proves the upper bound.The generation rule is that two known vertices in different parts determine the third vertex of their triple.Source: §C.15 · p. 94, §C.15.3 · pp. 97–98

• For n ≥56, (n/28)^4 < ζ∗(n, S7), while ζ∗(n, S7) ≤ n^4 for every n.Source: §C.15.4 · p. 98
• When n = 7q for q a power of two, ζ∗(n, S7) ≥ (n/7)^4; the correct constant remains undetermined.Source: §C.15.4 · p. 98
• Every subsquare isotopic to S7 has order 7, yielding ζ(n, 7) = Ω(n^4) by Theorem C.15.1; Browning et al. (2015, Theorem 8) gives ζ(n, 7) = O(n^4).Source: §C.15.4 · p. 98