Given a sequence $\{Z_d\}_{d\in \mathbb{N}}$ of smooth and compact hypersurfaces in ${\mathbb{R}}^{n1}$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$ such that each manifold $Z_d$ is diffeomorphic to a component of the zero set on $\Gamma$ of some polynomial of degree $d$. (This is in sharp contrast with the case when $\Gamma$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $p$ on $\Gamma$ is bounded by a polynomial in $\deg (p)$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$ containing a subset $D$ homeomorphic to a disk, and a family of polynomials $\{p_m\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that $(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n1}, Z_{d_m}),$ i.e. the zero set of $p_m$ in $D$ is isotopic to $Z_{d_m}$ in ${\mathbb{R}}^{n1}$. This says that, up to extracting subsequences, the intersection of $\Gamma$ with a hypersurface of degree $d$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $0 \leq k \leq n2$ and every sequence of natural numbers $a=\{a_d\}_{d\in \mathbb{N}}$ there is a regular, compact semianalytic hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$, a subsequence $\{a_{d_m}\}_{m\in \mathbb{N}}$ and homogeneous polynomials $\{p_{m}\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $b_k$ denotes the $k$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $\Gamma$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $d$, of the set $\Sigma _{d_m,a, \Gamma }$ of polynomials verifying (0.1) is positive, but there exists a constant $c_\Gamma$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $a$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $\Gamma$, for most polynomials a Bézouttype bound holds for the intersection $\Gamma \cap Z(p)$: for every $0\leq k\leq n2$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n1}{2}}}.\end{equation*}$$
 Award ID(s):
 1651321
 NSFPAR ID:
 10335141
 Date Published:
 Journal Name:
 Forum of Mathematics, Sigma
 Volume:
 9
 ISSN:
 20505094
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 
Let $V_1, V_2, V_3, \dots $ be a sequence of $\mathbb {Q}$vector spaces where $V_n$ carries an action of $\mathfrak{S}_n$. Representation stability and multiplicity stability are two related notions of when the sequence $V_n$ has a limit. An important source of stability phenomena arises when $V_n$ is the $d^{th}$ homology group (for fixed $d$) of the configuration space of $n$ distinct points in some fixed topological space $X$. We replace these configuration spaces with moduli spaces of tuples $(W_1, \dots, W_n)$ of subspaces of a fixed complex vector space $\mathbb {C}^N$ such that $W_1 + \cdots + W_n = \mathbb {C}^N$. These include the varieties of spanning line configurations which are tied to the Delta Conjecture of symmetric function theory.more » « less

