On the Links of Vertices in Simplicial d-Complexes Embeddable in the Euclidean 2d-Space

Abstract

We consider d-dimensional simplicial complexes which can be PL embedded in the 2d-dimensional Euclidean space. In short, we show that in any such complex, for any three vertices, the intersection of the link-complexes of the vertices is linklessly embeddable in the $(2d-1)$-dimensional Euclidean space. In addition, we use similar considerations on links of vertices to derive a new asymptotic upper bound on the total number of d-simplices in an (continuously) embeddable complex in 2d-space with n vertices, improving known upper bounds, for all $d \ge 2$. Moreover, we show that the same asymptotic bound also applies to the size of d-complexes linklessly embeddable in the $(2d+1)$-dimensional space.

1 Introduction and Overview of Results

There is great interest in understanding properties of simplicial complexes that are embeddable in a certain Euclidean space. The basic case is 1-dimensional complexes that are embeddable in the plane, i.e., graphs that can be drawn on the plane without crossings between the edges. Planar graphs are very well-understood. For instance, it is easily shown that if a planar graph has n vertices it has at most $3n-6$ edges. However, roughly speaking, how “dense” a simplicial d-complex embeddable in $\mathbb R^{2d}$ can be, is less understood for arbitrary d. In this paper we show certain properties of embeddable complexes that, for instance, can be used to give an upper bound for this density problem. We note that any simplicial d-complex can be embedded in a simplex-wise linear way in $\mathbb R^{2d+1}$. However, for any $d \ge 1$, there exist simplicial d-complexes non-embeddable in $\mathbb R^{2d}$.

The property we prove in this article involves the notion of the link-complex of a vertex and linking of spheres in Euclidean spaces (and more generally of algebraic cycles). We begin by considering the simplest (but perhaps the hardest) case $d=2$. We consider first 2-complexes in $\mathbb R^3$. Let K be a 2-complex. The link-complex¹ of a vertex is the maximal 1-subcomplex (a graph) whose join with the vertex is a subcomplex of K (we give definitions in later sections). Sometimes the embeddability of the complex provides restrictions on possible link-graphs. The following is well known, see [5]. Assume that the complex K is sitting in $\mathbb R^3$, i.e., simplex-wise linearly embedded. Then, if we consider small enough balls around each vertex, we can observe that the intersection of the boundary of a ball with the complex K is a drawing of the link-graph of the vertex on the 2-sphere. Now a planar graph with n vertices has at most $3n-6$ edges, hence the total number of edges in all link-graphs is at most $n(3(n-1)-6) = 3n^2 -9n$. Since each triangle is counted three times it follows that such a complex K over n vertices has at most $n^2-3n$ triangles. A complex embedded in $\mathbb R^3$ and with $\Omega (n^2)$ triangles can be constructed by putting n vertices on each of two skew lines in 3-space and then taking the Delaunay triangulation of the point set; it will consist of $\Omega (n^2)$ tetrahedra. Alternatively, one can take the boundary of the 4-dimensional cyclic polytope, remove a single facet and embed the result in $\mathbb R^3$.

If we know that K embeds in $\mathbb R^4$, in general no restriction is imposed on the link-graph of a vertex. To see this, take an arbitrary graph in some $\mathbb R^3 \subset \mathbb R^4$ and “cone” this graph from a vertex on one side of the 3-plane. Hence, arbitrary graphs appear as link-complexes of embeddable 2-complexes. We can add another vertex on the other side of the 3-plane and cone again. Thus the intersection of two link-graphs can be an arbitrary graph. However, there are global restrictions on the set of all link-complexes and the above process cannot be continued. In brief, we show that in a PL embeddable 2-complex in $\mathbb R^4$, for any triple of distinct link-graphs, their common intersection (or a triple intersection) is a linklessly embeddable graph. Informally, a linklessly embeddable graph is one that can be “drawn” in space without links between disjoint circles. Figure 1 shows some examples of links in Euclidean spaces between spheres of the right dimensions.

Fig. 1

Linking of spheres in various dimensions

An interesting property of our main observation is that the same proof works for all dimensions. That is, we show that for any PL embeddable d-complex, each triple intersection of link-complexes is a linklessly embeddable $(d-1)$-complex (in $\mathbb R^{2d-1}$). More formally,

Theorem 1.1

Let $\iota :|K| \rightarrow \mathbb R^{2d}$ be a PL embedding of the d-complex K. If L is a triple intersection of link-complexes of vertices of K, then $\iota _v :|L| \rightarrow S(v)$ embeds L linklessly, for any v that contains L in its link-complex, where $\iota _v$ is the restriction to |L| of the embedding of the (underlying space of the) link-complex of v into a small sphere S(v) centered at $\iota (v)$.

The above is true even for $d=1$. In a planar graph, triple intersections of link-complexes (subsets of vertices) have at most three vertices each. This is because four points on a real-line always allow a link between two 0-dimensional spheres. Obviously, in this case the graph would contain a $K_{3,3}$ otherwise, and hence would be non-planar. Of course, this bound is not tight since we know that the triple intersections have at most two points. However, this example shows the application of the results of this article to the case $d=1$. This theorem is proved using only elementary properties of intersection homomorphism and linking numbers in $\mathbb R^{2d}$.

In the case $d=2$ a stronger fact is true. A triple intersection of links is not only linklessly embeddable but actually is a planar graph.² The proof of planarity in the case $d=2$ uses the characterization of planar graphs by forbidden minors, and so is not directly generalized to higher dimensions, see the last section for a discussion about planarity.

