The Typical Algebraic Shifting of Graphs and Surfaces

In Section 2 we provide preliminaries on exterior algebraic shifting, homology lex-segments, and Delaunay triangulations; in Section 3 we prove Theorem 1.1; in Section 4 we prove Theorem 1.2; in Section 5 we prove Theorem 1.4; in Section 6 we discuss concentration for triangulations of other spaces.

The curve $\widetilde{{\gamma }_e}$ is contained in the interior of the tubular neighborhood with caps $\mathrm{int}\tilde{I}(\widetilde{{\gamma }_e})$ and consequently by setting we guarantee that the resulting set is an embedded disc. Property (1) holds by construction, and small enough $\delta$ clearly guarantees (2) as well. Since $\widetilde{{\gamma }_e}$ and $\widetilde{{\gamma }_{e^{\prime }}}$ are disjoint for every pair of distinct edges $e,e^{\prime }\in K$, then by setting $\delta \le d(\widetilde{{\gamma }_e},\widetilde{{\gamma }_{e^{\prime }}})/2$ property (3) holds. Finally, as ${\gamma }_e\cap B_v^{\prime \prime }=\mathrm{\varnothing }$ for $v\notin e$ since $B_v^{\prime \prime }\subseteq s{t}^{\circ }(v,K)$ then by setting also property (4) is satisfied. $◀$

As , every cycle on the edges of ${\mathrm{Del}}_D$ is fully contained in the disc $D$, hence so is its inner connected component disc $C$. Since $\mathrm{Del}(P)$ is a triangulation of $S$, it has a subcomplex that triangulates $C$, and its triangles are present in ${\mathrm{Del}}_D$ because they are contained in $D$. Thus, ${\mathrm{Del}}_D$ is a simply connected planar pure $2$-dimensional complex, hence a cacti, see e.g. [7], namely the union of maximal simplicial discs, every two of them are either disjoint or intersect in a single vertex, and the bipartite graph whose vertices correspond to the set $A$ of discs and the set $B$ of their intersection points and whose edges $ab$ correspond to incidences $b\in a$ for $(a,b)\in A\times B$, is a forest.

Denote by ${\mathrm{Del}}_{D,X}$ the maximal disc in the decomposition that contains $X$. It is left to show that ${\mathrm{Del}}_{D,X}$ is well defined. Indeed, for every point $x\in X$, each vertex in a triangle $A$ in $\mathrm{Del}(P)$ containing $x$ is of distance at most $2\rho$ from $x$. Since the embedding of $A$ is contained in $B(x,2\rho )$ since this last one is strongly convex. Moreover, given that the ball $B(x,2\rho )$, and consequently $A$ as well, is contained in $D$. Thus, the triangle $A$ is in ${\mathrm{Del}}_D$, and consequently there exists a unique disc component ${\mathrm{Del}}_{D,X}$ in the cacti that contains $X$. Further, as , for a vertex $v\in \mathrm{Del}(P)$ lying in $X$, all its neighbors are in $D$, hence such $v$ can not be on the boundary of ${\mathrm{Del}}_{D,X}$. $◀$

As $B\subseteq B^{\prime }$, the maximal discs ${\mathrm{Del}}_{B^{\prime \prime },B}$ and ${\mathrm{Del}}_{B^{\prime \prime },B^{\prime }}$ from Lemma 3.8 satisfy, by definition, that they are equal, and their boundary vertices lie in $B^{\prime \prime }\setminus B^{\prime }$.

Now, let $e=\{u,v\}$ be a Delaunay edge with endpoints in $B^{\prime \prime }\setminus B^{\prime }$. Then, ${\gamma }_e\cap B=\mathrm{\varnothing }$ since $d(B,\partial B^{\prime })>2\rho$ and all edges have length at most $2\rho$. $◀$

First, by Lemma 3.5 the triangulation $K$ admits a piecewise smooth embedding in $S$ that is transversal with respect to some layered vertex cover ${ℬ}_0$. In addition, let ${ℬ}_1$ be the edge cover guaranteed by Lemma 3.7. Finally, set $\rho >0$ small enough, to be specified below, that depends only on $S$, on the embedding of $K$, on the layered vertex cover ${ℬ}_0$ and on the edge cover ${ℬ}_1$.

Let and $P\subseteq S$ a $\rho$-dense finite subset locally in general position. Then, Theorem 2.8 implies that the simplicial complex $\mathrm{Del}(P)$ is a triangulation of $S$.

