{"id":"30e5c423-a63d-4661-9be2-066441e92480","arxiv_id":"2506.21286","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The line hypergraphs of generalized Petersen graphs GP(5k+11,2) form infinitely many counterexamples to Lovász's conjecture for r=3, and several quartic graphs give counterexamples for r=4.","lead":"This paper finds infinitely many graphs whose associated hypergraphs break a 50-year-old conjecture by Lovász about matchings and vertex covers. It also produces the first known counterexamples when each edge uses four parts, using a computer search over a new family of graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The infinite family in Theorem 2 rests on computationally asserted base cases, especially k=2, that are neither proved nor certified in the paper.","rationale":"The reader's weakest assumption identifies the computationally verified base cases of Theorem 13 as the load-bearing risk. I agree with that assessment after checking the surrounding proof. The inductive step is carefully constructed: the rotation to i0=n-9 is legitimate by dihedral symmetry, the reduced graph \\tilde G really is GP(5k+11,2), Lemma 10 supplies an empty rung among the five consecutive rungs available, and the constructed set I has the claimed size and independence. The index shifts in (ii) and (iii) map edges correctly, and the boundary edge checks cover all nine connections between the three segments. I found no hidden contradiction in the case where i1=n-5 or in the wrap-around edges a_n a_1, b_{n-1} b_1, b_n b_2. Thus the central proof is sound conditional on the base cases. The concern is precise and testable: if k=2 fails, the induction has no starting point and the infinite family is not established; if k=0 or k=1 fails, the stated theorem and the headline smallest counterexample are false even though a subfamily for k≥2 might survive. Since the reader already assigned CONDITIONAL, my stress-test does not change that verdict; it sharpens the condition by identifying the k=2 case as the one that must be independently verified.","tokens_in":9475,"tokens_out":21437,"duration_ms":218867,"concrete_test":"For each k=0,1,2, independently enumerate every unordered pair of edges {e,f} of GP(5k+11,2), compute the independence number of the graph with the endpoints of e and f deleted using an exact maximum-independent-set solver other than the authors' code, and assert that it equals 4k+8. Also pin a commit of the authors' GitHub repository and rerun their script on the k=2 case to confirm identical output. If all three pass, the induction is properly based; if k=2 fails, Theorem 2's infinite family is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 13 is the engine of Theorem 2. Its inductive step from k to k+1 is internally consistent: after rotating so the avoided 10-rung block is S_{n-9,10}, the graph \\tilde G is GP(5k+11,2), the shifted independent set avoids all boundary edges, and the nine cross-segment edges are handled correctly. No mathematical error was found in that argument. The only unproved input is the sentence in the proof of Theorem 13: 'The cases k=0,1,2 are easily verified computationally.' These are not mere examples; they are the base of the induction. Since the step is stated only for k≥2, the essential base for the infinite family is k=2; k=0 and k=1 are additional claimed members needed for the stated 'every k≥0' and for the 'smallest counterexample of order 22' claim. No in-paper certificate, exhaustive output, or commit-pinned script is provided, only a GitHub link. If the k=2 check is wrong, the induction produces nothing; if k=0 or k=1 is wrong, the theorem's full statement and the smallest-order claim fail even though k≥2 would remain. This is a load-bearing computational premise, not a defect in the graph-theoretic argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper constructs an infinite family of cubic graphs, the generalized Petersen graphs GP(5k+11,2) for k≥0, whose line hypergraphs are counterexamples to Lovász's conjecture for r=3, thereby answering an open question of Clow, Haxell, and Mohar. The proof centers on Theorem 13, which asserts that for any two edges of GP(5k+11,2), removing their endpoints does not change the independence number; together with a Tait coloring and Lemma 7, this implies the line hypergraph is a counterexample. The inductive step of Theorem 13 is proven rigorously for k≥2, while the base cases k=0,1,2 are only asserted to be computationally verified. The paper also presents the first counterexamples for r=4, obtained computationally from Cayley-generalized Petersen graphs, with several specific graphs listed and made available via graph6 strings and code.","tokens_in":9764,"tokens_out":18974,"duration_ms":181894,"significance":"If the computational verifications are correct, this is a substantial advance: it provides the first infinite family of counterexamples to Lovász's conjecture for r=3, greatly improving on the two sporadic examples of Clow et al., and it gives the first counterexamples for r=4. The induction argument in Theorem 13 is elegant and uses classical results on generalized Petersen graphs in a clean, parameter-free way. The paper is commendable for making its computational parts reproducible in principle: the authors provide a GitHub repository with code and graph descriptions. However, the lack of in-paper details or certificates for the load-bearing computational steps prevents the current version from being fully self-contained.","major_comments":[{"comment":"The base cases k=0,1,2 are asserted to be 'easily verified computationally' with only a GitHub link, but since the inductive step is proved only for k≥2, the k=2 case is essential for Theorem 2, and k=0 and k=1 are needed for the full statement 'every k≥0' and for the smallest-order example GP(11,2). This is a load-bearing computational premise rather than a minor remark; please provide a complete verification, such as a table of all edge pairs with the resulting independence numbers, or include the verification script and its output in the paper, and pin the repository to a specific commit.","section":"Section 3, proof of Theorem 13"},{"comment":"The quartic counterexamples are established entirely by computational verification, but the paper only states 'The properties of all of the graphs have been verified computationally' and points to a GitHub repository; it does not specify the exact condition checked, the number of 3-edge subsets tested for each graph, or provide any output or certificate for the listed examples. Since Theorem 3 rests on these checks, please document the verification procedure and provide the relevant code and results so that a reader can reproduce the computation and confirm the claims.","section":"Section 4, Theorem 3"}],"minor_comments":[{"comment":"The phrase 'Out infinite family' should be 'Our infinite family'.","section":"Section 3, first paragraph"},{"comment":"The formula defining S_{i,ℓ} is garbled in the text ('Si,ℓ := Si+ℓ−1 i Rj'); it should be the union of ℓ consecutive rungs, e.g., S_{i,ℓ} = ⋃_{j=i}^{i+ℓ-1} R_j.","section":"Definition 8"},{"comment":"The sentence 'we will imply a natural order 1 < 2 < ... < n on the rungs' should read 'we will impose a natural order'.","section":"Proof of Lemma 12"},{"comment":"The abstract says the counterexample of Clow, Haxell, and Mohar uses the 'line graph' of a 3-regular graph, but it should say 'line hypergraph' to be consistent with the rest of the paper.","section":"Abstract"},{"comment":"For reproducibility, the GitHub repository should be archived (for example, via Zenodo) or at least a commit hash should be provided, so that the code used for the computational verifications is permanently available in the exact version used.","section":"Section 4 and GitHub link"}],"recommendation":"major_revision","confidential_remarks":"The main mathematical construction appears sound: the induction argument in Theorem 13 is coherent and the only serious gap is the unverified computational base cases. The r=4 examples are also computationally asserted and need fuller documentation. I expect the authors can address these points with additional details, so a major revision is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the one thing to know: the infinite family for r=3 is real. The proof is an induction on k, and the inductive step is sound; I checked the gluing and the cross-edge cases. The only place I had to take anything on faith is the computationally asserted base cases k=0,1,2, and that is a small gap, not a fatal one.\n\nWhat's new: Clow, Haxell, and Mohar had two sporadic 3-uniform counterexamples. This paper shows all generalized Petersen graphs GP(5k+11,2) have line hypergraphs violating Lovász's conjecture, starting at order 22. That answers their Question 4.1 in the strongest sense. It also produces the first r=4 examples, via a computer search over Cayley-generalized Petersen graphs, and a 36-vertex cubic Cayley graph, which addresses the \"Cayley\" question. The tables in Section 4 give a nice census.\n\nThe main trick is solid. Lemma 12 is a short pigeonhole argument that after deleting any two edges you still have a 10-rung block untouched; Lemma 10 bounds the independent set on five consecutive rungs; the induction in Theorem 13 then shifts the independent set across the gluing. I don't see a hole in the cross-segment edges listed at the end of Theorem 13. Using the known independence formula for GP(n,2) is legitimate.\n\nThe soft spots are minor but worth noting. The base cases k=0,1,2 for the induction are described only as 'easily verified computationally,' with code linked on GitHub. Since the inductive step is stated for k≥2, the k=2 check is genuinely load-bearing: if it were wrong, the whole induction falls. The code is not pinned to a commit, so a referee can't easily re-run the exact verification. That's easily fixed: include an explicit certificate or a short printed verification in the appendix. Same for the r=4 table: everything is computational, and the search is not claimed to be exhaustive, but the reader should be able to reproduce the checks. I'd like to see a reproducibility note with library versions and a checksum.\n\nOne point where I disagree with the reader's take: the abstract doesn't overstate the r≥4 answer. It says 'specific counterexamples for r=4,' which is exactly what they deliver. The open question of infinite families for r≥4 remains open, but that's not misrepresented.\n\nBottom line: this is a strong, clean contribution to a 50-year-old conjecture. The proof is convincing, the citation to prior work is accurate, and the computational parts are small and verifiable. Send it to a referee; with a request to make the base-case verification reproducible, it should be accepted.","headline":"The r=3 infinite family is real, the induction is sound, and the only real caveat is the computationally asserted base cases, which are a small gap rather than a fatal one.","tokens_in":10291,"tokens_out":3191,"would_cite":true,"duration_ms":35000,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05C69","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the line hypergraphs of the generalized Petersen graphs GP(5k+11,2), for every k≥0, are counterexamples to Lovász's 1975 conjecture on reducing the matching number by deleting r−1 vertices, and it provides the first…","keywords":["Lovász conjecture","Ryser conjecture","hypergraph matching number","line hypergraph","generalized Petersen graphs","independence number","r-partite hypergraphs","counterexample"],"falsifier":"Run an independent computation of α(GP(5k+11,2)−{u,v,w,x}) for all pairs of edges uv,wx when k=0,1,2; if any result is smaller than α(GP(5k+11,2)), then Theorem 13 fails and with it the proof of the infinite family.","tokens_in":9290,"feed_emoji":"♾️","tokens_out":9095,"duration_ms":89587,"temperature":0.7,"pith_summary":"Lovász's conjecture from 1975 says that in any r-partite r-uniform hypergraph one can remove r−1 vertices and thereby shrink the matching number. This paper proves the conjecture false for r=3 in a strong sense: the line hypergraphs of the generalized Petersen graphs GP(5k+11,2), for every k≥0, are counterexamples. The smallest such example comes from a cubic graph on only 22 vertices, far smaller than the two sporadic counterexamples previously known. The paper also provides the first counterexamples for r=4, constructed as line hypergraphs of certain 4-regular Cayley-generalized Petersen graphs. If correct, this shows Lovász's proposed path toward Ryser's conjecture has infinitely many blocking examples at uniformity 3 and at least isolated failures at uniformity 4.","feed_headline":"Infinite family of graphs breaks Lovász's matching conjecture","feed_subtitle":"Smallest is just 22 vertices; r=4 counterexamples follow from a broader construction.","key_machinery":"The line hypergraph L(G) has as vertices the edges of G and as hyperedges the incidence sets S(v); it is r-uniform and r-partite exactly when G is r-regular and r-edge-colorable, and independent sets of G correspond bijectively to matchings of L(G). Lemma 7 converts Lovász's deletion condition into the graph statement α(G−⋃_{e∈S}e)=α(G) for every set S of r−1 edges. Theorem 13 verifies this statement for GP(5k+11,2) by induction, using the known formula α(GP(n,2))=⌊4n/5⌋, the bound that five consecutive rungs contain at most four independent vertices, and the existence of Tait colorings. The induction removes five consecutive rungs, applies the smaller case, and then reassembles a maximum independent set in the larger graph that avoids the two removed edges.","core_discovery":"The paper proves Theorem 2: for every k≥0, the line hypergraph of GP(5k+11,2) is a 3-uniform, 3-partite hypergraph whose matching number cannot be decreased by deleting any two vertices. The core identity is α(GP(5k+11,2)−{u,v,w,x})=α(GP(5k+11,2)) for any two edges uv,wx. Because the graph is 3-edge-colorable, this identity makes the line hypergraph a counterexample to Lovász's conjecture. The paper also proves Theorem 3: several 4-regular graphs, including CGP(2,Z35;5,7;15,0) on 70 vertices, give the first counterexamples for r=4.","pith_inferences":["Editorial extension: the gluing construction in Theorem 13 is not obviously tied to the parameter 2 in GP(n,2), so similar infinite families may exist among other generalized Petersen graphs; a computer search over GP(n,k) with n≡1 mod 5 would test this directly.","Editorial extension: because the r=4 examples are found by a finite computer search over Cayley-generalized Petersen graphs, and the paper leaves open whether an infinite r=4 family exists, the natural next question is whether such an infinite family exists; searching permutation graphs with additional structural assumptions would be a first place to look.","Editorial extension: the weakened version of Lovász's conjecture, which allows deleting k(r−1) vertices to decrease the matching number by at least k, is verified by the authors for small r=3 counterexamples but not for r=4; checking it for the 70-vertex quartic example is a concrete open computation.","Editorial extension: all counterexamples here are line hypergraphs, so the failure of Lovász's conjecture might be specific to this construction; testing non-line-hypergraph r-partite hypergraphs for analogous failures would clarify how broadly the conjecture fails."],"forward_implications":["For every k≥0, the matching number of the line hypergraph of GP(5k+11,2) stays unchanged after any two vertices are removed, so Lovász's conjecture fails infinitely often for r=3.","The smallest member of this infinite family is built from a 22-vertex cubic graph, giving an explicit counterexample much smaller than the prior 102-vertex example.","The r=4 counterexamples, starting with a 70-vertex quartic graph, show that the failure is not confined to uniformity 3.","None of the constructed hypergraphs contradict Ryser's conjecture or are extremal for it, so Ryser's conjecture can still hold even though this route to it is blocked.","Some of the counterexamples are Cayley graphs and some are not, so edge-transitivity and the Cayley property are not essential to the phenomenon."],"supporting_citations":[{"why":"Supplies the earlier r=3 counterexamples, the lemma translating deletion in the line hypergraph to independence in the graph, and the open questions that motivate the paper.","marker":"[8]"},{"why":"Provides the independence-number formula α(GP(n,2))=⌊4n/5⌋ and the bound on five consecutive rungs that the induction uses.","marker":"[14]"},{"why":"Proves that every generalized Petersen graph except GP(5,2) has a Tait coloring, making GP(5k+11,2) 3-edge-colorable and its line hypergraph 3-partite.","marker":"[6]"},{"why":"Introduced the generalized Petersen graphs that form the infinite family used for the r=3 counterexamples.","marker":"[13]"},{"why":"Stated the 1975 Lovász conjecture that this paper disproves.","marker":"[24]"}],"fun_headline_variants":["Infinite counterexample family to Lovász's conjecture","Smallest Lovász counterexample uses only 22 vertices","Lovász's conjecture fails for infinite family","Counterexamples for Lovász's conjecture at r=3 and r=4","Infinite family of 22-vertex graphs breaks Lovász's conjecture"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The infinite family proof is an induction whose three base cases k=0,1,2 are asserted to be 'easily verified computationally' but are not shown in the paper; if any of those three checks is wrong, the induction has no valid base and Theorem 2 collapses.","fun_headline_variants_meta":{"raw":{"variants":["Infinite counterexample family to Lovász's conjecture","Smallest Lovász counterexample uses only 22 vertices","Lovász's conjecture fails for infinite family","Counterexamples for Lovász's conjecture at r=3 and r=4","Infinite family of 22-vertex graphs breaks Lovász's conjecture"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000699,"raw_usage":{"total_tokens":3088,"prompt_tokens":804,"completion_tokens":2284,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":420,"completion_tokens_details":{"reasoning_tokens":2200}},"tokens_in":420,"tokens_out":2284,"duration_ms":19730,"temperature":1.0,"reasoning_tokens":2200,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:28:43.987079+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an independent computation of α(GP(5k+11,2)−{u,v,w,x}) for all pairs of edges uv,wx when k=0,1,2; if any result is smaller than α(GP(5k+11,2)), then Theorem 13 fails and with it the proof of the infinite family.","supporting_citations":[{"cited_title":"A Counterexample to a Conjecture of Lov\\'asz","cited_arxiv_id":"2505.05339","evidence_quote":"Supplies the earlier r=3 counterexamples, the lemma translating deletion in the line hypergraph to independence in the graph, and the open questions that motivate the paper."},{"cited_title":"The Independence Number for the General- ized Petersen Graphs","cited_arxiv_id":null,"evidence_quote":"Provides the independence-number formula α(GP(n,2))=⌊4n/5⌋ and the bound on five consecutive rungs that the induction uses."},{"cited_title":"Every generalized Petersen graph has a Tait col- oring","cited_arxiv_id":null,"evidence_quote":"Proves that every generalized Petersen graph except GP(5,2) has a Tait coloring, making GP(5k+11,2) 3-edge-colorable and its line hypergraph 3-partite."},{"cited_title":"Self-dual configurations and regular graphs","cited_arxiv_id":null,"evidence_quote":"Introduced the generalized Petersen graphs that form the infinite family used for the r=3 counterexamples."},{"cited_title":"On minimax theorems of combinatorics (Doctoral thesis, in Hun- garian)","cited_arxiv_id":null,"evidence_quote":"Stated the 1975 Lovász conjecture that this paper disproves."}],"review_version":1}