{"id":"131246a9-26b9-4df2-a0da-674e45d29f43","arxiv_id":"2604.21847","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Efficient sampling algorithm for the hardcore model on random regular bipartite graphs for λ ≲ 1/√Δ, implying an FPRAS for the partition function at all fugacities via combination with prior work.","lead":"The paper designs an efficient sampling algorithm for the hardcore model on random regular bipartite graphs when the fugacity λ is at most roughly 1 over the square root of the degree. Combined with prior results, this yields an FPRAS for the partition function at any fugacity.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"The proof that the simplicial complexes are top-link spectral expanders is the single load-bearing step for applying trickle-down to the two Markov chains.","rationale":"The reader's weakest_assumption isolates precisely the step whose correctness determines whether the two chains mix rapidly enough to yield the stated sampling algorithm. No other part of the argument (regime complementarity, combination with Jenssen–Keevash–Perkins, or the random-graph model) can rescue the claim if this spectral property does not hold.","tokens_in":1637,"tokens_out":348,"duration_ms":36350,"concrete_test":"In the section proving top-link expansion, recompute the second eigenvalue of the link graph for a fixed top-dimensional face on a Δ=4 random regular bipartite graph with λ=0.4; if the resulting gap is smaller than the minimum required by the cited trickle-down theorem, the mixing bound fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The sampling algorithm is established by constructing two new Markov chains that operate in complementary regimes up to λ ≲ 1/√Δ and proving fast mixing via the trickle-down theorem once the associated simplicial complexes are shown to be top-link spectral expanders. For random regular bipartite graphs this requires the second eigenvalue of every top link to be bounded below the threshold needed by trickle-down (typically a gap of 1 − O(1/k) in dimension k), and the bound must hold with high probability over the random graph. If the expansion constant degrades exactly at λ ∼ 1/√Δ or fails to be uniform in the random model, the mixing-time guarantee collapses and the FPRAS claim does not follow.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper designs an efficient sampling algorithm for the hardcore model on random regular bipartite graphs for λ ≲ 1/√Δ. It constructs two new Markov chains operating in complementary regimes, proves fast mixing by showing that the associated simplicial complexes are top-link spectral expanders, and invokes the trickle-down theorem. Combined with the work of Jenssen, Keevash and Perkins, this yields an FPRAS for the partition function at any fugacity.","tokens_in":1799,"tokens_out":362,"duration_ms":55578,"significance":"If the central claims hold, the result completes the picture for approximate sampling and counting in the hardcore model on random regular bipartite graphs by covering the regime up to the uniqueness threshold, where prior techniques were insufficient. The technical approach of establishing top-link expansion to apply the trickle-down theorem is a notable contribution that strengthens the connection between high-dimensional expanders and MCMC analysis for statistical physics models.","major_comments":[{"comment":"The proof that the simplicial complexes are top-link spectral expanders (as stated in the abstract and developed in the main analysis) is the single load-bearing step for the fast-mixing claims. Explicit bounds must be given showing that the second eigenvalue of every top link satisfies the gap condition required by the trickle-down theorem (typically a gap of 1 − O(1/k) in dimension k) with high probability over the random regular bipartite graph, uniformly up to λ ≲ 1/√Δ. If the expansion constant degrades exactly at this threshold or fails to be uniform, the mixing-time guarantees for both chains collapse.","section":"Abstract and the section establishing top-link spectral expansion"}],"minor_comments":[],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their careful reading of the manuscript and for highlighting the importance of the top-link spectral expansion argument. We agree that this is the central technical step and appreciate the opportunity to strengthen the presentation of the eigenvalue bounds.","responses":[{"response":"We agree that explicit, uniform bounds on the second eigenvalue are necessary to rigorously invoke the trickle-down theorem. Our current analysis already shows that the relevant simplicial complexes are top-link spectral expanders with high probability for λ ≲ 1/√Δ, but the eigenvalue gap is stated in asymptotic form. In the revised manuscript we will add an explicit derivation (in a new subsection of the main analysis and a supporting appendix) establishing that every top link has second eigenvalue at most 1 − Ω(1/k) with high probability, uniformly over the stated range of λ. The argument uses the random regular bipartite structure and a direct spectral calculation that remains valid up to the uniqueness threshold; we will also include a short paragraph confirming that the gap does not degrade at the boundary of the regime. This change will make the application of the trickle-down theorem fully explicit for both Markov chains without altering any claims.","revision_made":"yes","referee_comment":"[Abstract and the section establishing top-link spectral expansion] The proof that the simplicial complexes are top-link spectral expanders (as stated in the abstract and developed in the main analysis) is the single load-bearing step for the fast-mixing claims. Explicit bounds must be given showing that the second eigenvalue of every top link satisfies the gap condition required by the trickle-down theorem (typically a gap of 1 − O(1/k) in dimension k) with high probability over the random regular bipartite graph, uniformly up to λ ≲ 1/√Δ. If the expansion constant degrades exactly at this threshold or fails to be uniform, the mixing-time guarantees for both chains collapse."}],"tokens_in":1257,"tokens_out":408,"duration_ms":33234,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point is that the authors close the remaining regime for approximate sampling of the hardcore model on random regular bipartite graphs. Their algorithm works for fugacity λ up to about 1 over square root of degree, and when combined with the Jenssen-Keevash-Perkins result it covers all λ and gives an FPRAS for the partition function. That is the concrete advance here.","headline":"This paper gives a sampling algorithm for the hardcore model on random regular bipartite graphs up to λ roughly 1/sqrt(Δ) via two new Markov chains whose mixing follows from top-link expansion and the trickle-down theorem, which plus prior work yields an FPRAS for every fugacity.","tokens_in":2300,"tokens_out":182,"would_cite":false,"duration_ms":12998,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"An efficient sampling algorithm generates independent sets from the hardcore model on random regular bipartite graphs for fugacity up to roughly 1 over square root of the degree.","keywords":["hardcore model","sampling algorithms","random regular bipartite graphs","Markov chain Monte Carlo","spectral expanders","trickle-down theorem","partition function","fugacity"],"falsifier":"A direct computation showing that the mixing time of either Markov chain becomes super-polynomial on a random regular bipartite graph for some λ slightly larger than 1/√Δ would disprove the efficiency of the sampler.","tokens_in":2534,"feed_emoji":"","tokens_out":755,"duration_ms":24658,"temperature":0.7,"pith_summary":"The paper establishes an efficient algorithm for sampling from the hardcore model on random regular bipartite graphs when the fugacity parameter λ is at most about 1 over square root of the graph degree. It introduces two new Markov chains that handle complementary regimes of the parameter space and proves their rapid mixing by showing that associated simplicial complexes are top-link spectral expanders, then applying the trickle-down theorem. A reader would care because this extends the range of efficient sampling beyond the uniqueness threshold and, when combined with earlier results, yields a fully polynomial randomized approximation scheme for the partition function at every fugacity value. The approach relies on high-dimensional expansion to control the dynamics of the chains.","feed_headline":"Efficient sampler for hardcore model on bipartite graphs up to λ ≲ 1/√Δ","feed_subtitle":"Two Markov chains with top-link expansion yield fast mixing and an FPRAS for the partition function at any fugacity.","key_machinery":"Two complementary Markov chains whose state spaces are simplicial complexes shown to be top-link spectral expanders, with fast mixing proved via the trickle-down theorem.","core_discovery":"We design an efficient sampling algorithm to generate samples from the hardcore model on random regular bipartite graphs as long as λ ≲ 1/√Δ, where Δ is the degree. Combined with recent work of Jenssen, Keevash and Perkins this implies an FPRAS for the partition function of the hardcore model on random regular bipartite graphs at any fugacity. Our algorithm is shown by analyzing two new Markov chains that work in complementary regimes. Our proof then proceeds by showing the corresponding simplicial complexes are top-link spectral expanders and appealing to the trickle-down theorem to prove fast mixing.","pith_inferences":["The same expansion-based technique may extend to sampling other spin systems on bipartite graphs with similar degree regularity.","Top-link spectral expansion could serve as a general criterion for designing fast-mixing chains in high-dimensional settings beyond the hardcore model.","If the expansion property holds for a wider range of λ, the sampling threshold could be pushed closer to the computational limit.","The method suggests that proving expansion in top links might simplify analysis for other Markov chains used in approximate counting."],"forward_implications":["Samples from the hardcore model can be generated in polynomial time for all λ ≲ 1/√Δ on random regular bipartite graphs.","An FPRAS for the partition function holds for the hardcore model on these graphs at every fugacity value.","The two Markov chains mix rapidly in their respective regimes because of the top-link expansion property.","The uniqueness threshold can be surpassed for sampling purposes on this family of graphs."],"fun_headline_variants":["Hardcore model sampling on random regular bipartite graphs for λ ≲ 1/√Δ","Markov chains sample hardcore model on random bipartite graphs up to λ ≲ 1/√Δ","Spectral expanders show fast mixing for hardcore model on bipartite graphs","FPRAS for hardcore partition function on random regular bipartite graphs"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The simplicial complexes for the two Markov chains are top-link spectral expanders.","fun_headline_variants_meta":{"raw":{"variants":["Hardcore model sampling on random regular bipartite graphs for λ ≲ 1/√Δ","Markov chains sample hardcore model on random bipartite graphs up to λ ≲ 1/√Δ","Spectral expanders show fast mixing for hardcore model on bipartite graphs","FPRAS for hardcore partition function on random regular bipartite graphs"]},"model":"grok-4.3","cost_usd":0.012253,"raw_usage":{"total_tokens":5230,"prompt_tokens":604,"num_sources_used":0,"completion_tokens":84,"cost_in_usd_ticks":122528000,"prompt_tokens_details":{"text_tokens":604,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":4542,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":604,"tokens_out":84,"duration_ms":47137,"temperature":1.0,"reasoning_tokens":4542,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-09T20:00:13.281881+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A direct computation showing that the mixing time of either Markov chain becomes super-polynomial on a random regular bipartite graph for some λ slightly larger than 1/√Δ would disprove the efficiency of the sampler.","supporting_citations":[],"review_version":1}