{'fraction_non_alphanumeric': 0.062061081169361425, 'fraction_numerical': 0.015733028471881974, 'mean_word_length': 3.6826408360948255, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Higher minors and Van Kampen's obstruction

We generalize the notion of graph minors to all (finite) simplicial complexes. For every two simplicial complexes H and K and every nonnegative integer m, we prove that if H is a minor of K then the non vanishing of Van Kampen's obstruction in dimension m (a characteristic class indicating non embeddability in the (m-1)-sphere) for H implies its non vanishing for K. As a corollary, based on results by Van Kampen and Flores, if K has the d-skeleton of the (2d+2)-simplex as a minor, then K is not embeddable in the 2d-sphere. We answer affirmatively a problem asked by Dey et. al. concerning topology-preserving edge contractions, and conclude from it the validity of the generalized lower bound inequalities for a special class of triangulated spheres.


Introduction
The concept of graph minors has proved be to very fruitful. A famous result by Kuratowski asserts that a graph can be embedded into a 2-sphere if and only if it contains neither of the graphs K 5 and K 3,3 as minors. We wish to generalize the notion of graph minors to all (finite) simplicial complexes in a way that would produce analogous statements for embeddability of higher dimensional complexes in higher dimensional spheres. We hope that these higher minors will be of interest in future research, and indicate some results and problems to support this hope. Let K and K ′ be simplicial complexes. K → K ′ is called a deletion if K ′ is a subcomplex of K. K → K ′ is called an admissible contraction if K ′ is obtained from K by identifying two distinct vertices of K, v and u, such that v and u are not contained in any missing face of K of dimension ≤ dim(K). u ∈ T ∈ K}. An equivalent formulation of the condition for admissible contractions is that the following holds: skel dim(K)−2 (lk(v, K) ∩ lk(u, K)) = lk({v, u}, K) (1) where skel m (K) is the subcomplex of K consisting of faces of dimension ≤ m and lk(v, K) := {F ∈ K : v / ∈ F, F ∪ {v} ∈ K} is the link of v in K. For K a graph, (1) just means that {v, u} is an edge in K.
We say that a simplicial complex H is a minor of K, and denote it by H < K, if H can be obtained from K by a sequence of admissible contractions and deletions (the relation < is a partial order). Note that for graphs this is the usual notion of a minor. Remarks: (1) In equation (1), the restriction to the skeleton of dimension at most dim(K) − 2 can be replaced by restriction to the skeleton of dimension at most min{dim(lk(u, K)), dim(lk(v, K))}−1, making the condition for admissible contraction local, and weaker. All the results and proofs in this paper hold verbatim for this notion of a minor as well.
(2) In the definition of a minor, without loss of generality we may replace the local condition from the remark above by the following stronger local condition, called the Link Condition for {u, v}: lk(u, K) ∩ lk(v, K) = lk({u, v}, K). ( To see this, let K → K ′ be an admissible contraction which is obtained by identifying the vertices u and v where dim(lk(u, K)) ≤ dim(lk(v, K)). Delete from K all the faces F ⊎ {u} such that F ⊎ {u, v} is a missing face of dimension dim(lk(u, K)) + 2, to obtain a simplicial complex L. Note that {u, v} satisfies the Link Condition in L, and the identification of u with v in L results in K ′ . I thank an anonymous referee for this remark. We now relate this minor notion to Van Kampen's obstruction in cohomology; following Sarkaria [15] we will work with deleted joins and with Z 2 coefficients (background and definitions appear in the next section). For any positive integer d let H(d) be the (d−1)-skeleton of the 2d-dimensional simplex. A well known result by Van Kampen and Flores [5,20] asserts that the Van Kampen obstruction of H(d) in dimension (2d − 1) does not vanish, and hence H(d) is not embeddable in the 2(d − 1)-sphere (note that the case H(2) = K 5 is part of the easier direction of Kuratowski's theorem).
Remark: Corollary 1.2 would also follow from the following conjecture: The following theorem answers in the affirmative a question asked by Dey et. al. [3], who already proved the dimension ≤ 3 case.

Theorem 1.4 Given an edge in a triangulation of a compact PL (piecewise linear)-manifold without boundary, its contraction results in a PLhomeomorphic space if and only if it satisfies the Link Condition (2).
In Section 2 we give the needed background on Van Kampen's obstruction and Smith characteristic class. In Section 3 we prove Theorem 1.1 and show some applications. In Section 4 we prove an analogue of Theorem 1.1 for deleted products over Z. In Section 5 we prove Theorem 1.4 and deduce from it some f -vector consequences. In Section 6 we compare higher minors with graph minors.

