CS Paper Radar

Diameter bounds for complexes that are close to flag or close to normal

Bruno Benedetti, Giuliamaria Menara

cs.DM math.COmath.MG ·submitted 2026-11-05 14:23 UTC · v1

Abstract

The Hirsch problem asks how large the diameter of the dual graph of a simplicial complex can be, in terms of its number of vertices. For normal complexes, the classical bounds are the Larman-Barnette bound, which is linear for fixed dimension, the Kalai-Kleitman bound, which is quasi-polynomial, and the Adiprasito-Benedetti bound n-d, which however holds only for flag complexes. After sharpening the Larman-Barnette and the Kalai-Kleitman bounds, we study how the three bounds deteriorate when flagness or normality is weakened. We give three ways to quantify the distance from flagness, and in each case we bound the diameter in a way that interpolates between the Adiprasito-Benedetti and the Larman-Barnette bounds. We also quantify the distance from normality by a parameter q, and obtain a bound that is a polynomial of degree q in n. Finally, we conjecture a statement on flag layered families that would imply an interpolation between the Adiprasito-Benedetti and the Kalai-Kleitman bounds.

Comment
22 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A data structure for quotient flag complexes

cs.CG math.ATcs.DS ·2026-09-26 ·Konstantin Sorokin, Aleksandr Levin, Maxim Beketov, Anton Ayzenberg
similarity 0.63
Abstract

Vietoris-Rips filtrations, which are standard in topological data analysis, are flag complexes, and a simplex tree stores these without any attaching data. In this paper we ask what survives of this economy when a flag complex $K$ is divided by a subcomplex $A$, each connected component of $A$ being crushed to a point. Such a quotient is a CW complex whose cells are the simplices of $K\setminus A$, but their attaching maps are no longer implicit. We show that for flag $K$ the face order of the quotient is strictly graded exactly when $A$ is flag, and that the surviving labelled cells are determined by those of dimension at most 3. For $m$-flag pairs the threshold is $2m+1$, and it drops to $m+2$ when $K$ is flag. The prescribed cells form a regular CW decomposition only when $A$ is full in $K$. These results justify the QF-tree: a cell table that stores, for each surviving simplex, its ordered list of $d+1$ facets with collapsed facets flagged, indexed by a trie of quotient-vertex words. For bounded dimension its size is linear in the number of surviving simplices plus the retained provenance, and we derive and verify a simple formula for the collapsed fraction above which it is smaller than the homotopy-equivalent cone model. Because a collapse changes the attaching data only on the closed star of $A$, the QF-tree can also be applied locally inside a simplex tree. For a ball-shaped $A$ in the sampled Vietoris--Rips regime the closed star is a thin shell, and the median compact budget is below the cone model at every sampled radius. An accompanying library, modelled on Gudhi, implements the QF-tree, its local variant, an editable layer with local quotient updates, gluing, disc attachment, induced maps, cup products, fundamental-group presentations and zigzag persistence, and provided experiments separate the cost of maintaining a quotient from the cost of the algebra computed on it.

0.33

Asymptotic dimension of graphs excluding an induced or fat minor

cs.DM math.CO ·2026-10-15 ·Robert Hickingbotham, Freddie Illingworth, Piotr Micek, Bartosz Walczak
theory similarity 0.57
Abstract

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed graph $H$, the class of graphs excluding $H$ as a fat minor has bounded asymptotic dimension. A weaker conjecture asserts the same conclusion for graphs excluding $H$ as an induced minor. We substantially expand the range of graphs $H$ for which these conjectures are known to hold. Specifically, we prove bounded asymptotic dimension for the following classes of graphs: graphs excluding a fixed planar graph as a fat minor; and graphs excluding a fixed string graph as an induced minor. All of our results also hold for the stronger notion of Assouad--Nagata dimension, a refinement of asymptotic dimension. These results have a number of applications, two of which we mention here. First they imply that an induced minor-closed class is $χ$-bounded if and only if it does not contain some Burling graph. Second they imply that, in graph classes excluding a fixed planar graph as an induced minor, treewidth is polynomial in maximum degree.

0.24

Asymptotically good codes from Siegel modular varieties

cs.IT math.NTmath.AG ·2026-11-10 ·Yota Maeda
theory similarity 0.56
Abstract · 26 pages, v2:Acknowledgments added

We construct asymptotically good codes by evaluating Siegel modular forms at superspecial points on congruence towers of Siegel modular varieties. For every genus $g\ge2$ and every fixed weight $w\ge g+1$, the construction gives such a family in sufficiently large characteristic, over a finite field which is independent of the level of the tower. The towers can be chosen so that this field is $\mathbb{F}_{p^2}$. We give an explicit lower bound for the asymptotic rate. The lower bound for the relative minimum distance follows from the Pieri formula on the space of flags in the Hodge bundle and an intersection argument along its strata. We also prove that, for $p\ge5$ and $0\le w\le p+1$, the kernel of evaluation in every genus consists precisely of the multiples of the ordinary Hasse invariant. For $g=2,3$, the geometry of the supersingular locus gives explicit bounds for the relative minimum distance and recovery sets whose sizes are bounded independently of the level.

0.17

Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers

cs.DM math.CO ·2026-10-10 ·Yusuke Watanabe
theorycode/data similarity 0.55
Abstract · 39 pages. Main Theorems A-C formalized in Lean 4; code: https://github.com/ywatanabex/coefficientwise-rigidity-lean