These observations lead us to derive a new upper bound on the number of d-simplices of embeddable d-complexes with n vertices. For a simplicial complex K, let $f_i(K)$ be the number of i-dimensional simplices of K. Denote by $f_d(n)$ the maximum number of d-simplices of a continuously³ embeddable d-complex with n vertices in $\mathbb R^{2d}$. The problem of determining or bounding $f_d(n)$ is a major open problem. For the case of (boundaries of simplicial) convex polytopes, by the famous Upper Bound Theorem, the f-vector is always bounded above by the f-vector of the cyclic polytope, see [15, 25]. This result has been strengthened to include all complexes homeomorphic to the boundary of a convex polytope, see [20]. We note that deriving asymptotic tight bounds for all these cases is much easier by using the vanishing of the Betti numbers and the Euler relation. For instance, in the case $d=2$, the Euler relation states that $\beta _0(K) - \beta _1(K)+\beta _2(K) = f_0(K) - f_1(K) + f_2(K)$ in a simplicial complex. Hence $f_2(K)$ asymptotically is dominated by $f_1(K) + \beta _2(K)$.

It is conjectured by many that the same (at least) asymptotic bounds that are true for d-simplices in the Upper Bound Theorem are also true for $f_d(n)$, this means $f_d(n) = \Theta (n^{d})$. However, the best bound in the literature is $f_d(n) = O(n^{d+1 - 1/3^d})$, and this bound was the best known for any $d>1$. This fact is proved by forbidding some non-embeddable subcomplexes. This bound is first mentioned in [4], see [9] or [6, 24] for a proof, and [4] for an application. In this paper, in Theorem 4.1, we improve this bound to $f_d(n) = O(n^{d+1 - {1}/3^{(d-1)}})$. We prove the new bound in general dimension using further non-embeddability results of Grünbaum [7]. Theorem 1.1 and its proof which is independent of the dimension give us a necessity condition for embeddability of d-complexes in 2d-space. However, Theorem 1.1, or the stronger planarity result mentioned above, help directly improve the bound on the number of simplices only for $d=2$.

We also show that the same asymptotic bound (with different constant) is true for the number of d-simplices in d-complexes that can be linklessly embedded in $\mathbb R^{2d+1}$. This is proved using the results in [19]. Note that this latter bound is strictly stronger than the former, since a complex that is embeddable in $\mathbb R^{2d}$ is linklessly embeddable in $\mathbb R^{2d+1}$ and the converse is not true. There exist also bounds on these complexes by forbidding “bad” subcomplexes, see [19, 22] for instances of small non-linklessly embeddable complexes.

It is shown in [24] that a (suitably defined) random d-complex embeddable in $\mathbb R^{2d}$ has asymptotically almost surely $f_d(K) < C f_{d-1}(K)$ for some constant C. So the conjecture is true for almost all complexes. The general belief is that the current upper bounds are far from the truth. Nevertheless, we think this paper leads to a better understanding of embeddable complexes.

It is conjectured that for 2-complexes that are embeddable in $\mathbb R^4$ one has $f_2(K)\le 4 f_1(K)$. Inequalities of this type where considered by Grünbaum [8]. This inequality is called the Grünbaum conjecture, also sometimes Kalai’s conjecture. We believe this paper is a step towards proving this conjecture.

Organization of the paper We presented an overview of the results in Sect. 1 above. In Sect. 2, we briefly explain the necessary background material and definitions. This section serves also to set up our notation. In Sect. 3 we state formally the lemma on linklessness of the triple intersection of link-complexes and prove it. Next, we prove the stronger fact for $d=2$ on planarity of the triple intersection of link-graphs. Then, in Sect. 4 we derive the bounds on the number of simplices. The argument makes use of a combinatorial lemma which is proved in Sect. 4.2.

2 Basic Concepts

In this section we recall some definitions and briefly review some preliminary facts used later in the paper. By a simplicial complex K we mean an abstract complex, i.e., a set system over a finite set of vertices satisfying the usual condition that any subset of an element of K is also in K. Let $\#\,\sigma$ denote the number of elements of the set $\sigma$. If $\sigma \in K$, its realization $|\sigma |$ is a simplex in a Euclidean space that has $\#\,\sigma$ points in general position as vertices. The dimension of $\sigma$ is the dimension of its realization, i.e., $\#\,\sigma -1$. The dimension of K is the largest of the dimensions of its simplices. A realization of K in a Euclidean space is defined as follows. For each vertex choose a point of the space with the condition that all the simplices of K are simultaneously realized, and moreover, the realizations of disjoint simplices are disjoint. The subset of the Euclidean space which is the union of realizations of simplices is a realization of K in the Euclidean space. In fact, a realization always exists, and, with the induced topology from the Euclidean spaces these realizations are homeomorphic. Hence, there is a canonical topological space defined for K which is called the underlying space of K and denoted by |K|. We write $V(K) = \{ v_1, \ldots , v_n \}$ for the set of vertices. The k-skeleton of K, i.e., the subcomplex made of simplices of dimension up to k, is denoted by $K_k$. We also assume the empty element of K has dimension $-1$.

2.1 Stars and Links

The star of a simplex $\sigma \in K$ is the set $\mathrm{st}(\sigma ) = \{ \tau \in K, \sigma \subset \tau \}$. The closed star of $\sigma$, $\mathrm{St}(\sigma )$, is the smallest subcomplex of K containing $\mathrm{st}(\sigma )$. The complex $\mathrm{St}(x) - \mathrm{st}(x)$ is called the link-complex of $\sigma$ and denoted $L(\sigma )$. The closed star is the join of $L(\sigma )$ with $\sigma$.

We work with link-complexes of vertices only. The stars of vertices cover K such that each k-simplex, $k>0$, is covered $(k+1)$-times. Also, any k-simplex appears in as many link-complexes (of vertices), as the number of its incident $(k+1)$-simplices, or its degree. It follows that the link-complexes of vertices cover all simplices of degree at least 1.

Let $f_k = f_k(K)$ denote the number of k-simplices in K, $k= -1, 0, \ldots$ A k-simplex $\sigma \in K$ is determined by giving one of its vertices v and the $(k-1)$-simplex of L(v) whose join with v is $\sigma$. Each k-simplex is determined in $k+1$ different ways. Therefore, in general, the numbers $f_k$, $k \ge 0$, satisfy

$$\begin{aligned} (k+1) f_k = \sum \limits _{i=1}^{n} f_{k-1}(L(v_i)). \end{aligned}$$

(1)

