{"id":"d8501a2b-2ce6-4759-8566-a159d2ed4833","arxiv_id":"2501.04297","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new graph product and a tensor-based matrix construction yield new infinite families of graphs whose minimum number of distinct eigenvalues equals two.","lead":"This math paper invents a new way to combine two graphs, the 'modified strong product', and shows how to build matrices with only two distinct eigenvalues for the resulting graphs. The construction unifies several known families and produces new infinite families, though one of the claimed hypergraph families has a flawed proof.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 11(a,b) assigns isolated vertices diagonal 1, giving A_i eigenvalues {1, l-1, -1}; the claimed two-eigenvalue conclusion is not established for l ≥ 3.","rationale":"The reader's weakest assumption is precisely where I land. After independently tracing the proofs of Theorems 7, 8, and 11, the tensor-sum mechanism in Lemmas 3–6 is sound: Lemma 3's Householder construction supplies the needed J_i's, Lemma 5's eigenvectors are independent, and Lemma 6 correctly transfers block patterns. Theorem 7 works because a 1-factor has no isolated vertices, so each A_i has spectrum {-1,1}. Theorem 8 works because diagonal 1 is placed only on vertices missed by a color, and with k+1 colors every vertex is missed, while the spectrum of a matching plus isolated diagonal-1 vertices is still {-1,1}. The broken step is Theorem 11(a,b): diagonal 1 on missed vertices puts an eigenvalue 1 into A_i, and since l-1 differs from 1 for l≥3, Lemma 5 yields three distinct eigenvalues. In both cases those missed vertices necessarily exist. This invalidates the claimed hypergraph families and weakens the abstract's unifying claim. I do not see deeper problems in the framework; the flaw is localized and potentially repairable, so the conditional verdict remains appropriate rather than a full rejection. The K_1 edge case in Theorem 8 is a minor secondary overclaim.","tokens_in":7601,"tokens_out":13468,"duration_ms":142416,"concrete_test":"Instantiate Theorem 11(a) with the 3-uniform linear hypergraph H having edges {1,2,3}, {1,4,5}, {2,4,6}, {3,5,6}; H has maximum degree k=2 and chromatic index c=4>k. Form the four matrices A_i exactly as in the proof and compute each spectrum: every A_i is a K_3 block plus two 1×1 blocks, so its eigenvalues are {2,-1,1}. By Lemma 5, M=Σ A_i⊗J_i then has three distinct eigenvalues, contradicting the proof's claim that only two occur. Recomputing this spectrum directly settles whether Theorem 11(a) holds as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing defect is in the proof of Theorem 11(a,b). Each A_i is defined with diagonal entry 1 at every vertex not incident to any hyperedge of color i. A vertex missed by color i is therefore a 1×1 all-ones block with eigenvalue 1. A color class of an l-uniform linear hypergraph is a disjoint union of K_l's plus such isolated 1×1 blocks, so its spectrum is {l-1, -1, 1}, not the asserted {l-1, -1}. For l=2 these values coincide, but for every l≥3 the value 1 is a third distinct eigenvalue. In the settings of parts (a) and (b), every vertex is missed by some color—in (a) because c>k, and in (b) because a color is added—so the extra eigenvalue genuinely occurs. Lemma 5 then gives three distinct eigenvalues for M, so the construction does not prove q(G⊠K_c)=2 or q(G⊠K_{c+1})=2. This false premise is load-bearing for the hypergraph families advertised in the abstract. The defect is localized: Theorem 7 and the k-regular case (c) avoid the 1×1 blocks, and Theorem 8 supplies diagonal entries only in a way that keeps the spectrum at {-1,1}; but Theorem 11(a,b) needs repair before those infinite families are established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a variant of the strong graph product, called the modified strong product, and a tensor-sum construction M = Σ(A_i ⊗ J_i) built from orthogonal matrices. Lemma 5 gives the eigenvalues of M in terms of the spectra of the A_i, and Lemma 6 shows that the pattern of M is controlled by the entrywise sum of the A_i. The authors use this framework to claim new infinite families of graphs with q(G)=2, including modified strong products of 1-factorable regular graphs with cliques, strong products of bounded-degree graphs with cliques, and graphs arising from linear hypergraphs. Theorems 7, 8, and 11 are presented as the main results, with Theorem 11 subdivided into three cases (a), (b), and (c).","tokens_in":7918,"tokens_out":8837,"duration_ms":84672,"significance":"The tensor-sum framework in Lemmas 3-6 is elegant and correct, and the paper provides explicit, self-contained matrix constructions. If valid, the results would unify several known families of two-eigenvalue graphs, such as double ended candles and closed candles, and add new infinite families from 1-factorable graphs and linear hypergraphs. The constructive nature of the proofs is a strength, as is the explicit use of Householder matrices to produce the idempotent, mutually orthogonal J_i. However, the proof of Theorem 11(a,b) contains a load-bearing spectral error: the matrices A_i there have eigenvalue 1 from vertices missed by a color, giving three distinct eigenvalues for l≥3. This means the advertised hypergraph families are not established as written, though the rest of the paper's framework and the k-regular case (c) remain sound.","major_comments":[{"comment":"The proof defines A_i with diagonal entry 1 at every vertex not incident to a hyperedge of color i, and then states that the eigenvalues of M are −1 and l−1 from Lemma 5 and Lemma 9. This is incorrect for l≥3. A vertex missed by color i gives a 1×1 block [1] with eigenvalue 1. Since each color class is a disjoint union of K_l's (eigenvalues l−1 and −1) plus these isolated 1×1 blocks, the spectrum of A_i is {l−1, −1, 1}, not {l−1, −1}. In cases (a) and (b), every vertex is missed by at least one color (because c>k in (a), and an extra color is added in (b)), so the eigenvalue 1 genuinely appears. Lemma 5 then yields M with eigenvalues −1, l−1, and 1, which are three distinct values for every l≥3. Consequently the claims q(G⊠K_c)=2 and q(G⊠K_{c+1})=2 are not proved by this construction. The defect is load-bearing for the hypergraph families advertised in the abstract; a repair is needed, for example by restricting to l=2 or by modifying the diagonal entries so that missed vertices do not introduce a new eigenvalue while preserving the pattern argument.","section":"Section 3, Theorem 11(a,b), proof"}],"minor_comments":[{"comment":"In cases (a) and (b), the sum M is written as (A_1 ⊗ J_1) + ... + (A_k ⊗ J_k), but the number of colors is c in case (a) and c+1 in case (b), not the maximum degree k. This index error should be corrected for the pattern argument in Lemma 6 to apply with the correct number of matrices.","section":"Section 3, Theorem 11 proof"},{"comment":"The statement 'If connected G has max degree k, then q(G ⊠ K_{k+1}) = 2' fails for G = K_1, where k=0 and q(K_1 ⊠ K_1) = q(K_1) = 1. The theorem should assume k≥1, or the edgeless connected graph should be excluded or treated separately.","section":"Section 3, Theorem 8"},{"comment":"In the even-k case, the sentence 'the proof will proceed precisely as in the odd case' is too terse: because the entries of u are not constant, the claim that no diagonal entry of (1 − u_K^T u_K) u_K u_K^T equals 1/4 needs a short verification. This is true, but the argument should be spelled out.","section":"Section 2, Lemma 3"},{"comment":"The text says 'the pattern of M is determined by A_1 + · · · + A_k = B', but there are k+1 matrices in the construction, so this should be A_1 + · · · + A_{k+1} = B.","section":"Section 3, Theorem 8 proof"},{"comment":"The phrase 'every vertex of G fails to be incident to some color' is awkward; it should read 'every vertex of G is not incident to some color'.","section":"Section 3, Theorem 8 proof"}],"recommendation":"major_revision","confidential_remarks":"The paper's central construction is novel and mostly correct, and the defect in Theorem 11(a,b) is localized. The authors may be able to fix it by restricting to l=2 or by finding a different way to handle vertices missed by a color without introducing a third eigenvalue; if they cannot, the hypergraph families in parts (a) and (b) should be removed from the abstract and the paper. The K_1 edge case in Theorem 8 is minor. I recommend major revision rather than rejection because the remaining results and the framework are valuable and the flawed cases appear repairable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the modified strong product and the tensor-sum method are real and give new families, but the proof of Theorem 11(a,b) has a load-bearing eigenvalue-count error for l≥3.\n\nThe construction is genuinely new: G⋈H with adjacency A_G⊗(A_H+I), and the trick of using a Householder Q to get rank-one projectors J_i works cleanly. Lemma 5 and Lemma 6 are correct, and they make Theorem 7 (1-factorable G) and Theorem 8 (max degree k) go through. I checked the spectra: in Theorem 8, each A_i is a matching plus diagonal 1's on missed vertices, which still has only {1,-1}. So that part is solid, aside from G=K_1 which trivially gives q=1. The remark that the double-ended and closed candles are P_k⋈K_2 and C_k⋈K_2 is a nice unification.\n\nThe soft spot is Theorem 11(a,b). There, A_i puts a 1 on the diagonal for every vertex not incident to a hyperedge of color i. In an l-uniform linear hypergraph, a color class is a disjoint union of K_l's plus those isolated vertices with diagonal 1. So the eigenvalues of A_i are {l-1, -1, 1}, not {l-1, -1} as claimed. For l=2, 1 = l-1, so the argument survives; for every l≥3 it gives M three distinct eigenvalues, so q(G⊠K_c)=2 and q(G⊠K_{c+1})=2 are not proven. Since in cases (a) and (b) every vertex is missed by some color, this is not a corner case. Part (c) is fine: k-regularity with c=k means no vertex is missed, so A_i really is a union of K_l's.\n\nThe defect is localized and repairable—restrict to l=2 or require each vertex incident to every color—but as written the abstract overclaims. The rest of the paper is still worth a serious referee: Theorems 7 and 8 are new infinite families, and the tensor-sum framework will likely be reused. I'd recommend sending it back for revision rather than rejecting.","headline":"The new product and tensor method are legitimate, and Theorems 7–8 hold, but Theorem 11(a,b) overclaims because the A_i's isolated diagonal 1's introduce a third eigenvalue for l≥3.","tokens_in":8409,"tokens_out":5275,"would_cite":true,"duration_ms":45365,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C76","15A18"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a new modified strong product and a companion tensor-sum construction generate infinite families of graphs whose minimum number of distinct eigenvalues equals two.","keywords":["q(G)","minimum number of distinct eigenvalues","modified strong product","graph products","chromatic index","Kronecker product","linear hypergraphs","candle graphs"],"falsifier":"Take an $l$-uniform linear hypergraph with maximum degree $k$, chromatic index $c>k$, and at least one vertex that is incident to no hyperedge of some color $i$; for $l\\ge 3$, the matrix $A_i$ in Theorem 11(a) then has eigenvalues $l-1$, $-1$, and $1$, so Lemma 5 forces $M$ to have three distinct eigenvalues. Computing this example directly would determine whether Theorem 11(a) holds as stated and would reveal the exact missing hypothesis.","tokens_in":7394,"feed_emoji":"🧩","tokens_out":9773,"duration_ms":87595,"temperature":0.7,"pith_summary":"The paper studies $q(G)$, the minimum number of distinct eigenvalues that a symmetric matrix can have while respecting the zero-nonzero pattern of a graph $G$. It introduces a modified strong product $G\\bowtie H$, whose adjacency matrix is $A_G\\otimes (A_H+I)$, and a block tensor-sum construction $M=\\sum_{i=1}^k (A_i\\otimes J_i)$ whose eigenvalues are forced into a two-element set. The main theorems prove that $G\\bowtie K_k$ has $q=2$ for every $k$-regular $1$-factorable graph $G$, that $G\\boxtimes K_{k+1}$ has $q=2$ for every connected graph of maximum degree $k$, and that several families built from linear hypergraphs also reach $q=2$. If correct, this supplies infinite families of two-eigenvalue graphs and shows that the previously known candle families are special cases of one construction.","feed_headline":"New graph product builds two-eigenvalue graphs","feed_subtitle":"Candle graphs and other known examples all come from one tensor-product construction.","key_machinery":"The load-bearing objects are the modified strong product $G\\bowtie H$ (the strong product without the vertical edges of $H$, so its adjacency matrix is $A_G\\otimes(A_H+I)$), the tensor-sum matrix $M=\\sum_i A_i\\otimes J_i$, and the auxiliary orthogonal projections $J_i=QD_iQ^T$ built from a Householder orthogonal matrix $Q$. Lemma 5 carries the spectral argument: the mutually annihilating $J_i$ make the eigenvectors $v_{i,\\ell}\\otimes q_i$ diagonalize $M$ with the eigenvalues of the individual $A_i$. Lemma 6 carries the pattern argument: the support of $M$ is completely controlled by $A_1+\\cdots+A_k$, producing full blocks where that sum has entries strictly between $0$ and $k$, identity blocks where it equals $k$, and zero blocks where it is $0$.","core_discovery":"The central claim is that two-eigenvalue graphs can be manufactured by a tensor-sum sandwich: choose an orthogonal matrix $Q$, set $J_i=QD_iQ^T$ for the diagonal rank-one matrices $D_i$, and form $M=\\sum_i A_i\\otimes J_i$. Because $J_iJ_j=0$ for $i\\ne j$, every vector $v\\otimes q_i$ with $v$ an eigenvector of $A_i$ and $q_i$ a column of $Q$ is an eigenvector of $M$ with the same eigenvalue; hence $M$ has only two distinct eigenvalues whenever each $A_i$ does. Lemma 6 then recovers the graph pattern from the ordinary sum $A_1+\\cdots+A_k$, so $M$ can be engineered to be a matrix in $S(G\\bowtie K_k)$, $S(G\\boxtimes K_{k+1})$, or the corresponding hypergraph product. The paper uses this to establish Theorems 7, 8, and 11.","pith_inferences":["A natural extension, not pursued in the paper, is to let the second factor $H$ be any graph whose adjacency matrix has exactly two distinct eigenvalues; the same tensor-sum template would then potentially produce $G\\bowtie H$ and $G\\boxtimes H$ families with $q=2$.","Because any $q=2$ graph can realize any prescribed pair of eigenvalues (a fact the paper cites), the edge-partition strategy could in principle work with arbitrary two-eigenvalue pieces rather than only matchings and cliques; what is missing is a pattern-control lemma for weighted pieces.","A reader wanting a testable version of the hypergraph claims could add the hypothesis that every vertex is incident to a hyperedge of every color; under that extra condition the construction appears to go through and yields further infinite families.","Since the product pattern is read off from an additive sum of 0-1 matrices, iterating the construction may give towers of two-eigenvalue graphs, but the paper leaves the iteration behavior open."],"forward_implications":["Every $k$-regular graph whose edge set is the disjoint union of $k$ perfect matchings yields a graph $G\\bowtie K_k$ with exactly two attainable eigenvalues; cycles, complete graphs of odd order, and many other regular graphs qualify.","Every connected graph of maximum degree $k$ can be embedded as a factor in $G\\boxtimes K_{k+1}$ with $q=2$, so irregularity of the base graph is no obstruction once a $K_{k+1}$ factor is added.","Linear hypergraphs with chromatic index $c$ supply further infinite families, including $G\\boxtimes K_c$ when $c>k$ and $G\\boxtimes K_{c+1}$ when $c=k$.","The previously studied double-ended candles and closed candles are, respectively, $P_k\\bowtie K_2$ and $C_k\\bowtie K_2$, so their $q=2$ status follows from the new product rather than from case-by-case analysis.","The construction shows that $q=2$ is preserved under a kind of product operation in which the second factor contributes only a clique or complete graph structure, giving a systematic route to new examples."],"supporting_citations":[{"why":"Defines $q(G)$ and supplies the eigenvalue-rescaling lemma used in the paper's closing extension discussion.","marker":"[3]"},{"why":"Introduces the double-ended candle family with $q=2$, which the paper recovers as $P_k\\bowtie K_2$.","marker":"[5]"},{"why":"Introduces the closed candle family with $q=2$, which the paper recovers as $C_k\\bowtie K_2$.","marker":"[7]"},{"why":"Original source of the parameter $q(G)$ and of the two-eigenvalue question for graphs.","marker":"[11]"}],"fun_headline_variants":["Two eigenvalues via new graph product","Infinite two-eigenvalue graphs via product","Graph product yields two-eigenvalue families","Tensor trick builds two-eigenvalue graphs","New construction for two-eigenvalue graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction depends on being able to choose the edge-color pieces so that every corresponding 0-1 matrix $A_i$ has only two eigenvalues, and in the hypergraph cases this is not guaranteed by the stated hypotheses: a vertex missed by a color contributes a diagonal $1$, which for $l\\ge 3$ adds a third eigenvalue to $A_i$.","fun_headline_variants_meta":{"raw":{"variants":["Two eigenvalues via new graph product","Infinite two-eigenvalue graphs via product","Graph product yields two-eigenvalue families","Tensor trick builds two-eigenvalue graphs","New construction for two-eigenvalue graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000259,"raw_usage":{"total_tokens":1515,"prompt_tokens":802,"completion_tokens":713,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":418,"completion_tokens_details":{"reasoning_tokens":648}},"tokens_in":418,"tokens_out":713,"duration_ms":7099,"temperature":1.0,"reasoning_tokens":648,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:38:49.257693+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take an $l$-uniform linear hypergraph with maximum degree $k$, chromatic index $c>k$, and at least one vertex that is incident to no hyperedge of some color $i$; for $l\\ge 3$, the matrix $A_i$ in Theorem 11(a) then has eigenvalues $l-1$, $-1$, and $1$, so Lemma 5 forces $M$ to have three distinct eigenvalues. Computing this example directly would determine whether Theorem 11(a) holds as stated and would reveal the exact missing hypothesis.","supporting_citations":[{"cited_title":"Minimum number of distinct eigenvalues of graphs","cited_arxiv_id":null,"evidence_quote":"Defines $q(G)$ and supplies the eigenvalue-rescaling lemma used in the paper's closing extension discussion."},{"cited_title":"Sparsity of graphs that allow tw o distinct eigenvalues","cited_arxiv_id":null,"evidence_quote":"Introduces the double-ended candle family with $q=2$, which the paper recovers as $P_k\\bowtie K_2$."},{"cited_title":"Graphs with Bipartite Complement that Admit Two Distinct Eigenvalues","cited_arxiv_id":"2411.12917","evidence_quote":"Introduces the closed candle family with $q=2$, which the paper recovers as $C_k\\bowtie K_2$."},{"cited_title":"On the minimum num ber of distinct eigenvalues for a symmetric matrix whose graph is a given tree","cited_arxiv_id":null,"evidence_quote":"Original source of the parameter $q(G)$ and of the two-eigenvalue question for graphs."}],"review_version":1}