{"id":"78e8d1e0-f2b5-448d-87cf-b2eb13c543ac","arxiv_id":"1908.07586","paper_version":6,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper disproves the natural generalization of Vizing's conjecture for (t,r) broadcast domination when r≥2, and provides density bounds and a faster search algorithm for grid patterns.","lead":"This paper studies generalized broadcast domination on grids, where transmitters decay in strength with distance and each point needs a minimum total signal. The main results are counterexamples to a proposed generalization of Vizing's conjecture for these broadcasts, plus new lower bounds and a faster algorithm for computing optimal broadcast densities.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Correctness proof of the Section 5 search cites a false reflection symmetry; the needed reception symmetry actually follows from central inversion, so Table 3 is probably sound, but the proof and pseudocode need repair.","rationale":"The reader's weakest assumption identifies the false reflection symmetry in Section 5, and that is indeed the most load-bearing issue: the completeness of Algorithm 1, and therefore the validity of Table 3 as a statement about minimum tower-set density, rests on the claim that only one side of the x-axis has to be checked. I agree that the stated invariance under (x,y)->(-x,y) is false. However, the concern does not land as an actual invalidation of the computational results, because the weaker reception symmetry the reader mentions is true and easy to prove: T(d,e) is invariant under central inversion (x,y)->(-x,-y), and every vertex is equivalent under the tower translations to an x-axis vertex. Hence R(i,0)=R(-i,0) holds for every d,e, so the restricted search is mathematically justified. What remains is a proof-and-reproducibility gap, not a demonstrated counterexample to the table. The other issues in the paper, such as the misstated map in Theorem 15 and the typographical errors in Theorems 12 and the MaxPotentialD formula, are similarly local and fixable. For these reasons the reader's conditional verdict is appropriate, and my read does not change it.","tokens_in":11474,"tokens_out":36714,"duration_ms":856128,"concrete_test":"Reimplement IsBroadcast from the published pseudocode, and independently with an exact check of all vertices (x,y) in one period (x in [0,d-1], y in [-(t-1),t-1], using true Manhattan distance and all row-0 wrap-around broadcasts), scanning the same (t,r,d,e) range as the paper. Recompute Table 3 for t,r<=9 and compare the two outputs. If the restricted check and the full check agree on every entry, the false reflection statement is a harmless proof bug and the table stands; if they disagree, the reported reciprocal densities are not certified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The Vizing counterexample in Section 2 is correct; the load-bearing soft spot is the correctness argument for Algorithm 1 and Table 3. The text says that because the broadcast set is invariant under (x,y)->(-x,y), only vertices i in [t-r+1, d/2] on the x-axis need checking. That invariance is false for a general tower set: in T(18,5), row 1 contains x=5 but not x=13. What is actually needed is reception symmetry R(i,0)=R(-i,0), and this does hold: T(d,e) is invariant under central inversion (x,y)->(-x,-y), and every vertex is translation-equivalent to a vertex on the x-axis, so checking one representative of each pair {i,d-i} is sufficient. Thus the stated reason is wrong, but the algorithm's restriction is repairable. The remaining risk is that the published pseudocode is not a faithful certificate: MaxPotentialD is written as floor(1/gamma) instead of floor(C/r), the inner procedure is called Rebroadcast but defined as IsBroadcast, and no machine-checked or independently reproduced table is given. If any of these hides an implementation discrepancy, the Table 3 densities could be non-optimal, though still valid upper bounds.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies (t,r) broadcast domination on graphs, with emphasis on grid graphs. It proves that the natural analog of Vizing's conjecture fails for r≥2 by exhibiting cycles C_n with n=2(t−r+1) for which γ_{t,r}(C_n□C_n)=2<γ_{t,r}(C_n)^2=4 (Section 2). It then derives formulas and generating functions for the sizes of distance balls in Z^n, including a claimed bijection between B_n(d) and B_d(n) (Section 3), proves a double-counting lower bound on the domination density of grids (Section 4), and gives an algorithm that searches over periodic 'tower' broadcast patterns to compute densities, with a table of reciprocal densities for t,r≤9 (Section 5, Table 3).","tokens_in":11671,"tokens_out":14850,"duration_ms":134604,"significance":"The main conceptual contribution is the counterexample family to the (t,r)-broadcast generalization of Vizing's conjecture: it is correct, simple, and explicitly disproves a natural conjecture for all r≥2. The ball-counting identities, generating functions, and Delannoy-number connection are useful additions to the broadcast-domination toolkit, and the coverage double-counting lower bound (Theorem 17) is a clean argument. The paper also extends the computational method of Drews–Harris–Randolph to more dimensions and reports a speedup. However, the computational section is not yet in final form: the stated symmetry justification for Algorithm 1 is false, and the pseudocode contains internal inconsistencies. These issues are repairable, but the current manuscript does not provide a correct published certificate for Table 3.","major_comments":[{"comment":"The justification for checking only vertices (i,0) with i≤d/2 is incorrect. The broadcast set T(d,e) is not invariant under (x,y)→(−x,y): for T(18,5), the point (5,1) belongs to the tower set, but (−5,1) does not. The reduction can instead be proved from central inversion (x,y)→(−x,−y), which does preserve T(d,e), together with the translation equivalence (x,y)→(x−ye,0); these imply that reception at (−i,0) equals reception at (i,0) and that every vertex is domination-equivalent to an x-axis representative. Please replace the stated reflection argument with this correct version, since the correctness proof of the algorithm is otherwise invalid as written.","section":"Section 5, paragraph after Algorithm 1"},{"comment":"The pseudocode is not internally consistent. MaxPotentialD is written as floor(1/γ_{t,r}(G)) ≤ C_{t,r}(Z^n)/(r|V|), but Example 18 uses d starting at floor(C_{t,r}/r)=19 for (t,r)=(4,2), which is the quantity that makes sense. In addition, procedure MinDensity calls Rebroadcast, which is never defined, while the defined procedure is IsBroadcast. These discrepancies mean the published text is not a faithful certificate for Table 3; they should be corrected, and the authors should supply the actual code or machine-checkable output to support the tabulated values.","section":"Section 5, Algorithm 1 and preceding text"},{"comment":"The proof says that ψ is defined by reversing the order of the signed tuples, but reversing order does not map T_{n,d} to T_{d,n}, since it leaves both the dimension sum and the distance sum unchanged. Example 14 shows that the intended map swaps the two entries in each tuple, which is what interchanges the two sums. Please correct the proof of Theorem 15 to match the map used in the example.","section":"Section 3, Theorem 15 proof"}],"minor_comments":[{"comment":"The displayed formula for S_d(x) has (1+x)^{d+1} as the denominator; the first displayed expression in the proof and the analogous formula for S_n(y) show that the denominator should be (1−x)^{d+1}. The condition 'for x>0' should also be removed.","section":"Section 3, Theorem 12"},{"comment":"The initialization a[i]=a[−i]=t−i relies on an implicit wrap-around convention for negative indices; the pseudocode should state explicitly that a[−i] means a[d−i] for 1≤i<t.","section":"Section 5, pseudocode for IsBroadcast"},{"comment":"The sentence 'where the second equality comes from plugging in the cardinality |S_n(d)| from Theorem 7' refers to a second equality that is not present in the displayed formula; the sentence should be reworded or removed.","section":"Section 4, Lemma 16 proof"},{"comment":"The phrases 'found here' for the code and more complete data should be replaced by permanent references, an appendix, or a stable repository link, so the computational results can be independently checked.","section":"Section 5, data availability"}],"recommendation":"major_revision","confidential_remarks":"The Vizing counterexample in Section 2 is correct and is the paper's strongest contribution. My main concern is Section 5: the false reflection invariance and the pseudocode inconsistencies make the computational table unverified as published, although the repairable central-inversion argument suggests the table is probably sound. With a corrected proof, corrected pseudocode, and reproducible code/data, the computational claims should be salvageable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Tom,\n\nThe paper's central claim checks out: for r≥2, the natural (t,r) analog of Vizing's conjecture is false, and the counterexample in Theorem 4 is as clean as it gets. The lower bound in Theorem 17 is a straightforward double-count that is correct, and the algorithm in Section 5 appears to extend the published density tables, with a plausible speedup. There is real value here.\n\nThe genuinely new piece is the counterexample; the lattice-ball identities are mostly repackaged known Delannoy material, but the explicit bijection in Theorem 15 is a nice addition. That said, the proof of Theorem 15 has a misdefinition: ψ is described as \"reversing the order of all the signed tuples,\" but the example and the intended map swap the entries inside each tuple, not the order of the tuples. Read literally, the proof does not work. Fixing the definition makes the bijection correct, but it needs to be fixed.\n\nTheorem 12 has a denominator typo: the displayed S_d(x) should have (1-x)^{d+1} in the denominator, not (1+x)^{d+1}. Minor, but obvious once seen.\n\nThe bigger soft spot is the correctness argument for Algorithm 1. The text justifies checking only vertices on the positive x-axis by claiming the broadcast set is invariant under (x,y)→(-x,y). That is false: T(18,5) contains (5,1) but not (-5,1). What actually saves the search is that T(d,e) is invariant under central inversion and every row is a translate of the x-axis row, which gives the reception symmetry R(i,0)=R(-i,0). The conclusion is right, but the stated reason is wrong and should be corrected. The pseudocode also has two glitches: MaxPotentialD is written as floor(1/γ) instead of floor(C/r), and the inner procedure is called Rebroadcast while the definition is IsBroadcast. Those are easy repairs, but they need to be made before the table can be taken as a certificate.\n\nOne more: the claim that \"when r=1, the density equals the minimum density\" is asserted without proof. If it is true, show the argument; if not, soften it.\n\nNone of these are load-bearing in the sense of invalidating the main theorems, but they are real defects in an otherwise solid paper. I would send it to a competent referee and ask for a revision addressing the ψ definition, the symmetry justification, and the pseudocode. After that, it is citable.","headline":"The (t,r) Vizing counterexample is real and the main math holds, but the bijection proof and the algorithm's correctness argument both contain fixable errors.","tokens_in":12269,"tokens_out":3620,"would_cite":true,"duration_ms":34230,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","05C76","05A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The (t,r) broadcast domination analogue of Vizing's conjecture fails for reception threshold at least 2, with explicit cycle-square counterexamples.","keywords":["broadcast domination","(t,r) broadcast domination","Vizing's conjecture","Cartesian product of graphs","grid graphs","domination density","Delannoy numbers","lattice balls"],"falsifier":"Take $(t,r)=(4,2)$, so $n=6$: a single broadcast at $(0,0)$ leaves $(3,0)$ with reception $1<2$, while broadcasts at $(0,0)$ and $(3,3)$ give every vertex of $C_6 \\Box C_6$ reception exactly $2$. If either part fails, Theorem 4's counterexample collapses; for the density tables, a non-tower periodic pattern that dominates with density below the table's value would show those numbers are only tower-set minima.","tokens_in":11218,"feed_emoji":"📡","tokens_out":10413,"duration_ms":100989,"temperature":0.7,"pith_summary":"The paper studies (t,r) broadcast domination, in which each broadcast at strength t sends t minus distance to vertices within distance t, and a vertex is dominated when its total reception reaches r. Its central theoretical result is that the (t,r) analogue of Vizing's conjecture—that the domination number of a Cartesian product is at least the product of the factors' domination numbers—is false whenever r is at least 2. The counterexamples are squares of cycles: with n = 2(t-r+1), both a single cycle and its Cartesian square have (t,r) broadcast domination number 2, so the product bound predicts at least 4. The paper also develops counting formulas for lattice balls, a dimension-radius bijection, a lower bound on dominating-pattern density via coverage, and an algorithm that searches periodic tower patterns to produce upper bounds and tables of densities.","feed_headline":"Two broadcasts dominate a grid that Vizing-style bound says needs four","feed_subtitle":"For cycles of length twice (t-r+1), the product grid needs only two broadcasts, not four.","key_machinery":"Two mechanisms carry the argument. For the counterexample, the load-bearing identity is the antipodal-pair reception on $C_n \\Box C_n$: with $n = 2(t-r+1)$, the distances from any vertex to the two broadcasts at $(0,0)$ and $(n/2,n/2)$ sum to $n$, giving reception $2t-n = 2r-2$, which clears the threshold $r$ precisely when $r \\ge 2$. For the density results, the machinery is the tower set $T(d,e) = \\{(md+ne, n) : m,n \\in \\mathbb{Z}\\}$, a periodic lattice of broadcasts of density $1/d$, together with the unwasted-coverage function $C_{t,r}(\\mathbb{Z}^n)$ that caps how much reception one broadcast can contribute and yields the lower bound $\\gamma_{t,r}(G) \\ge r|V|/C_{t,r}(\\mathbb{Z}^n)$.","core_discovery":"On the paper's own terms, the discovery is a negative answer to the natural broadcast version of Vizing's conjecture. Fix $t \\ge r \\ge 2$ and let $n = 2(t-r+1)$. In the cycle $C_n$, one broadcast leaves the antipodal vertex with reception $r-1$, so $\\gamma_{t,r}(C_n)=2$. In the Cartesian square $C_n \\Box C_n$, two broadcasts placed at $(0,0)$ and $(n/2,n/2)$ dominate: for every vertex, the two distances to those broadcasts sum to $n$, so the total reception is $t-d_1 + t-d_2 = 2t-n = 2r-2 \\ge r$, while a single broadcast still leaves $(n/2,0)$ undominated. Hence $\\gamma_{t,r}(C_n \\Box C_n)=2 < \\gamma_{t,r}(C_n)\\gamma_{t,r}(C_n)=4$. The paper supports this with the conjecture that a factor $1/2$ lower bound holds for all $t,r$, and that the $r=1$ (distance-domination) case satisfies the original Vizing inequality. Alongside this, it proves formulas for $|S_n(d)|$ and generating functions, the bijection between $B_n(d)$ and $B_d(n)$, a coverage lower bound $\\gamma_{t,r}(G) \\ge r|V|/C_{t,r}(\\mathbb{Z}^n)$, and an algorithm over tower sets $T(d,e)$.","pith_inferences":["Editorial extension: if the bijection between $B_n(d)$ and $B_d(n)$ is combined with the coverage bound, domination densities for parameters $(n; t,r)$ may be compared with those for $(t; n,r)$; a concrete test is to compute $C_{n,r}(\\mathbb{Z}^t)$ and compare it with $C_{t,r}(\\mathbb{Z}^n)$.","Editorial extension: Conjecture 6 with $t=2$ is the original Vizing conjecture, since ordinary domination is $(2,1)$ broadcast domination, so a proof for all $t$ would settle the classical conjecture as a special case.","Editorial extension: the paper's density tables are restricted to periodic tower patterns, so a natural test is whether a non-tower periodic pattern can achieve lower density than the table values; if one does, the tables are upper bounds rather than global minima."],"forward_implications":["For every $t \\ge r \\ge 2$, the graph $C_n \\Box C_n$ with $n = 2(t-r+1)$ has $\\gamma_{t,r}(C_n \\Box C_n)=2 < 4 = \\gamma_{t,r}(C_n)\\gamma_{t,r}(C_n)$, so the product lower bound proposed in Question 2 is false.","The counterexample family has product ratio 2, so if Conjecture 5 is true its factor $1/2$ is tight for this family; no stronger constant of Vizing type can hold for all $(t,r)$ broadcasts with $r \\ge 2$.","The coverage bound $\\gamma_{t,r}(G) \\ge r|V|/C_{t,r}(\\mathbb{Z}^n)$ applies to every finite $n$-dimensional grid subgraph and gives a universal lower bound on the number of broadcasts needed.","The tower-set algorithm returns explicit periodic dominating patterns; for $r=1$ the returned density matches the lower bound, so these are optimal among tower sets, and the table values agree with previously known results.","The bijection between $B_n(d)$ and $B_d(n)$ means any conclusion that depends only on ball sizes is symmetric in dimension and radius."],"supporting_citations":[{"why":"Defines (t,r) broadcast domination and gives the reception formula and small-grid values that frame the paper's questions.","marker":"[1]"},{"why":"Introduces optimal broadcast patterns on the infinite grid and the tower-set method that Algorithm 1 extends and compares with.","marker":"[3]"},{"why":"States Vizing's conjecture, whose (t,r) analogue is posed as Question 2 and answered negatively for r at least 2.","marker":"[6]"},{"why":"Provides the formula for |S_n(d)| and the Delannoy-number connection used in the lattice-ball counting section.","marker":"[7]"},{"why":"Surveys known special cases of Vizing's conjecture, used as context for the generalization question.","marker":"[2]"}],"fun_headline_variants":["Grid needs 2 broadcasts, not 4, breaking Vizing-style bound","Counterexample to broadcast Vizing conjecture found in grids","New bounds and counterexample for broadcast domination in grids","Two broadcasts beat product bound in grid domination","Grid broadcast domination: Vizing conjecture fails for r≥2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The density tables rest on the search's assumption that checking only vertices $(i,0)$ for $t-r+1 \\le i \\le d/2$ catches every undominated vertex because the periodic broadcast pattern is symmetric under $(x,y) \\mapsto (-x,y)$; if that symmetry fails, the search can certify a non-dominating pattern as dominating.","fun_headline_variants_meta":{"raw":{"variants":["Grid needs 2 broadcasts, not 4, breaking Vizing-style bound","Counterexample to broadcast Vizing conjecture found in grids","New bounds and counterexample for broadcast domination in grids","Two broadcasts beat product bound in grid domination","Grid broadcast domination: Vizing conjecture fails for r≥2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000543,"raw_usage":{"total_tokens":2633,"prompt_tokens":1010,"completion_tokens":1623,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":1542}},"tokens_in":626,"tokens_out":1623,"duration_ms":10156,"temperature":1.0,"reasoning_tokens":1542,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:03:49.286332+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $(t,r)=(4,2)$, so $n=6$: a single broadcast at $(0,0)$ leaves $(3,0)$ with reception $1<2$, while broadcasts at $(0,0)$ and $(3,3)$ give every vertex of $C_6 \\Box C_6$ reception exactly $2$. If either part fails, Theorem 4's counterexample collapses; for the density tables, a non-tower periodic pattern that dominates with density below the table's value would show those numbers are only tower-set minima.","supporting_citations":[{"cited_title":"On ( t, r) broadcast domination numbers of grids","cited_arxiv_id":null,"evidence_quote":"Defines (t,r) broadcast domination and gives the reception formula and small-grid values that frame the paper's questions."},{"cited_title":"Drews, Pamela E","cited_arxiv_id":null,"evidence_quote":"Introduces optimal broadcast patterns on the infinite grid and the tower-set method that Algorithm 1 extends and compares with."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States Vizing's conjecture, whose (t,r) analogue is posed as Question 2 and answered negatively for r at least 2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the formula for |S_n(d)| and the Delannoy-number connection used in the lattice-ball counting section."},{"cited_title":"Har tnell, Michael A","cited_arxiv_id":null,"evidence_quote":"Surveys known special cases of Vizing's conjecture, used as context for the generalization question."}],"review_version":1}