2.2 Notions of Embeddings

There exist various types of embedding into Euclidean spaces. A continuous injective map is the most general notion. And the narrowest concept for our purposes is the simplex-wise linear embedding. This is the same as realizing the complex in the required Euclidean space. A piece-wise linear (PL) embedding is one that is a simplex-wise linear embedding after finitely many (barycentric) subdivisions. Since a closed simplex is compact, a continuous map can be approximated by a PL map such that the images of two (vertex) disjoint simplices are disjoint. Such a PL map is called an almost embedding. It would be interesting to know if the linklessness condition of Theorem 1.1 can be extended to almost embeddings.

2.3 Embeddings of Link-Complexes

The concepts and notations in this paragraph are used throughout the paper and are important for us. Let K be a d-complex with a PL map $\iota :|K| \rightarrow \mathbb R^{2d}$. Put a ball of small radius $\epsilon >0$ around the point $\iota (v_i)$, denoted by $B(v_i)$, and write $S(v_i)$ for its boundary $(2d-1)$-sphere. If we choose $\epsilon$ small enough then $S(v_i) \cap \iota (|K|)$ defines an embedding of the link-complex of $v_i$ into the sphere $S(v_i)$ and hence into $\mathbb R^{2d-1}$. All the embeddings that are achieved in this way on spheres of different (small) radii are isotopic to each other. We refer to such an embedding when we say the embedding of the link-complex of $v_i$, $i=1,\ldots ,n$, and denote it by $\iota _{v_i} :|L(v_i)| \rightarrow S(v_i)$.

2.4 Chains in Spaces

We will need familiarity with the very basic notions of chain complexes. In this paragraph we merely fix notation and refer to [10, 16, 18] or any textbook on algebraic topology for complete definitions.

A singular k-dimensional simplex in a space X is a (continuous) map $\sigma :|\Delta ^k| \rightarrow X$, where $\Delta ^k$ is a standard oriented k-simplex. The kth singular chain group of X, $C_k(X)$ is a free abelian group generated by all singular simplices, where $-\sigma$ is $\sigma$ with the oppositely oriented domain simplex. The elements $c \in C_k(X)$ are called singular k-chains and they can be written as finite sums $c = \sum _i n_i \sigma _i$ where the $n_i$ are integers and the $\sigma _i$ are singular simplices. When X is the underlying space of a simplicial complex, one can in the above definition replace a singular simplex by a fixed linear homeomorphism of the standard oriented simplex onto a target simplex of the same dimension. Those homeomorphisms that preserve the orientation are declared equal and denoted by $\sigma$, and those which reverse the orientation are also declared equal and denoted by $-\sigma$, where $\sigma$ is the target simplex. The resulting chains are called simplicial chains. Hence a simplicial chain is a finite summation of oriented simplices with integer coefficients, and it can be viewed as a subset of all the singular chains closed under group operations. We also set $C(X) = \bigoplus _k C_k(X)$.

For each k, there exists a homomorphism $\partial _k :C_k(X) \rightarrow C_{k-1}(X)$ called the boundary homomorphism. We refer to basic algebraic topology textbooks for the definitions. Intuitively, in the case of simplicial chains, $\partial _k$ assigns to each generator the sum of its boundary codimension 1 simplices with proper signs. In the singular case, the boundary homomorphism assigns to a singular simplex (that is, a generator) a combination of restrictions of the singular simplex to the boundary simplices; the singular boundary is the image of the simplicial boundary of the domain. A chain is said to bound if there exists a higher dimensional chain that maps to it by $\partial _*$. A chain is a cycle if its boundary is zero. We denote the group of k-cycles by $Z_k(X)$. We say two chains $c_1$ and $c_2$ are disjoint if their images are disjoint. A map f between spaces induces homomorphisms on chain complexes which we denote by $f_\sharp$. By |c| we denote the image of the singular chain c, or its carrier. Note that, if c is a k-dimensional simplicial chain of a simplicial complex, then |c| is the union of k-simplices that have a non-zero coefficient in the unique presentation of c in the basis formed by all of the k-simplices.

2.5 Intersection Homomorphism and Linking Numbers

We make use of some elementary facts about intersection and linking numbers of chains in the Euclidean space $\mathbb R^d$ or in the sphere $S^d$. Here we present an overview on these important tools from algebraic topology. For proofs of these properties we refer to [12, 18]. In $\mathbb R^d$, for some integer $d>0$, the intersection number of two singular chains $c_p\in C_p(\mathbb R^d)$, $c_{d-p} \in C_{d-p}(\mathbb R^d)$ is an integer defined whenever $\partial c_p$ is disjoint from $c_{d-p}$, and $\partial c_{d-p}$ is disjoint from $c_p$, and moreover, the maps are “nice”, see [18]. It is enough for our purposes to restrict to pairs of singular chains that intersect finitely many times and transversely at each intersection point. Intuitively, the intersection number, $\mathcal {I}(c_p,c_{d-p})$, counts the number of transverse intersections with proper signs. We next present a more formal introduction to the intersection numbers of chains in manifolds.

Let M be an orientable closed triangulated d-manifold. Then, it is well known that there exist dual cellular subdivisions⁴ for M. Let $T_1$ and $T_2$ be cellular subdivisions dual to each other. Orient the d-dimensional cells of $T_1$ and $T_2$ coherently, that is, so that the induced orientations on each $(d-1)$-cell are opposite. Since the cellular subdivisions are dual to each other, for any k-cell of $T_1$ there exists exactly one $(d-k)$-cell of $T_2$ with non-empty intersection, for $k=0, \ldots ,d$. And that intersection is a single point and the intersection is transversal, meaning the two intersecting cells near the intersection point span a d-dimensional space. A dual cellular subdivision to any triangulation can be obtained using a barycentric subdivision of the triangulation. Then, dual to a $(d-k)$-simplex of the triangulation, is a k-cell which is the union of all k-simplices of the barycentric subdivision incident on the vertex added on the $(d-k)$-cell – and used for its subdivision – that are not inside the $(d-k)$-simplex, for $k=1, \ldots , d$. The dual of a d-simplex is the vertex of the subdivision inside it.