Algebraic-topological background
The presentation here is based on work of Sarkaria [15,16] who attributes it to Wu [23] and all the way back to Van Kampen [20]. It is a Smith theoretic interpretation of Van Kampen's obstructions.
Let K be a simplicial complex. The join K * K is the simplicial complex {S 1 ⊎ T 2 : S, T ∈ K} (the superscript indicates two disjoint copies of K). The deleted join K * is the subcomplex {S 1 ⊎ T 2 : S, T ∈ K, S ∩ T = ∅}. The restriction of the involution τ : K * K −→ K * K, τ (S 1 ∪ T 2 ) = T 1 ∪ S 2 to K * is into K * . It induces a Z 2 -action on the cochain complex C * (K * ; Z 2 ). For a simplicial cochain complex C over Z 2 with a Z 2 -action τ , let C S be its subcomplex of symmetric cochains, {c ∈ C : τ (c) = c}. Restriction induces an action of τ as the identity map on C S . Note that the following sequence is exact in dimensions ≥ 0: (The only part of this statement that may be untrue for a non-free simplicial cochain complex C over Z 2 with a Z 2 -action τ , is that id + τ is surjective.) Thus, there is an induced long exact sequence in cohomology is called the m-th Smith characteristic class of K * , denoted also as Sm m (K).  [15] p.6) If a simplicial complex K embeds in R m (or in the m-sphere) then Sm m+1 (1 K * ) = 0.
Sketch of proof : The definition of Smith class makes sense for singular homology as well; the obvious map from the simplicial chain complex to the singular one induces an isomorphism between the corresponding Smith classes. The definition of deleted join makes sense for subspaces of a Euclidean space as well (see e.g. [13], 5.5); thus an embedding |K| of K into R m induces a continuous Z 2 -map from |K| * into the join of R m with itself minus the diagonal, which is Z 2 -homotopic to the antipodal m-sphere, S m . The equivariant cohomology of S m over Z 2 is isomorphic to the ordinary cohomology of RP m over Z 2 , which vanishes in dimension m + 1. We get that Sm m+1 (S m ) maps to Sm m+1 (1 |K| * ) and hence the later equals to zero as well. But |K * | and |K| * are Z 2 -homotopic, hence Sm m+1 (1 K * ) = 0.

A proof of Theorem 1.1
The idea is to define an injective chain map φ : P roof : Fix a labeling of the vertices of K, v 0 , v 1 , .., v n , such that K ′ is ob- so the sum above is nonzero. Extend linearly to obtain a map φ : First, let us check that φ is a chain map, i.e. that it commutes with the boundary maps ∂. It is enough to verify this for the basis elements F where , and as we work over Z 2 , this equals and as we work over Z 2 , this equals It suffices to show that in equations (3) and (4) the left summands on the RHSs are equal, as well as the right summands on the RHSs. This follows from observation 3.2 below. Thus φ is a chain map. Second, let us check that φ is injective. Let π K be the restriction map We proceed by induction on dim(F). As {v 0 , v 1 } ∈ K whenever dim(K) > 0 (and whenever dim(lk(v 0 , K)) ≥ 0, if we use the weaker local condition for admissible contractions), the case dim(F) ≤ 1 is clear. (If dim(K) = 0 there is nothing to prove. For the weaker local condition for admissible contractions, if lk(v 0 , K)) = ∅ then there is nothing to prove.) By the induction hypothesis we may assume that all the proper subsets of The other direction is trivial.
P roof : For two simplicial complexes L and L ′ and a field k, the following map is an isomorphism of chain complexes: where T ∈ L, T ′ ∈ L ′ and α is extended linearly. In case L = L ′ (in the definition of join we think of L and L ′ as two disjoint copies of L) and k is understood we denote α L,L ′ ,k = α L .
Thus there is an induced chain map φ * : is satisfied then we are done. (5) holds. By symmetry, (5) holds when S ∋ v 1 / ∈ T as well.
With abuse of notation (which we will repeat) we denote the above chain map by φ, φ : . It is immediate to check that α L,L ′ ,k and φ ⊗ φ commute with these Z 2 -actions, and hence so does their composition, φ. Thus, we have proved that φ : As φ commutes with the Smith connecting homomorphisms, for every m ≥ 0, φ(Sm m (1 K * )) = Sm m (1 K ′ * ). Theorem 3.4 Let H and K be simplicial complexes. If H < K then there exists an injective chain map φ : is an admissible contraction, then by Lemmas 3.1 and 3.3 it induces an injective chain map φ i : Remark: The conclusion of Theorem 1.1 would fail if we allow arbitrary identifications of vertices. For example, let K ′ = K 5 and let K be obtained from K ′ by splitting a vertex w ∈ K ′ into two new vertices u, v, and connecting u to a non-empty proper subset of skel 0 (K ′ ) \ {w}, denoted by A, and connecting v to (skel 0 (K ′ ) \ {w}) \ A. As K embeds into the 2-sphere, Sm 3 (K) = 0. By identifying u with v we obtain K ′ , but Sm 3 (K ′ ) = 0. To obtain from this example an example where the edge {u, v} is present, let L = cone(K) ∪ {u, v} (cone(K) is the cone over K), and let L ′ be the complex obtained form L by identifying u with v. Then Sm 4 (L) = 0 while Sm 4 (L ′ ) = 0. Case 2: ∂(T ) = K 1 . Hence ∂(T ) ⊆ K 2 and separates K 2 into two disks. By performing admissible contractions of pairs of vertices within each of these disks, and within K 1 , we can reduce L to the 2-skeleton of the join L 1 * L 2 where L 1 is the boundary of a triangle and L 2 is two boundaries of tetrahedra glued along a triangle. Let v be a vertex which belongs to exactly one of the two tetrahedra which were used to define L 2 . Deleting v from

