Title: Efficient simplicial replacement of semialgebraic sets
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 )}}$.
Chan, William; Jackson, Stephen; Trang, Nam(
, Forum of Mathematics, Sigma)
Abstract
This paper will study almost everywhere behaviors of functions on partition spaces of cardinals possessing suitable partition properties. Almost everywhere continuity and monotonicity properties for functions on partition spaces will be established. These results will be applied to distinguish the cardinality of certain subsets of the power set of partition cardinals.
The following summarizes the main results proved under suitable partition hypotheses.
If$\kappa $is a cardinal,$\epsilon < \kappa $,${\mathrm {cof}}(\epsilon ) = \omega $,$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$and$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$, then$\Phi $satisfies the almost everywhere short length continuity property: There is a club$C \subseteq \kappa $and a$\delta < \epsilon $so that for all$f,g \in [C]^\epsilon _*$, if$f \upharpoonright \delta = g \upharpoonright \delta $and$\sup (f) = \sup (g)$, then$\Phi (f) = \Phi (g)$.
If$\kappa $is a cardinal,$\epsilon $is countable,$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$holds and$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$, then$\Phi $satisfies the strong almost everywhere short length continuity property: There is a club$C \subseteq \kappa $and finitely many ordinals$\delta _0, ..., \delta _k \leq \epsilon $so that for all$f,g \in [C]^\epsilon _*$, if for all$0 \leq i \leq k$,$\sup (f \upharpoonright \delta _i) = \sup (g \upharpoonright \delta _i)$, then$\Phi (f) = \Phi (g)$.
If$\kappa $satisfies$\kappa \rightarrow _* (\kappa )^\kappa _2$,$\epsilon \leq \kappa $and$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$, then$\Phi $satisfies the almost everywhere monotonicity property: There is a club$C \subseteq \kappa $so that for all$f,g \in [C]^\epsilon _*$, if for all$\alpha < \epsilon $,$f(\alpha ) \leq g(\alpha )$, then$\Phi (f) \leq \Phi (g)$.
Suppose dependent choice ($\mathsf {DC}$),${\omega _1} \rightarrow _* ({\omega _1})^{\omega _1}_2$and the almost everywhere short length club uniformization principle for${\omega _1}$hold. Then every function$\Phi : [{\omega _1}]^{\omega _1}_* \rightarrow {\omega _1}$satisfies a finite continuity property with respect to closure points: Let$\mathfrak {C}_f$be the club of$\alpha < {\omega _1}$so that$\sup (f \upharpoonright \alpha ) = \alpha $. There is a club$C \subseteq {\omega _1}$and finitely many functions$\Upsilon _0, ..., \Upsilon _{n - 1} : [C]^{\omega _1}_* \rightarrow {\omega _1}$so that for all$f \in [C]^{\omega _1}_*$, for all$g \in [C]^{\omega _1}_*$, if$\mathfrak {C}_g = \mathfrak {C}_f$and for all$i < n$,$\sup (g \upharpoonright \Upsilon _i(f)) = \sup (f \upharpoonright \Upsilon _i(f))$, then$\Phi (g) = \Phi (f)$.
Suppose$\kappa $satisfies$\kappa \rightarrow _* (\kappa )^\epsilon _2$for all$\epsilon < \kappa $. For all$\chi < \kappa $,$[\kappa ]^{<\kappa }$does not inject into${}^\chi \mathrm {ON}$, the class of$\chi $-length sequences of ordinals, and therefore,$|[\kappa ]^\chi | < |[\kappa ]^{<\kappa }|$. As a consequence, under the axiom of determinacy$(\mathsf {AD})$, these two cardinality results hold when$\kappa $is one of the following weak or strong partition cardinals of determinacy:${\omega _1}$,$\omega _2$,$\boldsymbol {\delta }_n^1$(for all$1 \leq n < \omega $) and$\boldsymbol {\delta }^2_1$(assuming in addition$\mathsf {DC}_{\mathbb {R}}$).
Galvin, David; McKinley, Gwen; Perkins, Will; Sarantis, Michail; Tetali, Prasad(
, Combinatorics, Probability and Computing)
Abstract
We study the locations of complex zeroes of independence polynomials of bounded-degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer’s result on the optimal zero-free disc, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree$\Delta$have a zero-free disc almost as large as the optimal disc for graphs of maximum degree$\Delta$established by Shearer (of radius$\sim 1/(e \Delta )$). Up to logarithmic factors in$\Delta$this is optimal, even for hypergraphs with all edge sizes strictly greater than$2$. We conjecture that for$k\ge 3$,$k$-uniformlinearhypergraphs have a much larger zero-free disc of radius$\Omega (\Delta ^{- \frac{1}{k-1}} )$. We establish this in the case of linear hypertrees.
Sargsyan, Grigor; Trang, Nam(
, Forum of Mathematics, Sigma)
Abstract
A set of reals isuniversally Baireif all of its continuous preimages in topological spaces have the Baire property.$\mathsf {Sealing}$is a type of generic absoluteness condition introduced by Woodin that asserts in strong terms that the theory of the universally Baire sets cannot be changed by forcing.
The$\mathsf {Largest\ Suslin\ Axiom}$($\mathsf {LSA}$) is a determinacy axiom isolated by Woodin. It asserts that the largest Suslin cardinal is inaccessible for ordinal definable bijections. Let$\mathsf {LSA-over-uB}$be the statement that in all (set) generic extensions there is a model of$\mathsf {LSA}$whose Suslin, co-Suslin sets are the universally Baire sets.
We show that over some mild large cardinal theory,$\mathsf {Sealing}$is equiconsistent with$\mathsf {LSA-over-uB}$. In fact, we isolate an exact large cardinal theory that is equiconsistent with both (see Definition 2.7). As a consequence, we obtain that$\mathsf {Sealing}$is weaker than the theory ‘$\mathsf {ZFC} +$there is a Woodin cardinal which is a limit of Woodin cardinals’.
A variation of$\mathsf {Sealing}$, called$\mathsf {Tower\ Sealing}$, is also shown to be equiconsistent with$\mathsf {Sealing}$over the same large cardinal theory.
The result is proven via Woodin’s$\mathsf {Core\ Model\ Induction}$technique and is essentially the ultimate equiconsistency that can be proven via the current interpretation of$\mathsf {CMI}$as explained in the paper.
Ergemlidze, Beka; Molla, Theodore(
, Combinatorics, Probability and Computing)
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.
Based on a generalized local Kolmogorov–Hill equation expressing the evolution of kinetic energy integrated over spheres of size$\ell$in the inertial range of fluid turbulence, we examine a possible definition of entropy and entropy generation for turbulence. Its measurement from direct numerical simulations in isotropic turbulence leads to confirmation of the validity of the fluctuation relation (FR) from non-equilibrium thermodynamics in the inertial range of turbulent flows. Specifically, the ratio of probability densities of forward and inverse cascade at scale$\ell$is shown to follow exponential behaviour with the entropy generation rate if the latter is defined by including an appropriately defined notion of ‘temperature of turbulence’ proportional to the kinetic energy at scale$\ell$.
Basu, Saugata, and Karisani, Negin. Efficient simplicial replacement of semialgebraic sets. Retrieved from https://par.nsf.gov/biblio/10475721. Forum of Mathematics, Sigma 11. Web. doi:10.1017/fms.2023.36.
@article{osti_10475721,
place = {Country unknown/Code not available},
title = {Efficient simplicial replacement of semialgebraic sets},
url = {https://par.nsf.gov/biblio/10475721},
DOI = {10.1017/fms.2023.36},
abstractNote = {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 )}}$.},
journal = {Forum of Mathematics, Sigma},
volume = {11},
publisher = {Cambridge University Press},
author = {Basu, Saugata and Karisani, Negin},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