Assume now $\epsilon _k \sigma _k$ be an oriented k-cell of $T_1$, and, $\epsilon _{d-k} \tau _{d-k}$ be an oriented $(d-k)$-cell of $T_2$ where $\sigma$ is dual to $\tau$, and the $\epsilon _i$’s encode the respective orientations. And let $\epsilon$ encode the orientation of the manifold. That is, changing the orientation of the manifold multiplies $\epsilon$ by $-1$. Note that $\epsilon _k, \epsilon _{d-k}$, $\epsilon \in \{-1,1\}$. Then, define the intersection number as

$$\begin{aligned} \mathcal {I}(\epsilon _k \sigma _k, \epsilon _{d-k} \tau _{d-k}) = \epsilon _k\epsilon _{d-k}\epsilon . \end{aligned}$$

For non-dual pairs of oriented simplices the intersection number is defined to be zero. The intersection number then extends bilinearly to all the cellular chains of $T_1$, $T_2$.

For two singular chains which satisfy the “niceness” condition mentioned above, it is possible to approximate the two chains by chains in some two (very fine) dual cell subdivisions, and use the above intersection number definition. The standard theory, see e.g. [18], shows that the number so obtained is independent of the approximation.

The intersection number is bilinear as long as the terms on both sides are defined,

$$\begin{aligned} \mathcal {I}(c_p+c'_p,c_{d-p}) = \mathcal {I}(c_p,c_{d-p}) + \mathcal {I}(c'_p,c_{d-p}). \end{aligned}$$

Thus the intersection number defines a homomorphism $Z_p(\mathbb R^d) \times Z_{d-p}(\mathbb R^d) \rightarrow \mathbb Z$. It also passes to homology groups, that is if $c_p - c'_p = \partial d$ for a chain d then $\mathcal {I}(c_p,c_{d-p}) = \mathcal {I}(c'_p, c_{d-p})$ whenever both terms are defined. We will not need this fact though. The crucial fact we use is that in $\mathbb R^d$ any two cycles of complementary dimensions $(>0)$ have intersection number 0. Both of these claims above follow from the following general fact about the intersection numbers, which again is true when the terms are defined, that is, when $\partial c_p$ and $\partial c_{d-p+1}$ are disjoint,

$$\begin{aligned} \mathcal {I}(c_p, \partial c_{d-p+1}) = (-1)^{p} \mathcal {I}(\partial c_p, c_{d-p+1}). \end{aligned}$$

(2)

We next define the linking number of two (null-homologous) disjoint cycles $z_p,z_{d-p-1}$ in $\mathbb R^d$. Let c be such that $\partial c = z_{d-p-1}$, such a chain c always exists since the homology groups of $\mathbb R^d$ are trivial. Then

$$\begin{aligned} \mathcal {L}(z_p,z_{d-p-1}) = \mathcal {I}(z_p,c) \end{aligned}$$

is the linking number of $z_p$ and $z_{d-p-1}$. It follows from (2) that the linking number is independent of the choice of c and hence is well-defined. We also note that the linking number in general changes within a homology class.

2.6 Linklessly Embeddable Complexes

Let L be a simplicial d-complex and $\iota :|L| \rightarrow \mathbb R^{2d+1}$ an embedding, and denote by $\iota _\sharp$ the induced map on chain groups. We call the embedding $\iota :|L| \rightarrow \mathbb R^{2d+1}$ linkless ⁵, if for any two disjoint simplicial d-cycles $c_1,c_2 \in C_d(L)$ their images $\iota _\sharp (c_1), \iota _\sharp (c_2)$ have linking number zero. A simplicial d-complex is linklessly embeddable if there exists a linkless embedding of it into $\mathbb R^{2d+1}$. We remark that there exist other definitions of linklessness of embeddings, but this definition is suitable for our application.

2.7 Linklessly Embeddable Graphs

The Conway–Gordon–Sachs theorem states that the graph $K_6$ is not linklessly embeddable into $\mathbb R^3$. It follows that any graph which has a subdivision of $K_6$ as a subgraph is also not linklessly embeddable. It is an old and basic result in extremal graph theory, proved by Mader [13], that a graph without a subdivision of $K_6$ as a subgraph satisfies $m \le 4n$, where n is the number of vertices and m is the number of edges. This bound is tight and a graph with $4n + O(1)$ edges is just an apex graph, which is a planar graph together with a new vertex connected to every other vertex. On the other hand, there exists the Robertson–Saymour–Thomas characterization of linklessly embeddable graphs by forbidding the so called Petersen family of graphs as minors, [17]. Since $K_6$ is one of them, the set of linklessly embeddable graphs is contained in the set of $K_6$-minor-free graphs, and bounds for sizes of arbitrary $K_t$-minor-free graphs are also known [21]. Moreover, tight bounds on sizes of graphs that do not have a $K_t$ as topological subgraph are also known [2, 11].

3 Links in Link-Complexes

In this section we prove our main theorem on the possible link-complexes of vertices of a d-complex PL embedded into the Euclidean 2d-space. This theorem gives an obstruction for embeddability of complexes in Euclidean spaces based on the complexity of the intersections of link-complexes of vertices.

Let $c \in C(K)$ be a simplicial chain. Whenever c is defined in a link-complex L(v) (i.e., $|c| \subset |L(v)| \subset |K|$) then we have a singular chain ${\iota _v}_\sharp (c)$, which is an embedding of the carrier of c into S(v). Recall that for every vertex v, S(v) is a $(2d-1)$-sphere around v, which bounds a ball B(v) centered at v. We assume the balls are so small that the embedding inside the preimage of the ball B(v) (and of a slightly larger ball) is linear and the image inside the ball consists of a single connected component.

Lemma 3.1