The obstruction over Z
More commonly in the literature, Van Kampen's obstruction is defined via deleted products and with Z coefficients, where, except for 2-simplicial complexes, its vanishing is also sufficient for embedding of the complex in a Euclidean space of double its dimension. We obtain an analogue of Theorem 1.1 for this context.
The presentation of the background on the obstruction here is based on the ones in [14], [23] and [19].
Let K be a finite simplicial complex. Its deleted product is K × K \ {(x, x) : x ∈ K}, employed with a fixed-point free Z 2 -action τ (x, y) = (y, x). It Z 2 -deformation retracts into K × = ∪{S × T : S, T ∈ K, S ∩ T = ∅}, with which we associate a cell chain complex over Z: There is a Z 2 -action on C where the s l 's are elements of S and the t l 's are elements of T . Its importance to embeddability is given in the following classical result: [20,17,23] If a simplicial complex K embeds in R m then In relation to higher minors, the analogue of Theorem 1.1 holds: P roof of T heorem 4.2: Fix a total order on the vertices of K, v 0 < v 1 < .. < v n and consider an admissible contraction K → K ′ where K ′ is obtained from K by identifying v 0 → v 1 (shortly this will be shown to be without loss of generality). Define a map φ as follows: where sgn(v, F) = (−1) |{t∈F:t<v}| . Extend linearly to obtain an injective Z-chain map φ : The check that this map is indeed an injective Z-chain map is similar to the proof of Lemma 3.1.) In case we contract a general a → b, for the signs to work out consider the map φ = π −1 φπ rather than φ, where π is induced by a permutation on the vertices which maps π(a) = v 0 , π(b) = v 1 . Thenφ is an injective Z-chain map.
As φ(S × T ) := φ(S) × φ(T ) commutes with the Z 2 action and with the boundary map on the chain complex of the deleted product, φ induces a map H for all m ≥ 1. The checks are straightforward (for proving the last statement, choose a total order with contraction which identifies the minimal two elements v 0 → v 1 , and show equality on the level of cochains). We omit the details.
If K → K ′ is a deletion, consider the injection φ : K ′ → K to obtain again an induced map with φ * (o m Z (K × )) = o m Z (K ′ × ). Let the sequence K = K 0 → K 1 → ... → K t = H demonstrate the fact that H < K. By composing the corresponding maps as above we obtain a map φ * with φ * (o m Z (K × )) = o m Z (H × ) and the result follows. We are left to deal with the case lk(a, M) L B(b). As L is closed there exists a point t ∈ L ∩ int(B(b)) with a small punctured neighbor- B(b)). We get a Mayer-Vietoris exact sequence in reduced homology: ast(a, M)) ⊕ H d−2 N(t, B(b)).
Note that N (t, ast(a, M)) and N (t, B(b)) are homotopic to their boundaries which are (d − 1)-spheres. Note further that N (t, L) is homotopic to a proper subset X of ∂(N (t, B(b))) such that the pair (∂ (N (t, B(b))), X) is triangulated. By Alexander duality H d−1 N (t, L) = 0. Thus, (9) simplifies to the exact sequence Thus, rank(H d−1 N(t, M ′ )) ≥ 2, hence M and M ′ are not locally homologic, and in particular are not homeomorphic.
Remarks: (1) Omitting the assumption in Theorem 1.4 that the boundary is empty makes both implications incorrect. Contracting an edge to a point shows that the Link Condition is not sufficient. Contracting an edge on the boundary of a cone over an empty triangle shows that the Link Condition is not necessary.
(2) The necessity of the Link Condition holds also in the topological category (and not only in the PL category), as the proof of Theorem 1.4 shows. Indeed, for this part we only used the fact that B(b) is a pseudo manifold with boundary lk(a, M) (not that it is a ball); taking the point t to belong to exactly two facets of B(b). The following part, in the topological category, is still open: Problem 5.1 Given an edge in a triangulation of a compact manifold without boundary which satisfies the Link Condition, is it true that its contraction results in a homeomorphic space? Or at least in a space of the same homotopic or homological type?
A Mayer-Vietoris argument shows that such topological manifolds M and M ′ have the same Betti numbers; both st(a, M) and B(b) are cones and hence their reduced homology vanishes.
A candidate for a counterexample for Problem 5.1 may be the join M = T * P where T is the boundary of a triangle and P a triangulation of Poincaré homology 3-sphere, where an edge with one vertex in T and the other in P satisfies the Link Condition. By the double-suspension theorem (Edwards [4] and Cannon [1]) M is a topological 5-sphere.
Walkup [21] mentioned, without details, the necessity of the Link Condition for contractions in topological manifolds, as well as the sufficiency of the Link Condition for the 3 dimensional case (where the category of PL-manifolds coincides with the topological one); see [21], p.82-83.