Call an edge in a triangulated disc diagonal if both its vertices belong to the boundary of the disc. Now, let ${\mathrm{Del}}_{B_v^{\prime \prime },B_v}$ be the disc guaranteed by Lemma 3.8, see Figure 2(1). We proceed to select a subcomplex of ${\mathrm{Del}}_{B_v^{\prime \prime },B_v}$ without diagonal edges while still containing $B_v$ in its interior. For it, let $e$ be a diagonal edge in ${\mathrm{Del}}_{B_v^{\prime \prime },B_v}$. Then $e$ splits this complex into two connected components both of which are discs. By taking , Lemma 3.9 guarantees that the embedding ${\gamma }_e$ does not intersect $B_v$. We iterate this procedure with the component having $B_v$ in its interior. The resulting triangulated disc $D$ has no diagonal edges and contains $B_v$ in its interior. In $D$ we proceed to iteratively contract edges whose both endpoints are in the interior of $D$, see Lemma 2.6. The resulting complex $D_v$ is a star with boundary $\partial D$ and we identify the apex vertex with $v$, see Figure 2(2). Let $K^{\prime }$ denote the result of applying this sequence of edge contractions to $\mathrm{Del}(P)$ for every vertex $v\in K_0$.

Next we modify the embedding of $K$ so that its edges are realized on the $1$-skeleton of $K^{\prime }$. For it, let $e=\{u,v\}\in K_1$ and ${\mathrm{Del}}_{B_e,\widetilde{{\gamma }_e}}\subseteq \mathrm{Del}(P)$ given by Lemma 3.8¹¹1The definition of ${\mathrm{Del}}_{B,X}$ applies to every connected subspace $X$ contained in the interior of a disc $B$. Indeed, as $X$ is far enough from the boundary of $B$ then an open neighborhood of $X$ is contained in $\mathrm{Del}(P)\cap B$, hence $X$ is contained in a maximal disc component – this is ${\mathrm{Del}}_{B,X}$., where we have applied the lemma to a small enough neighborhood of $\widetilde{{\gamma }_e}$. Since $\widetilde{{\gamma }_e}$ intersects $\partial D_u$ and $\partial D_v$ so does ${\mathrm{Del}}_{B_e,\widetilde{{\gamma }_e}}$. Let ${\gamma }_e^{\prime }$ be a shortest path in the graph metric contained in the $1$-skeleton of ${\mathrm{Del}}_{B_e,\widetilde{{\gamma }_e}}$ between $\partial D_u$ and $\partial D_v$ with endpoints $b_{e,u}$ and $b_{e,v}$ respectively, see Figure 3. We need to make sure that for $e=vu$ and $e^{\prime \prime }=v{u}^{\prime \prime }$ the vertices $b_{e,v}$ and $b_{e^{\prime \prime },v}$ in $D_v$ are distinct. Indeed, by taking for every two edges $e,e^{\prime \prime }$ both containing $v$ as a vertex, we guarantee that $b_{e,v}$ and $b_{e^{\prime \prime },v}$ are distinct. Finally, replace the embedding ${\gamma }_e$ by the concatenation ${\gamma }_{e,u}^{\prime }\circ {\gamma }_e^{\prime }\circ {\gamma }_{e,v}^{\prime }$ where ${\gamma }_{e,u}^{\prime }$ is the unique edge in $D_u$ from $b_{e,u}$ to $u$ and similarly ${\gamma }_{e,v}^{\prime }$ is the unique edge in $D_v$ from $b_{e,v}$ to $v$, see Figures 2(3) and 3. Since the cyclic order at every vertex of $K$ is preserved, the embedded simplicial complex coincides with $K$ (combinatorially) and it is subdivided by $|K^{\prime }|$. $◀$

We proceed by induction on the number of edges of $K^{\prime }$. We split the analysis into two cases, in each case we perform an edge contraction to reduce the number of edges and proceed by induction. If the vertex sets $K_0=K_0^{\prime }$ then the simplicial complexes coincide. Let us assume then that $K^{\prime }$ has more vertices and consequently there exists a face $A\in K$ such that its subdivision $K_A^{\prime }$ has at least one interior vertex. We split the analysis into two cases, either there exists such a triangle $A$, or else $A$ must be an edge.

If $A$ is a triangle, we let $K_A^{\prime }$ be the subdivision of a $2$-face with an interior vertex. Then, by Lemma 2.6 there exists a contractible edge incident to an interior vertex.

