An official website of the United States government
Abstract Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set$$S \subset \mathbb {R}^k$$by a first-order quantifier-free formula in the language of the reals, the goal is to output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$, is semialgebraically homeomorphic toS. In this paper, we consider a weaker version of this question. We prove that for any$$\ell \geq 0$$, there exists an algorithm which takes as input a description of a semialgebraic subset$$S \subset \mathbb {R}^k$$given by a quantifier-free first-order formula$$\phi $$in the language of the reals and produces as output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$is$$\ell $$-equivalent toS. The complexity of our algorithm is bounded by$$(sd)^{k^{O(\ell )}}$$, wheresis the number of polynomials appearing in the formula$$\phi $$, andda bound on their degrees. For fixed$$\ell $$, this bound issingly exponentialink. In particular, since$$\ell $$-equivalence implies that thehomotopy groupsup to dimension$$\ell $$of$$|\Delta |$$are isomorphic to those ofS, we obtain a reduction (having singly exponential complexity) of the problem of computing the first$$\ell $$homotopy groups ofSto the combinatorial problem of computing the first$$\ell $$homotopy groups of a finite simplicial complex of size bounded by$$(sd)^{k^{O(\ell )}}$$.
more »
« less
This content will become publicly available on February 1, 2026
Meridional rank and bridge number of knotted 2-spheres
Abstract The meridional rank conjecture asks whether the bridge number of a knot in$$S^3$$is equal to the minimal number of meridians needed to generate the fundamental group of its complement. In this paper, we investigate the analogous conjecture for knotted spheres in$$S^4$$. Towards this end, we give a construction to produce classical knots with quotients sending meridians to elements of any finite order in Coxeter groups and alternating groups, which detect their meridional ranks. We establish the equality of bridge number and meridional rank for these knots and knotted spheres obtained from them by twist-spinning. On the other hand, we show that the meridional rank of knotted spheres is not additive under connected sum, so that either bridge number also collapses, or meridional rank is not equal to bridge number for knotted spheres.
more »
« less
- Award ID(s):
- 1745670
- PAR ID:
- 10651409
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Canadian Journal of Mathematics
- Volume:
- 77
- Issue:
- 1
- ISSN:
- 0008-414X
- Page Range / eLocation ID:
- 282 to 299
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract For a subset$$A$$of an abelian group$$G$$, given its size$$|A|$$, its doubling$$\kappa =|A+A|/|A|$$, and a parameter$$s$$which is small compared to$$|A|$$, we study the size of the largest sumset$$A+A'$$that can be guaranteed for a subset$$A'$$of$$A$$of size at most$$s$$. We show that a subset$$A'\subseteq A$$of size at most$$s$$can be found so that$$|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$$. Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling$$\kappa$$is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets$$A,B$$of$$\mathbb{F}_p$$of size at most$$\alpha p$$for an appropriate constant$$\alpha \gt 0$$, one only needs three elements$$b_1,b_2,b_3\in B$$to guarantee$$|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$$. Allowing the use of larger subsets$$A'$$, we show that for sets$$A$$of bounded doubling, one only needs a subset$$A'$$with$$o(|A|)$$elements to guarantee that$$A+A'=A+A$$. We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset.more » « less
-
Abstract For a subgraph$$G$$of the blow-up of a graph$$F$$, we let$$\delta ^*(G)$$be the smallest minimum degree over all of the bipartite subgraphs of$$G$$induced by pairs of parts that correspond to edges of$$F$$. Johansson proved that if$$G$$is a spanning subgraph of the blow-up of$$C_3$$with parts of size$$n$$and$$\delta ^*(G) \ge \frac{2}{3}n + \sqrt{n}$$, then$$G$$contains$$n$$vertex disjoint triangles, and presented the following conjecture of Häggkvist. If$$G$$is a spanning subgraph of the blow-up of$$C_k$$with parts of size$$n$$and$$\delta ^*(G) \ge \left(1 + \frac 1k\right)\frac n2 + 1$$, then$$G$$contains$$n$$vertex disjoint copies of$$C_k$$such that each$$C_k$$intersects each of the$$k$$parts exactly once. A similar conjecture was also made by Fischer and the case$$k=3$$was proved for large$$n$$by Magyar and Martin. In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of$$G$$to vary. We support this new conjecture by proving the triangle case. This result generalises Johannson’s result asymptotically.more » « less
-
Abstract Given a family$$\mathcal{F}$$of bipartite graphs, theZarankiewicz number$$z(m,n,\mathcal{F})$$is the maximum number of edges in an$$m$$by$$n$$bipartite graph$$G$$that does not contain any member of$$\mathcal{F}$$as a subgraph (such$$G$$is called$$\mathcal{F}$$-free). For$$1\leq \beta \lt \alpha \lt 2$$, a family$$\mathcal{F}$$of bipartite graphs is$$(\alpha,\beta )$$-smoothif for some$$\rho \gt 0$$and every$$m\leq n$$,$$z(m,n,\mathcal{F})=\rho m n^{\alpha -1}+O(n^\beta )$$. Motivated by their work on a conjecture of Erdős and Simonovits on compactness and a classic result of Andrásfai, Erdős and Sós, Allen, Keevash, Sudakov and Verstraëte proved that for any$$(\alpha,\beta )$$-smooth family$$\mathcal{F}$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\rho (\frac{2n}{5}+o(n))^{\alpha -1}$$is bipartite. In this paper, we strengthen their result by showing that for every real$$\delta \gt 0$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\delta n^{\alpha -1}$$is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families$$\mathcal{F}$$consisting of the single graph$$K_{s,t}$$when$$t\gg s$$. We also prove an analogous result for$$C_{2\ell }$$-free graphs for every$$\ell \geq 2$$, which complements a result of Keevash, Sudakov and Verstraëte.more » « less
-
Abstract We investigate a novel geometric Iwasawa theory for$${\mathbf Z}_p$$-extensions of function fields over a perfect fieldkof characteristic$$p>0$$by replacing the usual study ofp-torsion in class groups with the study ofp-torsion class groupschemes. That is, if$$\cdots \to X_2 \to X_1 \to X_0$$is the tower of curves overkassociated with a$${\mathbf Z}_p$$-extension of function fields totally ramified over a finite nonempty set of places, we investigate the growth of thep-torsion group scheme in the Jacobian of$$X_n$$as$$n\rightarrow \infty $$. By Dieudonné theory, this amounts to studying the first de Rham cohomology groups of$$X_n$$equipped with natural actions of Frobenius and of the Cartier operatorV. We formulate and test a number of conjectures which predict striking regularity in the$$k[V]$$-module structure of the space$$M_n:=H^0(X_n, \Omega ^1_{X_n/k})$$of global regular differential forms as$$n\rightarrow \infty .$$For example, for each tower in a basic class of$${\mathbf Z}_p$$-towers, we conjecture that the dimension of the kernel of$$V^r$$on$$M_n$$is given by$$a_r p^{2n} + \lambda _r n + c_r(n)$$for allnsufficiently large, where$$a_r, \lambda _r$$are rational constants and$$c_r : {\mathbf Z}/m_r {\mathbf Z} \to {\mathbf Q}$$is a periodic function, depending onrand the tower. To provide evidence for these conjectures, we collect extensive experimental data based on new and more efficient algorithms for working with differentials on$${\mathbf Z}_p$$-towers of curves, and we prove our conjectures in the case$$p=2$$and$$r=1$$.more » « less