PL spheres
In this section we use some terminology from f -vectors theory; readers unfamiliar with this terminology can consult [18].
Definition 5.2 Boundary complexes of simplices are strongly edge decomposable and, recursively, a triangulated PL-manifold S is strongly edge decomposable if it has an edge which satisfies the Link Condition (2) such that both its link and its contraction are strongly edge decomposable.
By Theorem 1.4 the complexes in Definition 5.2 are all triangulated PLspheres. Note that every 2-sphere is strongly edge decomposable.
Let vu be an edge in a simplicial complex K which satisfies the Link Condition, whose contraction u → v results in the simplicial complex K ′ .
We conclude the following: The g-vector of strongly edge decomposable triangulated spheres is non negative.
Is it also an M -sequence? The strongly edge decomposable spheres (strictly) include the family of triangulated spheres which can be obtained from the boundary of a simplex by repeated Stellar subdivisions (at any face); the later are polytopal, hence their g-vector is an M -sequence. For the case of subdividing only at edges (10)

Graph minors versus higher minors
While Theorem 1.1 is an instance of a property of graph minors which generalizes to higher minors, this is not always the case. Let us mention some properties which do not generalize, and others for which we do not know whether they generalize or not.
• For graphs, if K is a subdivision of H then H is a minor of K. This is not the case for higher minors.
Example 6.1 Let H be a triangulated PL 3-sphere whose triangulation contains a knotted triangle {12, 23, 13} (e.g. [11] for an example with few vertices and references to Hachimori's first examples. In [8] such spheres were proved to be non-constructible  • For a graph K on n vertices, if K has more than 3n − 6 edges then it contains a K 5 minor (Mader proved that it even contains a K 5 subdivision [12]). Is the following generalization to higher minors true?: Problem 6.2 Let C(d, n)) be the boundary complex of a cyclic dpolytope on n vertices, and let K be a simplicial complex on n vertices. Does f d (K) > f d (C(2d + 1, n)) imply H(d + 1) < K ? Example 6.3 Let M L be the vertex transitive neighborly 4-sphere on 15 vertices manifold (4, 15, 5, 1) found by Frank Lutz [10].
M L has no universal edges, i.e., every edge is contained in a missing triangle.
It is possible that K equals the 2-skeleton of M L union with a missing triangle would provide a counterexample to Problem 6.2.
• If K is the graph of a triangulated 2-sphere union with a missing edge then it contains a K 5 minor (the condition implies having more than 3n − 6 edges). Is the following generalization to higher minors true?: Problem 6.4 Let K be the union of the d-skeleton of a triangulated 2d-sphere with a missing d-face. Does H(d + 1) < K ?
It is possible that K equals the onion of the 2-skeleton of M L with a missing triangle would provide a counterexample. But if true, then by Theorems 1.1, 2.1 and 2.2, Conjecture 3.7 will follow.
• A Robertson-Seymour type theorem does not hold for embeddability in higher dimensional spheres: face of dimension < d (a facet for a pair from v 0 , .., v d or from v ′ 0 , .., v ′ d , and an edge or a triangle with the vertex t for the rest of the pairs).