Suppose that there are no more $2$-faces of $K$ whose subdivision has an interior vertex. Let $K_e^{\prime }$ be the subdivision of an edge $e\in K$ with a vertex in its relative interior and let $f=\{a,b\}\in K_e^{\prime }$ an edge. If $f$ is contractible, then we contract it and proceed by induction. Otherwise, $f$ is part of a missing triangle $T=\{a,b,c\}$ in $K^{\prime }$, hence $c$ must be in $K_e^{\prime }$ as we excluded Case 1.

The boundary of $T$ is contained in the disc $D$ formed by the embedded two triangles in $K$ that contain $e$. Thus, the boundary of $T$ bounds a disc $D_T$ realized inside $|D|$ which is a subcomplex of $K^{\prime }$ with an interior vertex; all vertices of $D_T$ belong to $K_e^{\prime }$. As $K_e^{\prime }$ has finitely many vertices, proceeding in this manner for an edge $f^{\prime }$ in $K_e^{\prime }\cap D_T$ and so on, we finally find a contractible edge in $K_e^{\prime }$, similar to the proof of Lemma 2.6. $◀$

For the first part we proceed by induction on $n$. Denote by $E_n$ the event that $P_n$ is locally in g.p. Observe that $\mathbb{P}(E_n)=\mathbb{P}(E_n|E_{n-1})\mathbb{P}(E_{n-1})$ and that $\mathbb{P}(E_{n-1})=1$ by induction. Conditioned on $E_{n-1}$, the probability of $E_n$ is given by the probability of picking a point that is not in the union of the sets determined by the complements of the conditions $(1)$ and $(2)$ in the definition of g.p. above. Since these complements have $\nu$-measure $0$ in $S$ and there are finitely many of them, the conclusion follows.

For the second part let $\{B(x,\rho /2):x\in I\}$ be a finite open cover of $S$, which exists since $S$ is compact. Then, it is enough to guarantee that $P_n\cap B(x,\rho /2)\ne \mathrm{\varnothing }$ for every $x\in I$. Indeed, if this is true, then for every $y\in S$ there exists $x\in I$ such that $y\in B(x,\rho /2)$ and $p\in P\cap B(x,\rho /2)$. Then, as claimed. It follows that

where $\mu ={\min }_{x\in I}\nu (B(x,\rho /2))/\nu (S)>0$. The conclusion now follows by taking $n\to \mathrm{\infty }$. $◀$

Let $K$ be a triangulation of $S$ given by Corollary 2.3 and set $\rho >0$ as required by Theorem 1.1 when applied to $K$ and $S$. By Lemma 4.1 $P_n$ is a.a.s. $\rho$–dense and is locally in general position. Then, Theorem 1.1 guarantees that $\mathrm{Del}(P_n)$ admits a sequence of edge contractions reaching $K$. Since ${\mathrm{\Delta }}^{ex}(K)$ is a homology lex-segment then Corollary 2.5 implies that ${\mathrm{\Delta }}^{ex}(\mathrm{Del}(P_n))$ is a homology lex-segment as well. $◀$

Let $X$ be a compact one dimensional topological space. It admits natural triangulations each given by some graph $G$. Let $\mathrm{sd}(G)$ denote the barycentric subdivision of $G$, namely the one obtained by introducing a new vertex at the interior of each edge of $G$, subdividing that edge into two edges. The following proposition holds for exterior algebraic shifting over any field:

First, we claim that $\mathrm{Tail}({\mathrm{\Delta }}^{ex}(\mathrm{sd}G),\{3,4\})=\mathrm{\varnothing }$. Otherwise there exists a connected subgraph $H$ of $\mathrm{sd}G$ that is a $2$-hypercycle and consequently is $3$-edge connected, see [17, Theorem 5.4]. However, this is not possible for if $e=\{u,v\}\in H$ and we assume without loss of generality that $u\in V(\mathrm{sd}G)\setminus V(G)$ then the degree of $u$ in $H$ is at most $2$. Since algebraic shifting outputs a shifted simplicial complex with identical Betti numbers we conclude that ${\mathrm{\Delta }}^{ex}(\mathrm{sd}G)=[n]\bigcup \{A\in \left(\genfrac{}{}{0pt}{}{[n-{\beta }_0]}{2}\right):A\le \{2,{\beta }_1+2\}\}$ as wanted. $◀$