Let $\iota :|K| \rightarrow \mathbb R^{2d}$ be a PL embedding of the d-complex K. Let $c_1,c_2 \in Z_{d-1}(K)$ be disjoint simplicial cycles. Give the spheres $S(v_i)$ orientations induced from that of $\mathbb R^{2d}$. Assume there is a vertex v such that $\mathcal {L}(\iota _{v\sharp }(c_1), \iota _{v\sharp }(c_2)) = \lambda \ne 0$ in S(v), then $\mathcal {L}(\iota _{w\sharp }(c_1), \iota _{w\sharp }(c_2)) = \pm \lambda$ in S(w), for any vertex w for which $\iota _{w\sharp }(c_1)$ and $\iota _{w\sharp }(c_2)$ are defined. Moreover, if one such $w \ne v$ exists then none of the chains $c_1, c_2$ can appear in a third link-complex.

Remark 3.2

Before presenting the proof we mention some points regarding it. (1) In the proof we consider simplicial chains as a special case of singular chains, that is, the simplicial chain complex is considered to be a sub-chain complex of singular chain complex. This is justified since any simplicial chain complex determines in a canonical way a singular chain complex. It is enough to observe this fact for the simplices. They are made into singular chains via the characteristic maps, see e.g. [10, Chap. 2, see also Sect. 2]. (2) For any vertex v, we regard C(S(v)) and C(B(v)) as sub-chain complexes of $C(\mathbb R^{2d})$. This is obviously justified, since the same singular chain can be considered a chain in a larger space.

Proof

We refer to Fig. 2 for a schematic overview of the notation. Let $c^u_{i} =\iota _{u\sharp }(c_{i})$, for a vertex u and $i=1,2$. By assumption, the linking number $\mathcal {L}(c^v_1, c^v_2)$ is defined and is not zero in S(v).

Fig. 2

Guide to the notation for $d=2$

Let $d^v_1,d^v_2 \in C(S(v))$ be such that $\partial d^v_1 = c^v_1$, $\partial d^v_2 = c^v_2$. Then by definition we have

$$\begin{aligned} \lambda = \mathcal {L}(c^v_1, c^v_2) = \mathcal {I}(c^v_1,d^v_2). \end{aligned}$$

Here and in the following the ambient space in which a linking or an intersection number is computed is clear from the arguments of $\mathcal {L}(\,\cdot \,,\,\cdot \,)$ and $\mathcal {I}(\,\cdot \,,\,\cdot \,)$.

Assume $c_1 = \sum _{i=1}^{m} n_i \sigma _i$, where the $\sigma _i$ are oriented simplices and the $n_i$ are non-zero integers. If the oriented d-simplex $\sigma$ is defined by $v_0 \cdots v_{d}$ then define $v \sigma$ to be the oriented $(d+1)$-simplex $v v_0 v_1 \cdots v_{d}$, i.e., the cone over $\sigma$ oriented as indicated. Let $h^v_1 \in C(\mathbb R^{2d})$ be the chain $\iota _{\sharp }(v c_1)$, where $vc_1 = \sum _{i=1}^m n_i v\sigma _i$. Let $h^v_2$ be the same for $c_2$. One easily computes that $\partial (vc_1) = \pm c_1$. The sign is not changed if the convention is that the oriented boundary simplex $p_{d-1} \ldots p_0$ is considered positively oriented with respect to the oriented simplex $p_{d}p_{d-1} \ldots p_0$, we assume it is the case. It then follows that $\partial h^v_1 = \iota _\sharp (c_1)$.

Observe that the image of the complex inside B(u) for any vertex u, is the linear cone over $S(u) \cap \iota (|K|)$ from $\iota (u)$. Consider the singular chain $d'^v_2 \in C(B(v)) \subset C(\mathbb R^{2d})$ whose image is the cone over $|c^v_2|$ from $\iota (v)$, $c^v_2 \in S(v)$, and with $\partial d'^v_2 = c^v_2$. This singular chain clearly exists and is easy to construct from $c^v_2$. Define $h'^v_2 = h^v_2-d'^v_2+d^v_2 \in C_d(\mathbb R^{2d})$. We claim that the intersection numbers satisfy