Let $G$ be a finite bipartite graph and let $\widetilde G$ be an $M$-fold cover. We compare independent sets of $\widetilde G$ with those of the trivial cover, consisting of $M$ disjoint copies of $G$, after prescribing how many vertices are selected above each vertex of $G$. A conjecture from 2011, motivated by the Bethe approximation, asserts that the trivial cover maximizes every such count. We prove this for every feasible occupation profile whose active graph has treewidth at most two or is chordal bipartite. Equality holds exactly when the restricted cover is flat, meaning that fibre relabelings make it trivial. For $M\ge2$ and positive feasible occupations, a nonflat cover of a connected bipartite graph of treewidth at most two has a deficit of at least twice the coefficient of $p_G^{M-2}$ with every occupation reduced by one. A holonomy-dependent bound improves the factor to three for odd-order holonomy; both uniform constants are sharp. Comparison and rigidity survive finite compositions along an edge or a vertex, and quantitative bounds from one piece propagate to the whole graph, giving results beyond the two original classes. On any bipartite base, the first nonzero homogeneous defect is determined by the shortest cycles with nontrivial holonomy. At singleton occupations, our counts are numbers of DP-colorings of full covers. The dual DP color function on these classes and their finite seam compositions equals the chromatic polynomial, with equality attained precisely by canonical labelings. Dong's chromatic-polynomial inequality then yields the Dual-DP Shameful inequality on the same graph class. The main theorems have been formalized in Lean 4.

0.28

Some algebraic and geometric computations in CH via Chow forms

cs.CC cs.SC ·2026-11-03 ·Robert Andrews, Abhibhav Garg, Rafael Oliveira, Éric Schost
similarity 0.55
Abstract

The problem of decomposing an algebraic variety into more structured components (such as equidimensional, irreducible, or connected components) is a fundamental problem in computer algebra and algebraic geometry. In this work, we study the computational complexity of computing equidimensional components of algebraic varieties, represented via Chow forms. We improve the state-of-the-art complexity bounds from PSPACE to CH, the counting hierarchy, for a number of problems related to equidimensional decomposition, including deciding (1) whether the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety vanishes at a given point, (2) whether a given monomial is in the support of the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety, (3) membership in a given equidimensional component of a given algebraic variety, and (4) membership in the closure of the image of an irreducible variety under a polynomial map. As an application of our algorithm to decide membership in the closure of the image of a variety under a polynomial map, we show that the approximate polynomial satisfiability problem can be decided in CH. We also show that the degree of the $k^{\text{th}}$ equidimensional component of a given projective variety can be computed in $\text{FP}^{\text{CH}}$. Our main technical result is the construction of a polylogtime-uniform family of constant-depth, exponential-size threshold circuits that compute the Chow forms of the equidimensional components of a given projective variety. We construct these circuits by combining the machinery of geometric resolutions together with the uniform constant-depth, exponential-size threshold circuits of Andrews, Garg, and Schost (FOCS 2026) for the multivariate resultant.

0.19

Torsion detection in clique complexes is conditionally $QMA_1$-hard

cs.CC quant-ph ·2026-09-12 ·Adam Wesołowski
similarity 0.54
Abstract

Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the kernel of a combinatorial Laplacian. Deciding whether a Betti number of a clique complex is nonzero is $QMA_1$-hard, and remains so under a spectral gap promise on vertex-weighted graphs. Integral homology, however, contains information inaccessible to the Laplacian spectrum. A new part that appears in integral homology is \emph{torsion}: cycles that become boundaries only after being traversed several times, as in a projective plane or a Klein bottle. We provide a simple reduction that allows us to establish the first hardness results for the problem of detecting torsion. We attach to an arbitrary clique complex a fixed $31$-vertex triangulation of the projective plane. The $k$th mod-$2$ Betti number of the input then reappears as $2$-torsion two degrees up, while all rational homology disappears and every combinatorial Laplacian acquires a constant spectral gap. We conclude that detecting torsion in clique complexes of \emph{unweighted} graphs is $NP$-hard, even under a constant gap promise, and that it is $QMA_1$-hard if mod-$2$ clique homology is.

0.14

A New Upper Bound for the Turán Density of the Tetrahedron

cs.DM math.COmath.OC ·2026-09-23 ·Gyeongwon Jeong, Seonghun Park, Seonghyuk Im, Joonkyung Lee, Hongseok Yang
theorycode/data similarity 0.54
Abstract · 28 pages, 5 figures, 8 tables. v2: Slightly improved upper bound and updated exact certificate following continuation of the search to conve…

We prove that the Turán density of the tetrahedron $K_4^{(3)}$ satisfies $π(K_4^{(3)}) \le 14993367693127837/26880000000000000 < 0.557789$, improving Baber's upper bound of $0.5615$ and closing about $62\%$ of the gap to the conjectured value $5/9$. The proof uses an exact seven-vertex flag-algebra certificate incorporating degree-stationarity from Razborov's differential method. To find the certificate, we combine the established techniques of cutting planes and column generation to optimize jointly over flag families whose types have at most five vertices. We give a complete formal proof of this Turán density bound in Lean 4.

0.63

Optimal girth-dependent bounds for the Bethe approximation of the permanent

cs.DS math.CO ·2026-09-02 ·Dingding Dong, Vishesh Jain
theoryhot direction similarity 0.54
Abstract · 21 pages; comments welcome!

For an $n\times n$ nonnegative matrix $A$, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{n/2}\operatorname{Bethe}(A).\] The lower bound, due to Gurvits, is attained on forests. The upper bound, due to Anari and Rezaei, is attained by the adjacency matrix of a disjoint union of $4$-cycles. Confirming a conjecture of Anari, we provide an optimal girth-dependent refinement of the above comparison. More precisely, we show that if the bipartite support graph of $A$ has girth at least an even integer $g \geq 4$, then \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{2n/g}\operatorname{Bethe}(A).\] The upper bound is attained by the adjacency matrix of a disjoint union of $g$-cycles.

0.47