Buchumschlag

From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gurvits, Leonid, Klein, Nathan, Leake, Jonathan
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Combinatorics Discrete Mathematics Probability
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Asymptotic Bounds and Online Algorithms for Average-Case Matrix Discrepancy
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Zero-One Laws for Random Feasibility Problems
von: Altschuler, Dylan J.
Veröffentlicht: (2023)

Cliques, Chromatic Number, and Independent Sets in the Semi-random Process
von: Gamarnik, David, et al.
Veröffentlicht: (2023)

A binomial random multigraph
von: Pelekis, Christos
Veröffentlicht: (2023)

Canonical labelling of random regular graphs
von: Isaev, Mikhail, et al.
Veröffentlicht: (2026)

On the Asymptotics of the Connectivity Probability of Random Bipartite Graphs
von: Chinyaev, Boris
Veröffentlicht: (2025)

A threshold for online balancing of sparse i.i.d. vectors
von: Altschuler, Dylan J., et al.
Veröffentlicht: (2025)

Speeding up random walk mixing by starting from a uniform vertex
von: Díaz, Alberto Espuny, et al.
Veröffentlicht: (2022)

Limit Laws for Critical Dispersion on Complete Graphs
von: De Ambroggio, Umberto, et al.
Veröffentlicht: (2024)

Shotgun assembly of random graphs
von: Johnston, Tom, et al.
Veröffentlicht: (2022)

Infinite Schnyder Woods
von: Addario-Berry, Louigi, et al.
Veröffentlicht: (2025)

Expected Length of the Longest Common Subsequence of Multiple Strings
von: Li, Ray, et al.
Veröffentlicht: (2025)

Approximate polymorphisms of predicates
von: Alekseev, Yaroslav, et al.
Veröffentlicht: (2025)

Record-biased permutations and their permuton limit
von: Bouvel, Mathilde, et al.
Veröffentlicht: (2024)

A Proof of Talagrand's Creating Large Sets Conjecture
von: Fang, Xuan, et al.
Veröffentlicht: (2025)

A sharp version of Talagrand's selector process conjecture and an application to rounding fractional covers
von: Pham, Huy Tuan
Veröffentlicht: (2024)

The Chvátal-Sankoff problem: Understanding random string comparison through stochastic processes
von: Tiskin, Alexander
Veröffentlicht: (2022)

Sunflowers in set systems with small VC-dimension
von: Balogh, József, et al.
Veröffentlicht: (2024)

Minimum stationary values of sparse random directed graphs
von: Cai, Xing Shi, et al.
Veröffentlicht: (2020)

Spread blow-up lemma with an application to perturbed random graphs
von: Nenadov, Rajko, et al.
Veröffentlicht: (2024)

Counterexamples to an Extremal Conjecture for Random Cycle-Factors
von: Gajjala, Rishikesh
Veröffentlicht: (2026)

A lower bound on the spectrum of unimodular networks
von: Rahman, Mustazee
Veröffentlicht: (2016)

Random 0/1-polytopes expand rapidly
von: Guo, He, et al.
Veröffentlicht: (2026)

Diameter Bounds for Friends-and-Strangers Graphs
von: Akella, Amogh, et al.
Veröffentlicht: (2025)

Polynomial Bounds in the Apex Minor Theorem
von: Hendrey, Kevin, et al.
Veröffentlicht: (2025)

Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees
von: Bencs, Ferenc, et al.
Veröffentlicht: (2023)

Cutoff profile of the Metropolis biased card shuffling
von: Zhang, Lingfu
Veröffentlicht: (2022)

Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration
von: Bangachev, Kiril, et al.
Veröffentlicht: (2024)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
von: Bansal, Nikhil, et al.
Veröffentlicht: (2025)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
von: Gutekunst, Samuel C.
Veröffentlicht: (2025)

Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials
von: Ai, Jiangdong, et al.
Veröffentlicht: (2024)

Smoothed Analysis of the Komlós Conjecture: Rademacher Noise
von: Aigner-Horev, Elad, et al.
Veröffentlicht: (2023)

Rapid mixing of the flip chain over non-crossing spanning trees
von: Anand, Konrad, et al.
Veröffentlicht: (2024)

On the clique number of random Cayley graphs and related topics
von: Conlon, David, et al.
Veröffentlicht: (2024)

The maximal hard-core model as a recoverable system: Gibbs measures and phase coexistence
von: Wang, Geyang, et al.
Veröffentlicht: (2025)

An Explicit Formula for Vertex Enumeration in the CUT(n) Polytope via Probabilistic Methods
von: Marić, Nevena
Veröffentlicht: (2025)

Recoverable systems and the maximal hard-core model on the triangular lattice
von: Wang, Geyang, et al.
Veröffentlicht: (2026)

Graph-theoretical estimates of the diameters of the Rubik's Cube groups
von: Hirata, So
Veröffentlicht: (2024)

Decoupling of clusters in independent sets in a percolated hypercube
von: Chowdhury, Mriganka Basu Roy, et al.
Veröffentlicht: (2025)

Gaussian to log-normal transition for independent sets in a percolated hypercube
von: Chowdhury, Mriganka Basu Roy, et al.
Veröffentlicht: (2024)