$$\begin{aligned} \mathcal {I}(h^v_1, h'^v_2) = \pm \mathcal {I}(c^v_1, d^v_2), \end{aligned}$$

(3)

where the intersection number in the right-hand side is computed in S(v). Assume there exists a vertex $w \ne v$, as in the statement of the lemma i.e. such that $c_1$ and $c_2$ appear in the link of w, with $\iota _w:|L(w)| \rightarrow S(w)$. Assuming (3) we argue as follows that $\mathcal {L}(c^w_1, c^w_2) = \pm \lambda$ in S(w). Note that this latter condition implies that $c^w_1$ and $c^w_2$ are defined.

To see this claim, we write

$$\begin{aligned} \mathcal {I}\left( h^w_1 - h^v_1, h'^w_2-h'^v_2 \right)&= \mathcal {I}\left( h^w_1, h'^w_2 \right) \nonumber \\&\quad -\, \mathcal {I}\left( h^w_1, h'^v_2 \right) - \mathcal {I}\left( h^v_1,h'^w_2 \right) + \mathcal {I}\left( h^v_1, h'^v_2 \right) . \end{aligned}$$

(4)

The two middle terms of the right-hand side are zero as follows. We have

$$\begin{aligned} \mathcal {I}\left( h^w_1, h'^v_2 \right) = \mathcal {I}\left( h^w_1, h^v_2 \right) + \mathcal {I}\left( h^w_1, - d'^v_2 + d^v_2 \right) . \end{aligned}$$

The underlying spaces of the chains $h^w_1$ and $h^v_2$ are disjoint and hence these two chains have intersection number zero. The second term is also zero since the cycle $d^v_2 - d'^v_2$ is inside the ball bounded by S(v) and is disjoint from $h^w_1$ by the choice of the spheres. The third term of the right-hand side of (4) can similarly be shown to be zero.

Since the two cycles $h^w_1 - h^v_1$ and $h'^w_2-h'^v_2$ must have intersection number 0, it follows that $\mathcal {I}(h^w_1, h'^w_2) = -\mathcal {I}(h^v_1, h'^v_2)$. And from (3) it must be that $\mathcal {I}(h^w_1, h'^w_2) = \pm \mathcal {I}(c^w_1, d^w_2)= \pm \mathcal {L}(c_1^w, c_2^w)$, and similarly, $\mathcal {I}(h^v_1, h'^v_2) = \mathcal {L}(c^v_1, c^v_2)$. Therefore, $\mathcal {L}(c^w_1, c^w_2) = \pm \lambda$.

It remains to show (3). Since by assumption the map $\iota$ restricted to $\iota ^{-1}(\hat{B}(v))$ is linear, where $\hat{B}(v)$ is a ball slightly larger than B(v), any transverse intersection between $|c^v_1|$ and $|d^v_2|$ gives rise to a transverse intersection between $|h^v_1|$ and $|d^v_2| \subset |h'^v_2|$. The rest of $|h'^v_2|$ is disjoint from $|h^v_1|$. Hence, the set of intersection points of $|h^v_1|$ and $|h'^v_2|$ is the same as the set of intersection points of $|c^v_1|$ and $|d^v_2|$ in S(v). We thus only need to argue that the intersections have the same signs in $\mathbb R^{2d}$ as in S(v), or all of the signs are changed. The sign of an intersection depends on three orientations, the two of the intersecting chains around the intersection point and the orientation of the ambient space. The chains $d^v_2$ and $h'^v_2$ have the same orientations around intersection points. The orientations of the $S(v_i)$ are induced by that of $\mathbb R^{2d}$ and hence are fixed. We thus must show that the orientations of the simplices of $h^v_1$ are determined naturally around the intersection points by those of $c^v_1$. But this is the case since the orientations of the simplices of $h^v_1$ inside the ball $\hat{B}(v)$ are defined from those of $c^v_1$ by the natural coning process sending $\iota _v(\sigma _i)$ to $\iota (v) \iota _v(\sigma _i)$.

Next we prove the last part of the lemma. From the above it follows that the 2-cycle $s_1 = h^v_1-h^w_1$ has linking number $\pm \lambda$ with $c^v_2$. Since $c^v_2 - \iota _\sharp (c_2)$ bounds a chain which is disjoint from $s_1$, it follows that $\mathcal {L}(s_1,\iota _\sharp (c_2))= \pm \lambda$. If a third vertex u exists such that $c_2$ is in its link-complex, then $\iota (uc_2)$ would be a chain disjoint from $s_1$ and bounding $c_2$. This contradicts the fact that $\lambda \ne 0$. Symmetrically the argument works for $c_1$ as well.$\square$

Theorem 1.1 is an immediate corollary of the above lemma.

Remark 3.3

We have presented our main lemma above in a setting that provides more information that is needed for Theorem 1.1. The reader will realize that, for instance, for chains with $\mathbb Z_2$ coefficients and $\mathbb Z_2$ intersection numbers, the proof simplifies.

3.1 Planarity for $d=2$

Theorem 3.4

Let K be a 2-complex embedded in $\mathbb R^{4}$. Let L be a 1-subcomplex that is the intersection of three link subcomplexes of K. Then, L is a planar graph.

This theorem can be derived easily from the following fact first proved by Grünbaum [7], see also [14, 23]. Let $K^{d_1}_{2d_1+3}, K^{d_2}_{2d_2+3}, \ldots , K^{d_p}_{2d_p+3}$ be p complexes such that $K^{d_i}_{2d_i+3}$ is the complete $d_i$-complex on $2d_i+3$ vertices, and, $d=d_1+d_2+ \cdots +d_p+p-1$. Then

$$\begin{aligned} K' = K^{d_1}_{2d_1+3} * K^{d_2}_{2d_2+3} * \cdots * K^{d_p}_{2d_p+3} \end{aligned}$$

is a d-complex not embeddable in $\mathbb R^{2d}$. The complex $K'$ is also minimal in the sense that removing a single d-simplex makes it embeddable. In order to show L planar, we must show that as a topological graph it cannot contain a topological $K_{3,3}$ or $K_5$. We have

$$\begin{aligned} K_{3,3} = [3]*[3],\qquad K_5 = K^1_{2\times 1+3}, \end{aligned}$$

where [3] is a complex consisting of three disjoint vertices. Thus, if L contains a homeomorphic copy of a $K_{3,3}$ or $K_5$ then K will contain a subcomplex homeomorphic to $[3]*[3]*[3]$ or $K^1_5 * [3]$. However, by the result mentioned above these complexes are not embeddable and the theorem is proved.

4 Bounding the Number of d-Simplices in d-Complexes in $\mathbb R^{2d}$

In this section we use the theorems which restrict the triple intersections of links of vertices to derive an upper bound on the number of d-simplices in a d-complex embeddable in $\mathbb R^{2d}$.

In the following, we consider first the cases $d=2$ and $d=3$ as examples of the general case and to introduce the intuition behind the proof. Let $d=2$. For the purpose of bounding the number of triangles, we use the fact that triple intersections of link complexes are planar. It is well known that a planar graph on n vertices has at most $f(n) = 3n-6$ edges. Thus, for any embedded 2-complex K in $\mathbb R^4$, any triple intersection of links of vertices has at most $f(n) = 3n-6$ edges. From (1) and a basic combinatorial lemma proved in the next section, Lemma 4.3, it follows that the total number of triangles satisfies $f_2 = O(n^{8/3})$.

A similar result with a slightly worse constant and only for PL embeddings can be obtained using Theorem 1.1. This is because the graph $K_6$ is not linklessly embeddable by the well known Conway–Gordon–Sachs theorem. Hence, any linklessly embeddable graph cannot contain a subdivision of $K_6$ and by the extremal results of Mader [13] it has at most $4n+O(1)$ edges.

Next let $d = 3$. From the non-embeddability result of Grünbaum it follows that a triple intersection of link-complexes cannot include a complex $F = K^1_5 * [3]$. This is because non-embeddability of $K^1_5*[3]*[3]$ (into $\mathbb R^6$) can be “read from the right” to imply that: In an embeddable complex, any triple intersection of link-complexes of vertices is such that any triple intersection of link-complexes of it does not include a homeomorphic image of $K^1_5$ as a subgraph. Thus, by the above discussion, any triple intersection of links is a 2-complex of size $O(n^{8/3})$. By Lemma 4.3 the total number of d-simplices is $O(n n^2 n^{8/9})=O(n^{3+8/9})$.

We now state the general result which is proved similarly.

Theorem 4.1

Let $f_d(n)$ be the maximum number of d simplices in an n-vertex d-complex embeddable in $\mathbb R^{2d}$, $d>0$. Then

$$\begin{aligned} f_d(n) = O\big (n^{d+1 - {1}/{3^{(d-1)}}}\big ). \end{aligned}$$

(5)

Proof

For the case $d=1$ the above reduces to $f_1(n) = O(n)$ hence the classical bound on the number of edges of a planar graph. So we assume that $d>1$. Let $\phi _d(n)$ be the maximum number of d-simplices in an n-vertex d-complex that does not have a subcomplex homeomorphic to $K_5 * [3] * \cdots * [3]$ with $d-1$ factors of [3]. By the results of Grünbaum $f_d(n) \le \phi _d(n)$ and we bound $\phi _d(n)$. For $d=2$, the condition that the complex does not contain a homeomorphic copy of $K_5 * [3]$ implies that triple intersections of link-graphs are graphs that do not contain a subdivision of $K_5$. By the early results of Mader [13] such graphs have O(n) edges. Then, from Lemma 4.3 it follows that $\phi _2(n) = O(n^{8/3})$.

Now consider the case of general d. The condition that a d-complex does not have a subcomplex homeomorphic to $K_5 * [3] * \cdots * [3]$ with $d-1$ factors of [3] implies that triple intersections of link-complexes do not contain subcomplexes homeomorphic to $K_5 * [3] * \cdots * [3]$ with $d-2$ factors of [3]. Hence, triple intersections of link complexes are $(d-1)$-complexes over at most $n-1$ vertices whose number of $(d-1)$-simplices is bounded by $\phi _{d-1}(n)$. Therefore, we can apply Lemma 4.3 again and we obtain

$$\begin{aligned} \begin{aligned} \phi _d(n)&\le c n n^{{2d}/{3}} \phi _{d-1}^{{1}/{3}}(n) \le c c' n n^{{2d}/{3}} n^{(d - {1}/{3^{d-2}})/3} \\&=cc' n^{d+1 - {1}/{3^{d-1}}}. \end{aligned} \end{aligned}$$

(6)

In the above c is a constant coming from the combinatorial lemma and $c'$ is the constant in the asymptotic bound for $\phi _{d-1}(n)$, so in general the constant in the notation depends on d. $\square$

4.1 Size of Linklessly Embeddable d-Complexes in $\mathbb R^{2d+1}$

Using the linklessness criterion of Theorem 3.1 one can prove in a way similar to the proof of Theorem 4.1, a stronger result than Theorem 4.1 for continuous embeddings. By [19, Lem. 1], if a d-complex embeds linklessly in $\mathbb R^{2d+1}$ then it cannot contain a subcomplex homeomorphic to $[3] * \cdots *[3]$, $d+1$ factors. Using an inductive argument as in the proof of Theorem 4.1, it follows that the same asymptotic bound proved above also applies to complexes that are linklessly embeddable in $\mathbb R^{2d+1}$, with slightly different constants. In the argument, $K_5$ is replaced by $[3] * [3]$. Hence, for the case $d=2$ one needs to bound the number of edges in graphs with no subdivision of $K_{3,3}$ as a subgraph and for this purpose it is enough to consider sizes of graphs with no subdivision of $K_6$ as subgraph. This is because the class of graphs with no subdivision of $K_{3,3}$ as a subgraph is contained in the class of graphs with no subdivision of $K_6$ as a subgraph.

Note that here for $d>1$ the codimension is at least three and a continuous embedding can always be approximated by a PL one [3].

Theorem 4.2

Let $g_d(n)$ be the maximum number of d-simplices of an n-vertex d-complex linklessly embeddable in $\mathbb R^{2d+1}$, $d>0$. Then

$$\begin{aligned} g_d(n) = O\big (n^{d+1 - {1}/{3^{(d-1)}}}\big ). \end{aligned}$$

(7)

4.2 A Combinatorial Lemma

This section gives the proof of a combinatorial lemma used in deriving the upper bounds. We produce it here for completeness and do not claim it is new. In this section, we denote the number of elements of a set S by |S|. Let $X = \{x_1, \ldots , x_n \}$ be a finite set and $S = \{S_1, S_2, \ldots , S_m \}$ a collection of subsets of X. We are interested in bounding the quantity $t(S) = \sum _{i=1}^{m} |S_i|$ that is a function of n and m. The restriction on sets $S_i$ comes from their common intersections. Assume that each triple of distinct sets $S_i,S_j, S_k$ satisfies

$$\begin{aligned} |S_i \cap S_j \cap S_k| \le f(n), \end{aligned}$$

where f(n) is a function of the total number of elements n.

Lemma 4.3

For the set systems satisfying the above conditions

$$\begin{aligned} t(S) = O\big (mn^{{2}/{3}} f(n)^{{1}/{3}}\big ), \end{aligned}$$

and the bound is best possible given only these conditions on the set systems.

Proof

Let $\kappa _i$ be the number of sets that the element $x_i$ belongs to. To prove the lemma, we bound the quantity $\sum _{\{i,j,k \}} |S_i \cap S_j \cap S_k|$ in two ways. First, since there are ${m\atopwithdelims ()3}$ summands with each having at most f(n) elements we have

$$\begin{aligned} \sum _{\{i,j,k \}} |S_i \cap S_j \cap S_k| \le {m \atopwithdelims ()3} f(n). \end{aligned}$$

Let the variable $Y_{lijk} = 1$ when $x_l$ is in $S_i \cap S_j \cap S_k$, $i<j<k$, and zero otherwise. Then, $\sum _{\{i,j,k \}} |S_i \cap S_j \cap S_k| = \sum _{l,i<j<k} Y_{lijk} = \sum _{l} {\sum _{i<j<k} {Y_{lijk}}}$. On the other hand, $\sum _{i<j<k} {Y_{lijk}}$ is the number of triples $(i,j,k), i<j<k,$ such that $x_l$ appears in $S_i \cap S_j \cap S_k$. This number is ${\kappa _l \atopwithdelims ()3}$. Then we have

$$\begin{aligned} \sum _l {\kappa _l \atopwithdelims ()3} = \sum _{\{i,j,k \}} |S_i \cap S_j \cap S_k|. \end{aligned}$$

(8)

By the Hölder inequality

$$\begin{aligned} \kappa _1+\kappa _2 + \cdots + \kappa _n \le \big (\kappa _1^3 + \kappa _2^3 + \cdots + \kappa _n^3 \big ) ^{{1}/{3}} n^{ {2}/{3}}. \end{aligned}$$

Writing $\kappa = (\sum \kappa _l) / n$, the above becomes $n \kappa ^3 \le \kappa _1^3 + \cdots + \kappa _n^3$.

We expand the left-hand side of (8):

$$\begin{aligned} \sum _l {\kappa _l \atopwithdelims ()3} = {\frac{1}{3!}}\biggl ( \sum _l {\kappa _l^3} -3 \sum _l \kappa _l^2 + 2 \sum _l \kappa _l\biggr ). \end{aligned}$$

From above and the fact that the $\kappa _l$ are non-negative it follows that

$$\begin{aligned} \sum _l {\kappa _l \atopwithdelims ()3} \ge \frac{1}{3!} n \kappa ^3. \end{aligned}$$

(9)

Therefore,

$$\begin{aligned} \kappa ^3 = O( m^3 n^{-1} f(n)), \end{aligned}$$

and since $n \kappa = t(S)$ we obtain

$$\begin{aligned} t(S) = O\big (m n^{{2}/{3}} f(n)^{{1}/{3}}\big ). \end{aligned}$$

If we consider the set of all those set systems for which all the $\kappa _i$ have asymptotically the same order, then the Hölder inequality is tight and it follows that for those sets $t(S) = \varTheta (m n^{2/3} f(n)^{1/3})$. Thus in general, using only the conditions in the lemma this bound cannot be improved. $\square$

We now discuss set systems that can possibly achieve the bounds of the lemma with parameters that are of interest to us, i.e., $n = f_0^2$, $m = f_0$, $f(n) = n^{1/2} = f_0$. Assume $S_1, \ldots , S_m$ are subsets such that each triple intersection (of distinct sets) $S_i \cap S_j \cap S_k$ has exactly f elements. Then, we can form another dual system as follows. Let $Y = \{ S_1, \ldots , S_m \}$ and define $T_i$ to be those sets $S_j$ that contain the element $x_i$, for $i=1, \ldots , n$. Then the sets $T_i$ satisfy the following conditions. Each 3-set of elements of Y appears in exactly f sets $T_i$. This defines a Steiner system $S_f(3,K;m)$, where K is the set containing sizes of sets $T_i$ and with n sets.

Refer to Beth et al. [1] for an extensive account of these and other combinatorial designs. Let t be a positive integer. A Steiner system $S_\lambda (t,K;v)$ is a set system $(A, \{B_1, \ldots , B_b \})$ over a set $A = \{a_1, \ldots , a_v \}$ such that, each set (or block) has size from K. Moreover, every t-subset of A appears in exactly $\lambda$ blocks.

It is clear from the above that any $S_f(3,K;m)$ with n blocks can be used to build m subsets of an n-element set such that each triple intersection of them has exactly f elements. Also, “approximate” Steiner systems are enough for our purposes, however, we are not aware of explicit descriptions of Steiner systems $S_{\lambda }(3,K; m)$ with roughly $f^2_0$ blocks such that m and $\lambda$ are also approximately $f_0$. See [1, Appendix 5] for a table of known Steiner systems.

Remark 4.4

If we are given a sequence of set systems achieving the upper bound in Lemma 4.3, then we can build as follows a simplicial complex whose triple intersections of links have at most f(n) elements each and with t(S) triangles. Let $f_0$ be the number of vertices. Take the set from the lemma with $m = f_0$, $n = f_0^2$, $f(n) = f_0$ (if such set systems exist). Then, simply make a graph over $2f_0$ vertices, so that the elements of the set X can be identified with the edges. Then, one introduces a vertex for each set $S_i$ and cones over the corresponding set of edges. The resulting complex has the required properties, i.e, the triple intersections of link-complexes have at most $f_0$ edges and the complex contains $\Theta (f_0^{8/3})$ triangles.

5 Discussion

We have shown certain restrictions on intersections of link-complexes of vertices in embeddable simplicial complexes. There is an obvious direction to continue this research and that is to find more restrictions of the type introduced here.

Let us say a simplicial complex is d-planar if it embeds in the Euclidean d-space. It is natural to strengthen the linklessness criterion to $(2d-2)$-planarity for all $d>1$. It could well be possible in addition to the case $d=2$ shown above, in dimensions $2d-2$, where the embeddability is characterized by the van Kampen obstruction, i.e., when $2d-2 \ne 4$. One shows that if a complex has van Kampen obstruction nonzero, then its join by three vertices also has nonzero van Kampen obstruction. Hence, non-embeddable complexes in Euclidean space of dimension $2d-2 \ne 4$ cannot be triple intersections of link-complexes of embeddable d-complexes in 2d-space. However, we are more interested to know if a proof exists that works for all dimensions and hence does not use the characterization of embeddable d-complexes in 2d-space, by forbidden minors or the van Kampen class.

It was shown that a triple intersection of link-complexes of vertices of a 2-complex in $\mathbb R^4$ is a planar graph. It is interesting to know if an embedding of the triple intersection graph in a plane or a 2-sphere can be obtained from the given embedding of the complex.