First, by Propositions 5.1 and 2.4 with $m=2$, the event that ${\mathrm{\Delta }}^{ex}(U_n(|G|))=\mathrm{\Delta }(|G|,n)$ contains the event $E$ that every edge of $G$ is subdivided. In addition, since the order in which we subdivide an edge is not important the model $U_n(|G|)$ can be viewed as a balls and bins model where the bins represent the edges of $G$ and the balls represent the new vertices. Therefore, the probability that $E$ does not occur is at most $|E|{(1-1/|E|)}^n$ which tends to $0$ as $n\to \mathrm{\infty }.$ $◀$

We show here that unlike the one-dimensional case, the uniform triangulation of the $2$-disc and of the disjoint union of two $2$-discs do not have a concentrated exterior algebraic shifting.

Since $K$ is part of a triangulation of a sphere, then $\{1,4,5\}\notin {\mathrm{\Delta }}^{ex}(K)$. Moreover, since the homology of $K$ is trivial, then there is no $2$-face whose smallest vertex is strictly larger than $1$. Since the $1$-skeleton of $K$ is $2$-hyperconnected, see [17], then $\{2,n+m\}\in {\mathrm{\Delta }}^{ex}(K)$. Combining this with the fact that $K$ is Cohen–Macaulay, even shellable, its algebraic shifting is pure implying that $\{1,2,m+n\}\in {\mathrm{\Delta }}^{ex}(K)$ and $\{4,5\}\notin {\mathrm{\Delta }}^{ex}(K)$ . Thus, the remaining edges must be of the form $\{3,k\}$, and the remaining triangles of the form $\{1,3,k\}$, forming initial lex-segments of edges and of triangles by the shiftedness of ${\mathrm{\Delta }}^{ex}(K)$. The claim now follows from the fact that algebraic shifting preserves the $f$-vector. $◀$

By well-known estimates [27, 14] for the number of $n$-vertex triangulations of the disc with $m$ boundary vertices, it can be derived that for every fixed $m\ge 3$ there exists ${\epsilon }_m>0$ such that $\mathbb{P}(U_n(X)\text{ has }m\text{ boundary vertices})={\epsilon }_m+o(1)$ as $n\to \mathrm{\infty }$. In consequence, the probability that the $2$-faces satisfy ${\mathrm{\Delta }}^{ex}(U_n(X))=\{A\in \left(\genfrac{}{}{0pt}{}{[n+m]}{3}\right):A\le \{1,3,3+n\}\}$, for every fixed $m$, is bounded away from $0$ as $n$ grows. $◀$

The proof follows by applying Proposition 5.2 and [24, Theorem 4.6] for exterior shifting of a disjoint union of simplicial complexes. $◀$

Let $K_1,K_2$ and $n$ and $m$ as in Lemma 5.4, then we have that $\{2,n+m-1\}\notin {\mathrm{\Delta }}^{ex}(K_1\bigsqcup K_2)$ while $\{1,n+m-1\},\{3,n-3\}\in {\mathrm{\Delta }}^{ex}(K_1\bigsqcup K_2)$, showcasing that the complex is not an homology lex-segment. The lack of concentration follows from Corollary 5.3. $◀$

Let $K$ triangulate $S_g$ and denote $m=f_0(\mathrm{sd}(K))$. The $1$-skeleton of $\mathrm{sd}(K)$ is $3$-hyperconnected, see e.g. [25, Thm.3.4.2], and similarly over every field, hence $\{3,m\}\in {\mathrm{\Delta }}^{ex}{(\mathrm{sd}(K))}_1$. To see that $\{5,6\}\notin {\mathrm{\Delta }}^{ex}{(\mathrm{sd}(K))}_1$, it is enough to remove from $\mathrm{sd}(K)$ vertices of degree at most $4$ one by one until we reach a collection of isolated vertices; see Kalai [17, Lem.4.3(i)] for shifting over a field of characteristic zero, and the same proof holds over every field. First we remove vertices at the barycenter of edges of $K$ (their degree is $4$), then we remove vertices at the barycenter of triangles of $K$ (their degree at this stage is $3$), to reach the original vertices of $K$, and no higher dimensional faces. As ${\mathrm{\Delta }}^{ex}(\mathrm{sd}(K))$ is shifted and has the same number of edges as $\mathrm{sd}(K)$, we conclude that . Assuming Conjecture 6.3, $\{1,3,m\}\in {\mathrm{\Delta }}^{ex}{(\mathrm{sd}(K))}_2$, and as ${\mathrm{\Delta }}^{ex}(\mathrm{sd}(K))$ is a shifted simplicial complex, not containing the edge $\{5,6\}$ with the same face and Betti numbers as $\mathrm{sd}(K)$ we conclude that . $◀$