{"id":"ccacef68-922a-4622-9380-75ba15d8ecaa","arxiv_id":"2607.17829","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A thesis compiling results that pyramid graphs are determined by their adjacency spectrum, that transitivity of generalized-Hamming graphs and complements is classified, and that closed-form Lovász theta values follow in edge-transitive cases.","lead":"This mathematics thesis compiles the author's results on spectral graph determination and on symmetry properties of generalized Hamming graphs. It introduces the 'graphs of pyramids' family, proves they are spectral-unique, and classifies edge and distance transitivity of Hamming-type graphs and their complements.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of strict spectral inequality in Thm 4.4.10(2) relies on a false claim about additive characters; the inequality itself appears to hold in the needed range, making this a repairable proof gap rather than a refutation.","rationale":"The thesis compiles three prior papers, and the reader's CONDITIONAL verdict reflects both the lack of new results beyond the cited publications and a set of repairable errors. My stress-test focused on the transitivity classification, which is the central claim. Theorem 4.1.1 is proved combinatorially in Section 4.3 and appears sound: the edge-invariant F(v) is correctly derived, the counting identities in (4.3.3)–(4.3.12) check out, and the exceptional distance-transitive cases (d=2, (2,3), (2,n)) are handled correctly. The complement classification, Theorem 4.1.2, depends on the spectral decomposition in Theorem 4.4.10. The reader's weakest-assumption identification is on target: the strict inequality γ_1 < γ_m is load-bearing because it makes the Lagrange-type polynomials in (4.5.1) and (4.5.10) well-defined. My scrutiny confirms the written proof of this inequality contains a false overgeneralization about additive characters: for q=2, x = all-ones, and an even weight class, the character is identically 1. However, the specific parameters used in Lemmas 4.5.1 and 4.5.2 always have x of weight m−1 ≤ n−2, so the all-ones obstruction is never reached. Small exact checks (q=2, n up to 6) confirm γ_1 < γ_m in every needed case, and the same is expected for larger parameters by known Krawtchouk bounds. Other noted issues—the join-versus-disjoint-union typo in Theorem 2.4.7 and the H_4 spectrum misprint—are unrelated to the main classification. The central mathematical claim is therefore very likely correct, but the manuscript currently lacks a valid written proof of the key strict inequality, and several typos should be corrected. This does not change the reader's CONDITIONAL verdict, which already required corrections; hence UNCHANGED.","tokens_in":66823,"tokens_out":36566,"duration_ms":284385,"concrete_test":"Run an exact-arithmetic sweep: for all prime powers q ≤ 7 and all 2 ≤ d ≤ n ≤ 25, compute γ_j from the closed form (4.4.15) and verify γ_1 < γ_m for every 2 ≤ m ≤ n−1, and also verify γ_1 ≠ γ_n whenever q ≠ 2 or d is even. If any violation appears, the complement non-transitivity proofs in Lemmas 4.5.1–4.5.2 collapse; a clean sweep indicates the classification is true and the paper only needs a corrected proof of Theorem 4.4.10(2).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.4.4, Theorem 4.4.10(2) claims γ_1 < γ_m for 2 ≤ m ≤ n−1. The proof bounds K_{d−1}(m−1; n−1, q) by the triangle inequality and asserts that equality would force the additive character χ_y(x) to be identically 1 on all y of weight d−1, which 'cannot' happen for a nontrivial character. This assertion is false as stated: for q=2, x = 1^N, and d−1 even, every y of even weight satisfies ⟨x,y⟩=0, so χ_y(x)=1 on the entire weight class. The needed instance only has x of weight m−1 ≤ n−2 (because m ≤ n−1), where the all-ones obstruction is absent, but the written proof does not invoke this restriction. Consequently, the strict inequality used to define the denominators in (4.5.1) and (4.5.10) is not established by the argument as written. Since Lemmas 4.5.1 and 4.5.2 provide the entire non-transitivity proof for the complement graphs, a failure of this inequality at some parameter set would invalidate Theorem 4.1.2. The fix is a correct proof that K_k(s; n, q) < K_k(0; n, q) for 1 ≤ s ≤ n−1, which follows from standard Krawtchouk-bounds once the full-weight vector is excluded; independent small-parameter checks indicate the inequality does hold in the required range.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This Master's thesis treats two themes in algebraic graph theory. The first part surveys spectral graph determination and contains new proofs that complete bipartite graphs and Turán graphs are determined by their adjacency spectrum, together with a proof that the 'graphs of pyramids' T_{n,k}=K_k∨\\overline{K_{n-k}} are DS. The second part classifies the parameters (q,n,d) for which the generalized-Hamming graph G_{q,n,d} and its complement are edge-transitive or distance-transitive, and derives closed-form Lovász theta values in the edge-transitive cases. The main results are largely reproduced from the author's published or submitted papers with his co-authors, and the thesis adds a survey of cospectral constructions and open problems.","tokens_in":67054,"tokens_out":33956,"duration_ms":293408,"significance":"If the proof gaps are repaired, the transitivity classification in Theorems 4.1.1 and 4.1.2 is a useful contribution: it completely identifies the highly symmetric members of the generalized-Hamming family and feeds directly into the closed-form Lovász theta computations of Theorem 4.7.1, which are genuinely valuable because the SDP formulation on q^n vertices is exponential in n. The pyramid-graph DS theorem is a small but elegant result, proved with Schur complements and interlacing. The survey portions are broad and generally accurate. On the other hand, the thesis's own proofs contain several load-bearing errors, and the corollary on complete bipartite DS graphs is plainly false; the current version is not acceptable without revision.","major_comments":[{"comment":"The proof of the 'only if' direction defines G=K_{a,b}∨K_r with r=p+q−a−b and asserts in (2.4.6) that its adjacency spectrum equals that of K_{p,q}. This is false: for r>0 the join contains triangles, so G is not bipartite and cannot be cospectral with a complete bipartite graph; moreover the displayed spectrum has zero multiplicity pq−2, which should be p+q−2. The intended construction must be the disjoint union K_{a,b}∪\\overline{K_r}, whose spectrum is {−√pq, [0]^{p+q−2}, √pq}. As written, the proof of Theorem 2.4.7(2) does not establish the characterization.","section":"§2.4.2, Theorem 2.4.7(2)"},{"comment":"The proof states that A(P_3) has rank 3; the adjacency matrix of P_3 has rank 2, so the interlacing argument used to exclude P_3 as an induced subgraph is invalid. The subsequent conclusion that a graph cospectral with K_{p,q} has the form K_{a,b}∪H with H empty is not derived: one needs an explicit argument, for example via Theorem 2.4.22 or via the fact that the spectrum has only two nonzero eigenvalues, that a connected bipartite graph with exactly one positive eigenvalue is complete bipartite. This is a load-bearing step for Theorem 2.4.7.","section":"§2.4.2, Theorem 2.4.7(1)"},{"comment":"The corollary is false as stated. On n=6 vertices both K_{1,5} and K_{2,4} are DS: for K_{1,5}, {1,5} is the unique minimizing factor pair of 5, and for K_{2,4}, {2,4} is the unique minimizing factor pair of 8. The proof conflates the number n of vertices with the product pq; the DS condition of Theorem 2.4.7 involves factorizations of pq, not factorizations of n. The corollary and its proof should be corrected or removed.","section":"§2.4.2, Corollary 2.4.9"},{"comment":"The proof of the strict inequality γ_1<γ_m asserts that a nontrivial additive character cannot be identically 1 on all vectors of a fixed positive weight. This is false in general: over F_2, for x=1^N and even weight d−1, every y of weight d−1 has trivial inner product with x. In the application one has 1≤w_H(x)=m−1≤n−2, so the all-ones obstruction is absent, but the written proof does not invoke this restriction. Since the denominators in (4.5.1) and (4.5.10) depend on γ_1−γ_m, the non-transitivity proofs in Lemmas 4.5.1 and 4.5.2, and hence the corresponding direction of Theorem 4.1.2, rest on an unproved assertion. The gap is repairable by proving K_{d−1}(s;n−1,q)<K_{d−1}(0;n−1,q) for 1≤s≤n−2, but the current text is incomplete.","section":"§4.4.4, Theorem 4.4.10(2)"}],"minor_comments":[{"comment":"In Definition 2.4.10 and throughout the join constructions, K_r is used for the edgeless graph, while the notation list defines K_n as the complete graph. Please introduce \\overline{K_n} and use it consistently; this ambiguity contributes to the error in the proof of Theorem 2.4.7.","section":"§2.4.10 / notation"},{"comment":"The claim that G has one eigenvalue strictly smaller than −1 is false for k=n−1, where T_{n,k}≅K_n has no eigenvalue below −1. The proof of Lemma 3.4.10 only needs the 'at most one' version, so the statement should be weakened accordingly.","section":"§3.4, Lemma 3.4.6(3)"},{"comment":"The proof uses connectivity of the complement graph to conclude that γ_0 is a simple eigenvalue, but this connectivity is not proved or referenced. It should be stated explicitly for the parameter range considered.","section":"§4.5, Lemma 4.5.1"},{"comment":"In the final summary of cases, the text attributes the case 'q=2 and 1<d<n−1' to Lemma 4.5.1, but the odd-d subcase is handled by Lemma 4.5.2; the attribution should be adjusted for clarity.","section":"§4.5, completion of Theorem 4.1.2"},{"comment":"The proof that the map φ is an automorphism of G checks that edges are mapped to edges but leaves implicit that a bijective edge-preserving map preserves non-edges; this should be stated for completeness.","section":"§4.5, Lemma 4.5.4"}],"recommendation":"major_revision","confidential_remarks":"The thesis is essentially a compilation of the author's published/submitted papers; the standalone novelty is moderate, but the transitivity classification and theta formulas are worth publishing if the proof gaps are closed. The most serious technical issue is the invalid character argument in Theorem 4.4.10(2); it appears to be repairable, and the inequality itself is likely correct in the needed range. Corollary 2.4.9, however, is demonstrably false and must be fixed before the thesis can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: read Chapter 4, not the thesis as a new contribution. The genuinely valuable result is the classification of edge- and distance-transitivity for generalized-Hamming graphs and their complements, with the closed-form Lovász theta formulas as a nice payoff. Chapter 3's pyramid-graph DS proof is a clean piece of work. Chapter 2 is a competent survey with alternative proofs of known results, but nothing there is new.\n\nThe soft spots are mostly in the writing. The cospectral mate in Theorem 2.4.7 is written as a join K_{a,b} ∨ K_r, which is wrong as stated; it should be a disjoint union. The eigenvalue list for H_4 has a misprint. These are minor and repairable.\n\nThe one substantive gap is in the proof of Theorem 4.4.10(2). The strict inequality γ_1 < γ_m is justified by claiming a nontrivial additive character cannot be identically 1 on all vectors of a fixed weight. That claim is false as stated: for q=2, x the all-ones vector, and d−1 even, the character is 1 on every weight class. In the actual application x has weight m−1 ≤ n−2, so the all-ones obstruction is absent, and the inequality likely holds by standard Krawtchouk bounds. So this is a repairable proof gap, not a refutation, but the proof as written does not establish what Lemmas 4.5.1 and 4.5.2 need.\n\nThe thesis is honest about provenance: it says plainly that each research chapter reproduces one of the author's prior papers. That is fine for a thesis, but it means this arXiv submission is a compilation rather than a new contribution. The underlying science appears defensible; the classification claims are plausible and the spectral arguments are mostly sound once the gap is patched.\n\nWho gets value from this? Someone wanting a self-contained tour of spectral determination plus the transitivity classification, or someone who wants the theta formulas without re-deriving them. It deserves a serious referee if submitted as a paper, but only after the proof of Theorem 4.4.10(2) is fixed and the notational errors cleaned up. I would not desk-reject it.","headline":"A mostly honest thesis-compilation: the transitivity classification is the real contribution, but the arXiv version has repairable proof gaps and does not itself advance the field beyond the author's own published papers.","tokens_in":67661,"tokens_out":1549,"would_cite":false,"duration_ms":18019,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C25","05E30","05C12"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that for a prime power $q$ and $2 \\le d \\le n$, the generalized-Hamming graph $G_{q,n,d}$ is edge-transitive if and only if it is distance-transitive, with the precise parameter list $d=2$, $(q,d)=(2,3)$, or…","keywords":["spectral graph theory","graphs determined by spectrum","generalized-Hamming graphs","edge-transitivity","distance-transitivity","association schemes","Krawtchouk polynomials","Lovász theta function"],"falsifier":"A direct automorphism search on $\\overline{G}_{2,5,4}$ (the complement of the generalized-Hamming graph with $q=2$, $n=5$, $d=4$) should find no automorphism sending the edge from $00000$ to $11111$ onto the edge from $00000$ to $11110$, since this parameter set is excluded; finding one would refute the classification.","tokens_in":66524,"feed_emoji":"🕸️","tokens_out":7509,"duration_ms":59360,"temperature":0.7,"pith_summary":"The thesis has two strands. In spectral determination it proves that graphs of pyramids are determined by their adjacency spectrum, that the star $S_n$ is determined by its spectrum exactly when $n-1$ is prime, and gives new proofs that complete bipartite and Turán graphs are spectrally determined. In the transitivity strand, the central result is a complete classification: the generalized-Hamming graph $G_{q,n,d}$ is edge-transitive if and only if it is distance-transitive, and this happens exactly for $d=2$, $(q,d)=(2,3)$, or $(q,d)=(2,n)$. For the complements the two notions separate: edge-transitivity holds for $(q,d)=(2,n-1)$ with $n$ even or $d=n$, while distance-transitivity holds for a strictly smaller set, namely $(q,d)=(2,n-1)$ with $n$ even, or $d=n$ with $q=2$ or $n=2$. Whenever either graph or its complement is edge-transitive, the paper gives closed formulas for the Lovász theta function of both, computed from the Hamming scheme's spectrum in quadratic time instead of exponential-time SDP.","feed_headline":"Edge-transitive iff distance-transitive: full list found","feed_subtitle":"Only $d=2$, $(q,d)=(2,3)$, and $(q,d)=(2,n)$ admit either symmetry; theta values follow.","key_machinery":"The argument runs on two mechanisms. For the graphs themselves, edge-transitivity is probed by the invariant $F(v)=|N(v)\\setminus N(0)|$ counting neighbors of a neighbor $v$ that are not neighbors of $0$; if the graph were edge-transitive this count would be constant on $N(0)$, but explicit binomial counts for the vectors $(1,0,\\ldots,0)$, $(1,1,0,\\ldots,0)$ and, in the binary case, $(1,1,1,0,\\ldots,0)$ force an impossible equality, leaving only the three listed parameter sets, whose positive transitivity comes from known distance-regularity of the Hamming graph, a known proof for $G_{2,n,3}$, and a parity automorphism for $G_{2,n,n}$ constructed in Lemma 4.3.1. For the complements, the machinery is the Hamming association scheme: the adjacency matrix decomposes as $\\sum_j \\gamma_j E_j$ with $\\gamma_j = -K_{d-1}(j-1;n-1,q)$ in terms of $q$-ary Krawtchouk polynomials, and the key spectral fact is the strict inequality $\\gamma_1 < \\gamma_m$ for $2 \\le m \\le n-1$, proved by the character-theoretic representation of Krawtchouk polynomials. That inequality makes the interpolating polynomials $p(t)$ that isolate $E_1$ (or $E_1+E_n$) well defined; applying such a polynomial to the adjacency matrix produces a matrix that must be invariant under every automorphism, but its $(0,u)$-entries for vectors of different weights take different values, a contradiction that rules out all but the exceptional parameter sets.","core_discovery":"On the paper's own terms, the main discovery is Theorem 4.1.1 and Theorem 4.1.2: for a prime power $q$ and $2 \\le d \\le n$, the generalized-Hamming graph $G_{q,n,d}$ — the Cayley graph on $\\mathbb{F}_q^n$ connecting vectors at Hamming distance less than $d$ — is edge-transitive exactly when it is distance-transitive, which occurs precisely when $d=2$, or $(q,d)=(2,3)$, or $(q,d)=(2,n)$. Its complement is edge-transitive exactly for $(q,d)=(2,n-1)$ with $n$ even or $d=n$, and distance-transitive exactly for $(q,d)=(2,n-1)$ with $n$ even, or $d=n$ with $q=2$ or $n=2$; hence the distance-transitive parameters form a proper subset of the edge-transitive ones. As a corollary, every edge-transitive case yields closed-form Lovász $\\theta$ values for both the graph and its complement, since all these graphs are vertex-transitive and the equality conditions of the spectral $\\theta$ bounds are met.","pith_inferences":["The same polynomial-isolating technique — build a polynomial of the adjacency matrix that acts as an idempotent and then show no automorphism can commute with it — should apply to other Cayley graphs whose association scheme has a known eigenmatrix, e.g., graphs built from the Johnson scheme.","The classification suggests that for this family the size of the automorphism group is a poor predictor of spectral determination: the most symmetric cases are exactly the structured ones with known spectra, while random graphs, which are spectrally determined generically, are far less symmetric.","A testable extension: for parameters outside the three listed sets, computer search for small $q,n,d$ should find a pair of edges with different $F$-values (respectively different $(E_1)$ entries for the complement), giving an explicit certificate of non-edge-transitivity independent of the proof."],"forward_implications":["Every edge-transitive generalized-Hamming graph is distance-transitive, so the stronger symmetry comes for free in exactly the parameters $d=2$, $(q,d)=(2,3)$, and $(q,d)=(2,n)$.","For complements, edge-transitivity no longer implies distance-transitivity; the gap is witnessed by $d=n$ with $q\\ge 3$ and $n\\ge 3$, which is edge- but not distance-transitive.","In all edge-transitive cases, the Lovász theta value of the graph and of its complement is given in closed form from the eigenvalues in (4.4.15), computed in $O(n^2)$ time rather than by solving the exponential-size SDP.","If both a generalized-Hamming graph and its complement are edge-transitive, the parameters are $(q,d)=(2,n)$ or $(q,n,d)=(2,3,4)$ (Corollary 4.1.3)."],"supporting_citations":[{"why":"Supplies the fact that the Hamming graph $G_{q,n,2}$ is distance-transitive, the base case $d=2$ of the classification.","marker":"[42]"},{"why":"Supplies the proof that $G_{2,n,3}$ is distance-transitive, covering the exceptional case $(q,d)=(2,3)$.","marker":"[108]"},{"why":"Gives the eigenvalues of the generalized-Hamming graph, which are transformed into the complement's spectrum in Remark 4.4.11.","marker":"[148]"},{"why":"Provides the Hamming scheme eigenmatrices and Krawtchouk polynomial identities used in the spectral decomposition of the complement.","marker":"[56]"},{"why":"Supplies the character-theoretic representation of Krawtchouk polynomials and the trace properties needed for the strict eigenvalue inequality.","marker":"[93]"},{"why":"Supplies the theta-function bounds with equality conditions for edge-transitive and vertex-transitive regular graphs, on which the closed-form application rests.","marker":"[125]"},{"why":"Motivates the transitivity question via the Schrijver-theta counterexample and provides the vertex-transitive product formula $\\vartheta(G)\\vartheta(\\overline{G})=q^n$.","marker":"[124]"}],"fun_headline_variants":["Edge-transitivity iff distance-transitivity for Hamming-type graphs","Three edge-transitive families in generalized-Hamming graphs","Equivalence theorem: edge-transitivity = distance-transitivity","Full transitivity classification for Hamming-type graphs","Edge-transitivity and distance-transitivity coincide here"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proofs that the non-listed graphs lack edge-transitivity rest on a strict inequality between two eigenvalues of the complement graph, and that inequality holds only because a nonzero additive character cannot be constantly 1 on all vectors of a fixed nonzero weight.","fun_headline_variants_meta":{"raw":{"variants":["Edge-transitivity iff distance-transitivity for Hamming-type graphs","Three edge-transitive families in generalized-Hamming graphs","Equivalence theorem: edge-transitivity = distance-transitivity","Full transitivity classification for Hamming-type graphs","Edge-transitivity and distance-transitivity coincide here"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001282,"raw_usage":{"total_tokens":5314,"prompt_tokens":1098,"completion_tokens":4216,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":714,"completion_tokens_details":{"reasoning_tokens":4139}},"tokens_in":714,"tokens_out":4216,"duration_ms":31884,"temperature":1.0,"reasoning_tokens":4139,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:34:06.586828+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct automorphism search on $\\overline{G}_{2,5,4}$ (the complement of the generalized-Hamming graph with $q=2$, $n=5$, $d=4$) should find no automorphism sending the edge from $00000$ to $11111$ onto the edge from $00000$ to $11110$, since this parameter set is excluded; finding one would refute the classification.","supporting_citations":[{"cited_title":"Some remarks on the square graph of the hypercube","cited_arxiv_id":"2101.01615","evidence_quote":"Supplies the proof that $G_{2,n,3}$ is distance-transitive, covering the exceptional case $(q,d)=(2,3)$."},{"cited_title":"Improving the Gilbert-Varshamov Bound by Graph Spectral Method","cited_arxiv_id":"2104.01403","evidence_quote":"Gives the eigenvalues of the generalized-Hamming graph, which are transformed into the complement's spectrum in Remark 4.4.11."}],"review_version":2}