{"id":"458fec00-5f5b-4936-b8ac-8f4791b1a447","arxiv_id":"1908.06189","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Exact (t,r) broadcast domination numbers are claimed for paths, wide rectangular grids, and narrow king's grids, with upper bounds for slant and 3D grids.","lead":"This paper gives formulas for the minimum number of broadcasting towers needed to cover paths, certain rectangular grids, and king-move chessboard grids, where towers send signals that fade with distance. It also gives upper bounds for slanted grids and 3D grids, extending earlier work on (t,r) broadcast domination.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The exact grid and king's-grid formulas depend on an unproved tiling-optimality assumption: the lower-bound proofs in Theorems 1.2 and 1.4 only check that the constructed blocks are locally efficient and never rule out non-tiled dominating sets.","rationale":"The paper's headline contribution is a set of exact formulas; the path formula in Theorem 1.1 has a counting argument that is terse but plausibly repairable, and the appendix gives constructive code for paths. The grid and king's-grid theorems, however, are exact claims whose lower bounds are asserted rather than proved. Showing that a particular tiling is locally efficient does not establish that no other arrangement uses fewer towers, and the inductive lemmas that define the starting blocks do not verify reception vertex-by-vertex after the shifts. This is a genuine correctness risk, not a stylistic preference or a disagreement with the literature. The reader identified the same load-bearing assumption, and the proposed exhaustive-search test is a feasible way to check whether the formulas are merely unproved or actually false. As submitted, the central exact claims are not substantiated, so the reader's REJECT verdict stands; if the small-case search later confirms the formulas, the paper would still need a rigorous lower-bound proof before the theorems could be accepted.","tokens_in":19739,"tokens_out":10233,"duration_ms":108108,"concrete_test":"Run an exact backtracking or integer-programming solver for gamma_{t,r}(G_{m,n}) on small grids and compare with Theorem 1.2, e.g. (t,r,m) = (4,1,4), (3,2,3), and (4,2,3) for n from the starting-block width through about 20. Also run the same exact search for gamma_{3,2}(K_{3,n}) and compare with Theorem 1.4. In particular, Theorem 1.2 predicts gamma_{4,1}(G_{4,5})=2 and gamma_{4,1}(G_{4,9})=3; if the solver certifies these values and extends the match, the formulas survive this finite test, but the missing lower-bound proof would still need to be supplied before the theorems are established. If any mismatch occurs, the tiling-optimality assumption is false and Theorems 1.2 and 1.4 need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The exact grid formula in Theorem 1.2 rests on two unproved steps. First, Lemma 3.2 only sketches why two towers dominate its m x (2t-r-(m-2)) starting block; the induction 'shifts' a tower down and left without listing tower coordinates or computing the reception of every vertex. A placement whose two towers are again at distance 2t-r does not automatically dominate every off-diagonal vertex. Second, the minimality argument is not a lower bound: the proof says each tiling block is efficient, so spreading towers within a block would leave gaps, and concludes minimality. That only compares the given tiling with perturbations of itself; it does not rule out an entirely different tower layout with fewer towers. An exact domination number needs an argument that every set of one fewer tower fails, typically via a counting or partition argument; no such argument appears. Theorem 1.4 for king's grids has the same structure and the same gap: Lemma 5.4 gives a 2-tower pattern, and minimality is asserted because the first tower cannot move right and blocks cannot spread. Non-tiled, staggered placements are never considered. Theorem 1.3 is not an exact claim, but it is also non-substantive because B is never defined through a covering algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies $(t,r)$ broadcast domination numbers for paths, rectangular grid graphs, 3D grid graphs, slant grids, and king's grids. It claims exact formulas for paths, grids, and king's grids, and upper bounds for 3D grids and slant grids. The constructions are based on 'starting blocks' efficiently dominated by two towers, which are then tiled across larger graphs. The paper also includes a SageMath algorithm for paths and several results on infinite king's lattices.","tokens_in":19923,"tokens_out":18890,"duration_ms":158607,"significance":"Explicit formulas for $(t,r)$ broadcast domination numbers would be a useful contribution to the literature, and the paper addresses natural families of graphs. However, the central exact-formula claims are not established: the proofs rely on unsupported tiling-optimality assumptions, and the grid formula is actually false. The 3D grid result is not a substantive quantitative bound because the quantity $B$ is never defined through a concrete covering algorithm. The paper does provide a constructive path algorithm, but the main theoretical results lack the necessary rigorous lower-bound arguments.","major_comments":[{"comment":"Theorem 1.2 is false. For $t=2$, $r=1$, $m=3$, $n=5$, the formula claims $\\gamma_{2,1}(G_{3,5}) = 2 + \\lceil (5-2)/1 \\rceil = 5$. But the set $D=\\{(2,1),(1,3),(3,3),(2,5)\\}$ of four towers is a $(2,1)$ broadcast dominating set of $G_{3,5}$: every vertex is at Manhattan distance at most 1 from one of these towers, hence receives signal at least 1. Thus $\\gamma_{2,1}(G_{3,5}) \\le 4 < 5$. The minimality proof in Section 3 only checks local efficiency of the constructed tiling and does not rule out alternative configurations with fewer towers.","section":"§3, Theorem 1.2"},{"comment":"Lemma 3.2 is not proven. The induction step from $G_{m,n}$ to $G_{m+1,n-1}$ asserts that shifting the second tower down one row and left one column preserves domination, but it does not provide tower coordinates or verify reception for every vertex. The claim that shifting the tower 'results in an efficiently dominated grid' is exactly what needs proof, and the lemma is load-bearing as the base of the tiling formula in Theorem 1.2.","section":"§3, Lemma 3.2"},{"comment":"The king's grid formula in Theorem 1.4 has the same two gaps. Lemma 5.4's induction on $t$ and $r$ is only sketched: it says to shift the first tower one column and the second tower four columns, but it never lists the resulting positions or checks all vertices. The lower-bound part of Theorem 1.4 argues that the first tower cannot move right and that starting blocks cannot be spread apart, which establishes only local optimality of the constructed configuration. It does not rule out a completely different dominating set with fewer towers, so no genuine lower bound is given.","section":"§5.2, Lemma 5.4 and Theorem 1.4"},{"comment":"The path formula is a main result, but its proof is informal. The lower-bound argument 'if we remove one tower, we lose one broadcast zone... shift the remaining towers... insufficient reception at the beginning or end' is not a rigorous counting argument. Lemma 2.1, which is used as the overlap estimate, also lacks a valid proof: the statement about $\\gamma_{t,t-k}(P_n)$ does not establish a lower bound for an arbitrary dominating set. The formula may be true, but the manuscript does not provide a proof.","section":"§2, Theorem 1.1 and Lemma 2.1"},{"comment":"Theorem 1.3 is not a substantive upper bound because $B$ is never defined as a computable covering number, and no algorithm or existence argument for covering an arbitrary $G_{m,n,k}$ by starting blocks is given. Theorem 4.2's proof only checks vertices that lie inside the two broadcast zones and does not show that every vertex of the block lies in the union of those zones; moreover, the displayed equations assume both towers contribute to every vertex considered, which is not justified and is not true for vertices far from both towers.","section":"§4, Theorem 1.3 and Theorem 4.2"}],"minor_comments":[{"comment":"The definition of 'efficient broadcast' as 'minimizes wasted signal in the sense that every vertex in the overlap between multiple towers receives a signal of strength exactly r' is informal and not used as a formal definition in the proofs; please make it precise or remove it.","section":"§1, page 2"},{"comment":"The induction in Lemma 3.1 is phrased confusingly: it simultaneously refers to induction on $t$ and on $r$ without a clear base case and induction step for each parameter. For example, 'Assume, by induction, that $\\gamma_{t,1}(G_{2,(2t-1)})=2$' followed by 'we will show that $\\gamma_{(t+1),1}$' mixes the two inductions.","section":"§3, Lemma 3.1"},{"comment":"There is a typo in the reception computation: the line for $r'(v')$ is missing a closing parenthesis and uses $t'$ where $t$ is intended. This makes the displayed formula hard to follow.","section":"§4, Theorem 4.2"},{"comment":"The explanation of the equal-diagonal case in the proof of Lemma 5.5 says 'you will have path length of $n + (n-1)$', but the shortest path length in the king's lattice when $|p-x|=|q-y|$ is $|p-x|$, not $n+(n-1)$. The lemma statement is correct, but the explanation is wrong.","section":"§5.2, Lemma 5.5"},{"comment":"The GitHub URL is not properly formatted: it contains a space ('t r path domination.git') and is not a clickable link.","section":"§7, Appendix"},{"comment":"The proof of the lower bound in Theorem 5.4 again asserts minimality from the local efficiency of the starting block ('if the towers were further apart, vertices... would have insufficient reception'), which does not rule out alternative configurations with fewer towers. Since this is an exact-formula claim, the same lower-bound concern applies as in Theorem 1.4.","section":"§5.1, Theorem 5.4"}],"recommendation":"reject","confidential_remarks":"The counterexample to Theorem 1.2 shows a load-bearing error in the central grid result, so rejection is warranted. The paper appears to be an early preprint with several informal proofs; the missing lower bounds are not merely presentational and would require substantial new arguments. I would not encourage resubmission in the current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is an REU-style paper with some real content and a recurring proof gap. The path result is right, and the tiling constructions are elegant. The problem is that the exact formulas for grids and king's grids are asserted with minimality arguments that only compare the construction to itself; the lower bound is missing.\n\nWhat's new: an explicit formula for paths (elementary but useful), the wide-grid formula under the stated parameter restrictions, and the narrow-king's-grid formula. The slant-grid upper bounds via the triangular-lattice transfer are reasonable, and the infinite king's lattice patterns are neat. The authors are honest about what is an upper bound vs. exact, and Theorem 1.3 is frankly just a definition wrapped in an inequality—B is never computed, so it is not a substantive bound.\n\nThe soft spot is the lower-bound proofs in Theorems 1.2 and 1.4. The argument that each tiling block is 'efficient' only rules out small perturbations of the tiling. It doesn't rule out a completely different tower placement using fewer towers. For an exact domination number you need a counting or partition argument that shows every set of one fewer towers fails; nothing like that appears. Lemma 3.2 and Lemma 5.4 also need real coordinate-based reception checks; the inductive 'shift down and left'/'shift left' descriptions are too loose to verify the base of the tiling. If these lemmas fail, the formulas lose their foundation.\n\nThe path proof has a similar but minor issue—Lemma 2.1's overlap argument is handwavy, but the formula is correct and can be fixed with a standard interval-covering argument.\n\nCitation pattern is fine; the relevant prior work is cited, and the relationship to [2] for slant grids is appropriate.\n\nBottom line: as written, the main exact claims are not substantiated. But the paper is not junk. The constructions are concrete, the formulas are plausible and likely correct, and the gaps are identifiable and possibly repairable. I'd send it to a referee who knows broadcast domination and ask for a rigorous lower-bound argument and full reception verification in the lemmas. If those come back, the paper could be acceptable. So: not a desk reject, but a major-revision reject in current form.","headline":"The grid and king's-grid formulas are likely correct but the proofs don't establish minimality; this is a promising paper that needs a serious rewrite, not a desk reject.","tokens_in":20538,"tokens_out":5944,"would_cite":false,"duration_ms":57005,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves exact formulas for the (t,r) broadcast domination number of paths, finite grid graphs, and king's grid graphs via tilings by efficient two-tower starting blocks.","keywords":["(t,r) broadcast domination","broadcast domination number","grid graphs","paths","king's grid graph","slant grid graph","starting block","efficient broadcast"],"falsifier":"Run an exhaustive search or integer program for a small case inside the theorem's range, for example G_{3,6} with (t,r)=(4,2), where the formula predicts 2+\\lceil (6-5)/4 \\rceil = 3 towers, and also G_{3,5}, where it predicts the base case of 2 towers. A minimum below the predicted value in either case would disprove the formula; equality in both is consistent with it.","tokens_in":19465,"feed_emoji":"📡","tokens_out":7349,"duration_ms":63587,"temperature":0.7,"pith_summary":"Building on the (t,r) broadcast domination model, the paper asks how many strength-t towers are needed so that every vertex of a graph receives signal at least r. It proves exact answers for three families: paths, wide m×n grid graphs, and king's grid graphs with few rows. In each case the minimum is a ceiling of a linear ratio, with the ratio determined by the width of a two-tower block and the r−1 columns of overlap between consecutive blocks. These exact formulas reduce an optimization problem to arithmetic and extend earlier results that covered only small grids or gave upper bounds.","feed_headline":"Exact tower counts found for paths, grids, and king's grids","feed_subtitle":"The minimum-tower search collapses to a ceiling formula built from two-tower starting blocks.","key_machinery":"The load-bearing object is the (t,r) starting block: a rectangular grid that two towers of strength t dominate with no wasted signal, so every vertex in the overlap receives exactly r. The arguments prove the dimensions of such a block in each family and then tile the graph with copies of it, inserting r−1 columns of overlap between consecutive blocks so no vertex falls below reception r. The overlap requirement comes from Lemma 2.1, which says any two consecutive towers must share at least r−1 vertices in their broadcast zones. The formulas are the arithmetic of this tiling: block width determines the denominator, starting towers determine the numerator offset, and the ceiling counts the last partial block.","core_discovery":"The central discovery is that optimal (t,r) broadcasts on these graphs are column-by-column tilings by an efficient two-tower block, and once the block's width is known the domination number follows by counting columns. For a path P_n the block has width 2t−r, giving γ_{t,r}(P_n) = \\lceil (n+r-1)/(2t-r) \\rceil. For an m×n grid with m≥2, 2t−r>m−1, and n≥2t−r−(m−2), the block width is 2t−r−(m−2), giving γ_{t,r}(G_{m,n}) = 2 + \\lceil (n-(2t-r-(m-2)))/((2t-r-(m-2))-1) \\rceil. For a king's grid with t>r and m≤2(t−r)+1, placing towers along the middle row makes the count match the path formula, γ_{t,r}(K_{m,n}) = \\lceil (n+r-1)/(2t-r) \\rceil. The same starting-block vocabulary produces upper bounds for 3D grids and for slant grids, and exact two-row slant counts.","pith_inferences":["If the starting-block tiling is optimal at every parameter value covered by the theorems, the same column-counting argument should yield exact formulas for wider king's-grid bands; the natural test is to increase m past 2(t−r)+1 and look for the threshold where diagonal edges begin to reduce the tower count.","The paper's path and king's-grid formulas both use the r−1 overlap rule, which suggests that cycles may often attain the upper bound given in Corollary 6.1; one could test whether γ_{t,r}(C_n) equals \\lceil (n+r-1)/(2t-r) \\rceil except when the closing of the cycle forces a larger last block.","The block widths in the grid theorem are all of the form 2t−r−(m−2), so the same machinery might give exact counts for other rectangular families with fixed row number m, replacing exhaustive search with a one-line formula once the correct starting block is identified."],"forward_implications":["For paths, the (t,r) broadcast domination number is now known for every t≥r≥1; the exact value is \\lceil (n+r-1)/(2t-r) \\rceil for all n≥1.","For m×n grids in the stated range, the number of towers grows linearly in the number of columns with slope 1/(2t−r−(m−1)), plus two towers for the starting block.","For king's grids with m≤2(t−r)+1, the diagonal edges do not lower the tower count below the path value; the middle row alone carries the domination.","For 3D grids, any rectangular box can be covered by copies of a two-tower starting block, giving the upper bound γ_{t,r}(G_{m,n,k})≤2B where B is the number of blocks needed.","For two-row slant grids, the exact count is \\lceil 2(n+r-1)/(4t-2r-1) \\rceil whenever t>r."],"supporting_citations":[{"why":"Defines (t,r) broadcast domination and supplies the small-grid formulas that this paper generalizes.","marker":"[1]"},{"why":"Provides the efficient domination pattern for the triangular lattice that the slant-grid upper bounds are derived from.","marker":"[2]"},{"why":"Gives a prior upper bound for t>2 on finite grids that the exact grid formula refines for the parameter range considered.","marker":"[3]"}],"fun_headline_variants":["Two-tower blocks tile grids for exact broadcast counts","Exact tower counts from two-tower block formulas","Two-tower block cracks grid and king's grid counts","Exact minimal towers for paths grids and king's grids","Broadcast domination numbers collapse to ceiling formulas"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The grid and king's-grid formulas assume that an optimal dominating set can always be cut into identical two-tower starting blocks of the exact dimensions used in the constructions, with the proof of the grid block's base case left as an induction sketch that does not explicitly check reception at every vertex after the shift.","fun_headline_variants_meta":{"raw":{"variants":["Two-tower blocks tile grids for exact broadcast counts","Exact tower counts from two-tower block formulas","Two-tower block cracks grid and king's grid counts","Exact minimal towers for paths grids and king's grids","Broadcast domination numbers collapse to ceiling formulas"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000763,"raw_usage":{"total_tokens":3456,"prompt_tokens":1083,"completion_tokens":2373,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":699,"completion_tokens_details":{"reasoning_tokens":2297}},"tokens_in":699,"tokens_out":2373,"duration_ms":16755,"temperature":1.0,"reasoning_tokens":2297,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:55:21.416642+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive search or integer program for a small case inside the theorem's range, for example G_{3,6} with (t,r)=(4,2), where the formula predicts 2+\\lceil (6-5)/4 \\rceil = 3 towers, and also G_{3,5}, where it predicts the base case of 2 towers. A minimum below the predicted value in either case would disprove the formula; equality in both is consistent with it.","supporting_citations":[{"cited_title":"On (t,r) Broadcast Domination Numbers of Grids","cited_arxiv_id":"1401.2499","evidence_quote":"Defines (t,r) broadcast domination and supplies the small-grid formulas that this paper generalizes."},{"cited_title":"Broadcast Domination of Triangular Matchstick Graphs and the Triangular Lattice","cited_arxiv_id":"1804.07812","evidence_quote":"Provides the efficient domination pattern for the triangular lattice that the slant-grid upper bounds are derived from."},{"cited_title":"Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids","cited_arxiv_id":"1805.06058","evidence_quote":"Gives a prior upper bound for t>2 on finite grids that the exact grid formula refines for the parameter range considered."}],"review_version":1}