{"id":"98ac31a4-a1a7-4925-9f48-9c0770e8ee7a","arxiv_id":"1908.10573","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For edge ideals I and J with I contained in J, the regularity of IJ is bounded by induced matching and chordal cover invariants, and exact values are found for several graph classes.","lead":"This mathematics paper proves new upper and lower bounds for the Castelnuovo-Mumford regularity of products of edge ideals, an algebraic quantity that measures how complicated an ideal is. It then computes the exact regularity for several families of graphs and for products of three or four edge ideals ending in a complete graph.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lower bound in Theorem 3.3 depends on an unproved extension of the Beyarslan–Hà–Trung Betti inequality from powers to products IJ; without it the exact formulas of Section 4 lack support.","rationale":"The paper's central claim splits into a lower bound (Theorem 3.3) and an upper bound (Theorem 3.5). The upper-bound proof is lengthy but largely self-contained via Lemma 3.4. The lower bound, however, rests on a one-sentence assertion that a known Betti-number comparison for powers extends to the product IJ. This is the weakest point because Betti numbers are not monotone under ideal inclusion and the lcm-lattice structure for a product of two distinct edge ideals differs from that of powers of one edge ideal. A finite computational search over small graphs can settle whether the claimed inequality β_{i,j}(P^2) ≤ β_{i,j}(IJ) holds; if it fails, Theorem 3.3 is false, and the exact regularity formulas in Section 4 collapse. The reader identified exactly this assumption, and the secondary gap in Theorem 4.6 is less dangerous because it does not affect the two-ideal case. The paper includes some Macaulay2-based examples but no formal verification, so the unproved comparison has no independent machine-checked support. A conditional verdict remains appropriate: the results are plausible, but the proof is incomplete at a load-bearing point, and the concrete test would either repair or refute it.","tokens_in":14542,"tokens_out":29315,"duration_ms":307406,"concrete_test":"Run a Macaulay2 search over all pairs (H, G) of graphs on at most six vertices with H an induced subgraph of G. For each pair compute reg(I(H)I(G)) and ν_GH; any pair with reg(IJ) < ν_GH + 3 disproves Theorem 3.3. To isolate the Betti assertion, fix Q to be a maximum common induced matching, set P = I(Q), and check degree by degree whether β_{i,j}(P^2) ≤ β_{i,j}(IJ) fails. A good first explicit instance is H consisting of two disjoint edges {x1x2, x3x4} and G = H ∪ {x1y} with a new vertex y, where Q is induced in both; compare reg(IJ) with the predicted value 5.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower bound ν_GH + 3 ≤ reg(IJ) (Theorem 3.3) is obtained by taking Q to be a common induced matching of H and G, setting P = I(Q), and asserting that β_{i,j}(P^2) ≤ β_{i,j}(IJ) because the proof of Beyarslan–Hà–Trung [4, Lemma 4.2] 'goes through'. That lemma concerns powers I(K′)^s ⊆ I(K)^s when K′ is an induced subgraph of K, not products of two distinct edge ideals. The inclusion P^2 ⊆ IJ is not enough: Betti numbers are not monotone under inclusion of monomial ideals — for instance (x^2, xy, y^2) ⊂ (x, y) has higher regularity than the larger ideal. The BHT proof uses the lcm-lattice of s-tuples of edges of a single graph; for IJ the relevant objects are pairs (edge of H, edge of G), and the lcm of two edges of Q may also be realizable by mixed pairs in H × G, so the injection used in the power case is not automatic. The paper provides no argument for this extension. Since the lower bound feeds into Corollaries 3.7, 4.1, 4.2 and Theorem 4.3(2), this is the most load-bearing unproved step. A smaller gap, Theorem 4.6 ending with 'proceed as in Theorem 4.3', affects only the d ≥ 3 results and is secondary.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Castelnuovo-Mumford regularity of products of edge ideals IJ with I⊆J, where I and J are the edge ideals of graphs H and G. The main results are a lower bound in terms of a common induced matching number ν_GH and upper bounds in terms of co-chordal cover numbers and the regularities of I and J. These bounds are then applied to obtain exact formulas for several graph classes (cycles of length divisible by 3, weakly chordal graphs, unmixed bipartite graphs, graphs with dominating induced matchings) and to obtain linear-resolution criteria. A final theorem treats products of chains J1⊆⋯⊆Jd with Jd the edge ideal of a complete graph for d=3,4.","tokens_in":14814,"tokens_out":28725,"duration_ms":293510,"significance":"If the main lower bound were fully established, the paper would give a clean combinatorial description of reg(IJ), generalizing the Katzman-Woodroofe bounds for a single edge ideal and yielding exact formulas for natural graph classes. The upper-bound machinery via colon ideals and co-chordal covers (Lemma 3.4, Theorem 3.5) is original and carefully developed, and Theorem 3.9 is a useful inequality. The Macaulay2 examples are a concrete strength, and the statements are explicit and falsifiable. However, the central lower bound currently rests on an unproved Betti-number comparison, so the exact formulas of Section 4 are conditional on that missing argument.","major_comments":[{"comment":"The lower bound ν_GH+3≤reg(IJ) is not proved as written. The proof invokes Beyarslan-Hà-Trung Lemma 4.2, which compares Betti numbers of powers of an edge ideal when passing to an induced subgraph, and asserts that the proof 'goes through' for the product IJ. This is not a formality: the inclusion P^2⊆IJ does not by itself imply β_{i,j}(P^2)≤β_{i,j}(IJ), because Betti numbers are not monotone under inclusion of monomial ideals (e.g., reg(x^2,y^2)=3 but reg(x^2,xy,y^2)=2 even though (x^2,y^2)⊂(x^2,xy,y^2)). The lcm-lattice of P^2 embeds into that of IJ, but the desired inequality in the product case must be established explicitly, either by constructing a comparison of free resolutions or by proving the relevant lcm-lattice homology inequality. I note that Theorem 4.3(2) is proved by a separate exact-sequence argument and does not itself depend on this lower bound; however, the lower bound is load-bearing for Corollary 3.7, Corollary 4.1, Remark 4.2, and Theorem 4.3(1). This gap should be repaired before the paper is accepted.","section":"Theorem 4.6 (Section 4)"},{"comment":"The proof of Theorem 4.6 is only a sketch and should be completed. The claim that every minimal generator of ((J,F1,…,F_{i-1}):F_i) has degree 2 is not derived in full detail from the preceding claim in all cases, and the final sentence 'Proceeding as in the proof of Theorem 4.3 we will get the desired conclusion' omits the actual Betti-number and regularity argument that is central to the theorem. Since the theorem asserts an exact value of regularity for products of three or four edge ideals, the long exact sequence and regularity comparison should be written out for d=3 and d=4, or the proof should be replaced by a reference to a complete argument.","section":"Theorem 4.6 (Section 4)"}],"minor_comments":[{"comment":"The definition of ν_GH as 'the largest size of induced matching of H as well as G' should be stated more explicitly, for example as the maximum size of a matching whose edges are edges of H and which is induced in G (and hence in H).","section":"Section 2, definition of ν_GH"},{"comment":"In Remark 4.2, the condition 'ν(G)=ν(G)' should read 'ν(H)=ν(G)'; otherwise the statement is vacuous.","section":"Remark 4.2"},{"comment":"In the proof of Theorem 3.5, the inequality 'reg( ~IJ : fi) ≤ co-chord(P_i)+1' is stated for ideal regularity, but the exact-sequence chain above it requires a bound on the quotient regularity reg(R/(IJ:f_i)). Using the quotient version reg(R/I(P_i)) ≤ co-chord(P_i) gives the stated upper bound; as written this appears to be an off-by-one slip in the presentation, not in the result, but it should be corrected.","section":"Theorem 3.5 proof"},{"comment":"There are several typographical errors ('Caste lnuovo-Mumford', 'regular ity', 'SEL V ARAJA') that should be corrected in a final version.","section":"Abstract and Introduction"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the unproved Betti-number comparison in Theorem 3.3. If the authors can supply a complete proof of that inequality, the paper would be a solid contribution to the study of regularity of products of edge ideals. I do not see grounds for rejection, since the claim is plausible and may follow from known lcm-lattice methods, but the missing argument is central and must be supplied before the exact formulas of Section 4 can be regarded as established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The paper proves genuinely new two-sided bounds for reg(IJ) when I and J are edge ideals with I⊆J, and works out exact formulas for several graph classes. The main theorem is: ν_GH + 3 ≤ reg(IJ) ≤ max{co-chord(G)+3, co-chord(H)+1}. That's a natural extension of the Katzman–Woodroofe bounds, and the upper bound argument is the real work: Theorem 3.2 identifies the colon ideal (IJ:ab) as a quadratic monomial ideal, and Lemma 3.4 shows the associated graph has co-chordal number no bigger than co-chord(G). That part is carefully done, with a long case analysis that looks correct to me. Theorem 3.9, relating reg(IJ) to reg(I) and reg(J), is also solid and gives a nice incomparable bound.\n\nThe soft spot is the lower bound. Theorem 3.3 imports Beyarslan–Hà–Trung's Lemma 4.2 — monotonicity of Betti numbers for powers under induced subgraphs — and asserts the same proof goes through for the product IJ. That is not automatic. Betti numbers are not monotone under ordinary inclusion of monomial ideals, so the mere inclusion P²⊆IJ is not enough. In the powers case there is an lcm-lattice injection; for products of two different ideals the pairs are (edge of H, edge of G) and the lcm of two edges of Q might also be realized by mixed pairs. The paper gives no argument. Since this lower bound feeds Corollaries 3.7, 4.1, 4.2, and Theorem 4.3(2), the exact formulas of Section 4 only hold if the Betti inequality actually extends. I think it likely does, but the authors need to prove it. Theorem 4.6 also ends with 'proceeding as in Theorem 4.3', which is thin for the d∈{3,4} claims, but that is secondary.\n\nThere are minor typos — Remark 4.2 writes ν(G)=ν(G) where ν(H)=ν(G) is meant — and the Macaulay2 examples are plausible checks.\n\nWho's this for: people working on regularity of monomial ideals and edge ideals. It is a worthwhile contribution if the gap is filled. I'd send it to a serious referee, not desk reject, because the upper bound and the framework are real. The referee should ask for a complete proof of the lower bound as a revision condition.\n\nRecommendation: engage with it, but condition your acceptance on fixing Theorem 3.3.","headline":"New bounds for regularity of products of edge ideals, but the lower bound rests on an unproved Betti inequality that needs to be supplied before the exact formulas can be trusted.","tokens_in":15351,"tokens_out":2600,"would_cite":false,"duration_ms":24914,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["13D02","05E45","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Induced matchings bound the regularity of edge-ideal products","keywords":["Castelnuovo-Mumford regularity","edge ideals","induced matching number","co-chordal cover number","product of ideals","linear resolution","monomial ideals"],"falsifier":"Compare the graded Betti numbers of I(Q)^2 and IJ for a pair of graphs H ⊆ G that share an induced matching Q using a computer algebra system; a single pair with β_{i,j}(I(Q)^2) > β_{i,j}(IJ) would invalidate the proof of the lower bound in Theorem 3.3.","tokens_in":14326,"feed_emoji":"📏","tokens_out":9926,"duration_ms":82178,"temperature":0.7,"pith_summary":"This paper studies the Castelnuovo-Mumford regularity of the product of two edge ideals, a numerical measure of how complicated the syzygies of an ideal are. For edge ideals I and J with I ⊆ J, coming from graphs H and G, it proves a lower bound in terms of the induced matching number common to both graphs, and an upper bound in terms of the co-chordal cover number of G and the regularity of I. When H sits inside G with equal induced matching numbers, the bounds collapse to an exact formula reg(IJ) = ν(G)+3 for several graph classes, including cycles on 3n vertices, weakly chordal graphs, and certain bipartite graphs. If the larger ideal J has a linear resolution, the paper shows the product has a linear resolution when reg(I) ≤ 4 and otherwise reg(IJ) = reg(I). These results turn a generally intractable invariant into a graph-counting problem for a natural class of monomial ideals.","feed_headline":"Induced matchings bound the regularity of edge-ideal products","feed_subtitle":"Lower bound from induced matchings, upper bound from chordal covers, plus exact formulas for several graph classes.","key_machinery":"The load-bearing object is the colon ideal (IJ : ab), taken modulo a generator ab of I. Theorem 3.2 shows this colon is generated by quadrics, so after polarization it is again an edge ideal of a graph P that contains G. Lemma 3.4 proves co-chord(P) ≤ co-chord(G) by extending each co-chordal cover of G with carefully ordered edges, preserving the forbidden-induced-2K2 condition. This lets the proof feed the classical bound reg(I(G)) ≤ co-chord(G)+1 for a single edge ideal into the short exact sequences that relate IJ to its colon ideals. On the lower side, the comparison of graded Betti numbers between the square of the edge ideal of an induced matching and the full product IJ carries the argument, reducing the lower bound to ν_GH+3.","core_discovery":"The central claim is Theorem 1.1: if I is the edge ideal of H and J is the edge ideal of G with I ⊆ J, then ν_GH + 3 ≤ reg(IJ) ≤ max{co-chord(G)+3, co-chord(H)+1}, where ν_GH is the induced matching number of H (equivalently of G when the matching is induced in both) and co-chord(−) is the minimum number of co-chordal subgraphs needed to cover the edge set. The paper also proves reg(IJ) ≤ max{reg(J)+3, reg(I)} as an incomparable upper bound. From these, it derives exact values for cycles with 3n vertices, weakly chordal graphs, unmixed bipartite graphs, and bipartite graphs of regularity 3, plus a dichotomy when J has a linear resolution.","pith_inferences":["The Betti-number comparison used for the lower bound suggests a general principle: products of edge ideals may inherit lower bounds from the square of any induced subgraph ideal, so if the monotonicity fails, the lower bound may need a smaller constant or a modified combinatorial invariant.","The quadratic-generation result for colon ideals hints that a similar graph-cover description might work for products of more than two edge ideals without a complete-graph assumption, potentially yielding a recursive formula for reg(J_1···J_d).","The exact formulas for cycles and weakly chordal graphs likely extend to any graph where ν(G)=co-chord(G), so one could test whether reg(IJ)=ν(G)+3 holds for all gap-free graphs with H induced and ν equal."],"forward_implications":["For any subgraph H of G, reg(IJ) ≤ m(G)+3, where m(G) is the matching number of G (Corollary 3.6).","If H is an induced subgraph of G with ν(H)=ν(G), then reg(IJ)=ν(G)+3 whenever G is a cycle on 3n vertices, weakly chordal, unmixed bipartite, or bipartite with regularity 3 (Corollary 4.1).","If J has a linear resolution, then IJ has a linear resolution when reg(I) ≤ 4, and reg(IJ)=reg(I) when reg(I) ≥ 5 (Theorem 4.3).","For a chain of d=3 or 4 edge ideals with J_d the complete graph, the product has linear resolution if reg(J_1···J_{d−1}) ≤ 2d, and its regularity equals that of the shorter product otherwise (Theorem 4.6).","The upper bound reg(IJ) ≤ max{reg(J)+3, reg(I)} is sharp, as a 16-cycle with a perfect-matching subgraph shows (Example 3.10)."],"supporting_citations":[{"why":"Supplies the Betti-number comparison for powers of edge ideals of induced subgraphs and the value reg(I(Q)^2)=ν+3 that the lower bound extends to the product IJ.","marker":"[4]"},{"why":"Gives the template bounds ν(G)+1 ≤ reg(I(G)) ≤ co-chord(G)+1 for a single edge ideal, which the product bounds mimic and use in the upper-bound proof.","marker":"[23]"},{"why":"Provides the edge-ordering characterization of co-chordal graphs used in Lemma 3.4 to show the enlarged graph P has co-chordal cover at most that of G.","marker":"[3]"},{"why":"Polarization and the equality reg(I)=reg(~I) (Corollary 2.2) convert colon ideals into edge ideals, a step used throughout the upper-bound arguments.","marker":"[14]"},{"why":"Bounds the regularity of colon ideals, feeding the short exact sequence argument in Theorems 3.5 and 3.9.","marker":"[18]"},{"why":"Provides regularity bounds for induced subgraphs, used in Theorem 3.9 to handle the graph P attached to the colon ideal.","marker":"[16]"},{"why":"Proves that the edge ideal of a complete graph has linear resolution, used in Theorem 4.6 for products where the largest ideal is the complete graph.","marker":"[12]"},{"why":"Gives conditions under which ν(G)=co-chord(G) for bipartite graphs, used in Corollary 4.1 for exact formulas.","marker":"[17]"}],"fun_headline_variants":["Bounds and exact formulas for regularity of edge-ideal products","Induced matchings and co-chordal covers bound regularity of edge-ideal products","Regularity of edge-ideal products: induced matching and co-chordal bounds","Regularity of edge-ideal products: exact values for several graph classes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound requires that a known Betti-number comparison for powers of an edge ideal also holds for the product of two different edge ideals; the paper asserts this extension without proof, and if it fails the bound ν_GH+3 could break.","fun_headline_variants_meta":{"raw":{"variants":["Bounds and exact formulas for regularity of edge-ideal products","Induced matchings and co-chordal covers bound regularity of edge-ideal products","Regularity of edge-ideal products: induced matching and co-chordal bounds","Regularity of edge-ideal products: exact values for several graph classes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000815,"raw_usage":{"total_tokens":3532,"prompt_tokens":866,"completion_tokens":2666,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":2585}},"tokens_in":482,"tokens_out":2666,"duration_ms":17316,"temperature":1.0,"reasoning_tokens":2585,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:40:27.410928+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compare the graded Betti numbers of I(Q)^2 and IJ for a pair of graphs H ⊆ G that share an induced matching Q using a computer algebra system; a single pair with β_{i,j}(I(Q)^2) > β_{i,j}(IJ) would invalidate the proof of the lower bound in Theorem 3.3.","supporting_citations":[{"cited_title":"Beyarslan, H","cited_arxiv_id":null,"evidence_quote":"Supplies the Betti-number comparison for powers of edge ideals of induced subgraphs and the value reg(I(Q)^2)=ν+3 that the lower bound extends to the product IJ."},{"cited_title":"W oodroofe","cited_arxiv_id":null,"evidence_quote":"Gives the template bounds ν(G)+1 ≤ reg(I(G)) ≤ co-chord(G)+1 for a single edge ideal, which the product bounds mimic and use in the upper-bound proof."},{"cited_title":"Benzaken, Y","cited_arxiv_id":null,"evidence_quote":"Provides the edge-ordering characterization of co-chordal graphs used in Lemma 3.4 to show the enlarged graph P has co-chordal cover at most that of G."},{"cited_title":"Herzog and T","cited_arxiv_id":null,"evidence_quote":"Polarization and the equality reg(I)=reg(~I) (Corollary 2.2) convert colon ideals into edge ideals, a step used throughout the upper-bound arguments."},{"cited_title":"Kalai and R","cited_arxiv_id":null,"evidence_quote":"Bounds the regularity of colon ideals, feeding the short exact sequence argument in Theorems 3.5 and 3.9."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides regularity bounds for induced subgraphs, used in Theorem 3.9 to handle the graph P attached to the colon ideal."},{"cited_title":"Fr¨ oberg","cited_arxiv_id":null,"evidence_quote":"Proves that the edge ideal of a complete graph has linear resolution, used in Theorem 4.6 for products where the largest ideal is the complete graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives conditions under which ν(G)=co-chord(G) for bipartite graphs, used in Corollary 4.1 for exact formulas."}],"review_version":1}