For each odd integer
$n \geq 3$ , we construct a rank3 graph$\Lambda _n$ with involution$\gamma _n$ whose real$C^*$ algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)$ is stably isomorphic to the exotic Cuntz algebra$\mathcal E_n$ . This construction is optimal, as we prove that a rank2 graph with involution$(\Lambda ,\gamma )$ can never satisfy$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n$ , and Boersema reached the same conclusion for rank1 graphs (directed graphs) in [Münster J. Math.10 (2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank1 graph with involution$(\Lambda , \gamma )$ whose real$C^*$ algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )$ is stably isomorphic to the suspension$S \mathbb {R}$ . In the Appendix, we show that the$i$ fold suspension$S^i \mathbb {R}$ is stably isomorphic to a graph algebra iff$2 \leq i \leq 1$ . 
One of the most intruguing conjectures in extremal graph theory is the conjecture of Erdős and Sós from 1962, which asserts that every $n$vertex graph with more than $\frac{k1}{2}n$ edges contains any $k$edge tree as a subgraph. Kalai proposed a generalization of this conjecture to hypergraphs. To explain the generalization, we need to define the concept of a tight tree in an $r$uniform hypergraph, i.e., a hypergraph where each edge contains $r$ vertices. A tight tree is an $r$uniform hypergraph such that there is an ordering $v_1,\ldots,v_n$ of its its vertices with the following property: the vertices $v_1,\ldots,v_r$ form an edge and for every $i>r$, there is a single edge $e$ containing the vertex $v_i$ and $r1$ of the vertices $v_1,\ldots,v_{i1}$, and $e\setminus\{v_i\}$ is a subset of one of the edges consisting only of vertices from $v_1,\ldots,v_{i1}$. The conjecture of Kalai asserts that every $n$vertex $r$uniform hypergraph with more than $\frac{k1}{r}\binom{n}{r1}$ edges contains every $k$edge tight tree as a subhypergraph. The recent breakthrough results on the existence of combinatorial designs by Keevash and by Glock, Kühn, Lo and Osthus show that this conjecture, if true, would be tight for infinitely many values of $n$ for every $r$ and $k$.The article deals with the special case of the conjecture when the sought tight tree is a path, i.e., the edges are the $r$tuples of consecutive vertices in the above ordering. The case $r=2$ is the famous ErdősGallai theorem on the existence of paths in graphs. The case $r=3$ and $k=4$ follows from an earlier work of the authors on the conjecture of Kalai. The main result of the article is the first nontrivial upper bound valid for all $r$ and $k$. The proof is based on techniques developed for a closely related problem where a hypergraph comes with a geometric structure: the vertices are points in the plane in a strictly convex position and the sought path has to zigzag beetwen the vertices.more » « less

An \ell _p oblivious subspace embedding is a distribution over r \times n matrices \Pi such that for any fixed n \times d matrix A , \[ \Pr _{\Pi }[\textrm {for all }x, \ \Vert Ax\Vert _p \le \Vert \Pi Ax\Vert _p \le \kappa \Vert Ax\Vert _p] \ge 9/10,\] where r is the dimension of the embedding, \kappa is the distortion of the embedding, and for an n dimensional vector y , \Vert y\Vert _p = (\sum _{i=1}^n y_i^p)^{1/p} is the \ell _p norm. Another important property is the sparsity of \Pi , that is, the maximum number of nonzero entries per column, as this determines the running time of computing \Pi A . While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of 1 \le p \lt 2 , much less was known. In this article, we obtain nearly optimal tradeoffs for \ell _1 oblivious subspace embeddings, as well as new tradeoffs for 1 \lt p \lt 2 . Our main results are as follows: (1) We show for every 1 \le p \lt 2 , any oblivious subspace embedding with dimension r has distortion \[ \kappa = \Omega \left(\frac{1}{\left(\frac{1}{d}\right)^{1 / p} \log ^{2 / p}r + \left(\frac{r}{n}\right)^{1 / p  1 / 2}}\right).\] When r = {\operatorname{poly}}(d) \ll n in applications, this gives a \kappa = \Omega (d^{1/p}\log ^{2/p} d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 is optimal up to {\operatorname{poly}}(\log (d)) factors. (2) We give sparse oblivious subspace embeddings for every 1 \le p \lt 2 . Importantly, for p = 1 , we achieve r = O(d \log d) , \kappa = O(d \log d) and s = O(\log d) nonzero entries per column. The best previous construction with s \le {\operatorname{poly}}(\log d) is due to Woodruff and Zhang (COLT, 2013), giving \kappa = \Omega (d^2 {\operatorname{poly}}(\log d)) or \kappa = \Omega (d^{3/2} \sqrt {\log n} \cdot {\operatorname{poly}}(\log d)) and r \ge d \cdot {\operatorname{poly}}(\log d) ; in contrast our r = O(d \log d) and \kappa = O(d \log d) are optimal up to {\operatorname{poly}}(\log (d)) factors even for dense matrices. We also give (1) \ell _p oblivious subspace embeddings with an expected 1+\varepsilon number of nonzero entries per column for arbitrarily small \varepsilon \gt 0 , and (2) the first oblivious subspace embeddings for 1 \le p \lt 2 with O(1) distortion and dimension independent of n . Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise \ell _p lowrank approximation. Our results give improved algorithms for these applications.more » « less