## Extremal Hypercuts and Shadows of Simplicial Complexes

Nati Linial ∗

Ilan Newman †

Yuval Peled ‡

Yuri Rabinovich §

November 13, 2015

## Abstract

Let F be an n -vertex forest. We say that an edge e / F ∈ is in the shadow of F if F ∪{ } e contains a cycle. It is easy to see that if F is 'almost a tree', that is, it has n -2 edges, then at least glyph[floorleft] n 2 4 glyph[floorright] edges are in its shadow and this is tight. Equivalently, the largest number of edges an n -vertex cut can have is glyph[floorleft] n 2 4 glyph[floorright] . These notions have natural analogs in higher d -dimensional simplicial complexes, graphs being the case d = 1 . The results in dimension d &gt; 1 turn out to be remarkably different from the case in graphs. In particular the corresponding bounds depend on the underlying field of coefficients. We find the (tight) analogous theorems for d = 2 . We construct 2 -dimensional ' Q -almost-hypertrees' (defined below) with an empty shadow. We also show that the shadow of an ' F 2 -almost-hypertree' cannot be empty, and its least possible density is Θ( 1 n ) . In addition we construct very large hyperforests with a shadow that is empty over every field.

For d ≥ 4 even, we construct d -dimensional F 2 -almost-hypertree whose shadow has density o n (1) . Finally, we mention several intriguing open questions.

## 1 Introduction

This article is part of an ongoing research effort to bridge between graph theory and topology (see, e.g. [9, 12, 6, 11, 2, 5, 8, 13]). This research program starts from the observation that a graph can be viewed as a 1 -dimensional simplicial complex, and that many basic concepts of graph theory such as connectivity, forests, cuts, cycles, etc., have natural counterparts in the realm of higher-dimensional simplicial complexes. As may be expected, higher dimensional objects tend to be more complicated than their 1 -dimensional counterparts, and many fascinating phenomena reveal themselves from the present vantage point. This paper is dedicated to the study of several extremal problems in this domain. We start by introducing some of the necessary basic notions and definitions.

## Simplices, Complexes, and the Boundary Operator:

All simplicial complexes considered here have [ n ] = { 1 , . . . , n } or Z n as their vertex set V . A simplicial complex X is a collection of subsets of V that is closed under taking subsets. Namely, if A ∈ X and B ⊆ A , then B ∈ X as well. Members of X are called faces or simplices . The dimension of the simplex A ∈ X is defined as | A | -1 . A d -dimensional simplex is also called a d -simplex or a d -face for short. The dimension dim( X )

∗ School of Computer Science and engineering, The Hebrew University of Jerusalem, Jerusalem, Israel. Email: nati@cs.huji.ac.il . Research supported by an ERC grant 'High-dimensional combinatorics'.

† Department of Computer Science, University of Haifa, Haifa, Israel. Email: ilan@cs.haifa.ac.il . This Research was supported by The Israel Science Foundation (grant number 862/10.)

‡ School of Computer Science and engineering, The Hebrew University of Jerusalem, Jerusalem, Israel. Email: yuvalp@cs.huji.ac.il . Yuval Peled is grateful to the Azrieli Foundation for the award of an Azrieli Fellowship.

§ Department of Computer Science, University of Haifa, Haifa, Israel. Email: yuri@cs.haifa.ac.il . This Research was supported by The Israel Science Foundation (grant number 862/10.)

is defined as maxdim( A ) over all faces A ∈ X , and we also refer to a d -dimensional simplicial complex as a d -complex. The size | X | of a d -complex X is the number d -faces in X . The complete d -dimensional complex K d n = { σ ⊂ [ n ] | | σ | ≤ d +1 } contains all simplices of dimension ≤ d . If X is a d -complex and t &lt; d , the collection of all faces of dimension ≤ t in X is a simplicial complex that we call the t -skeleton of X . If this t -skeleton coincides with K t n we say that X has a full t -dimensional skeleton. If X has a full ( d -1) -dimensional skeleton (as we usually assume), then its complement ¯ X is defined by taking a full ( d -1) -dimensional skeleton and those d -faces that are not in X .

The permutations on the vertices of a face σ are split in two orientations of σ , according to the permutation's sign. The boundary operator ∂ = ∂ d maps an oriented d -simplex σ = ( v , ..., v 0 d ) to the formal sum ∑ d i =0 ( -1) ( i σ \ v i ) , where σ \ v i = ( v , ...v 0 i -1 , v i +1 , ..., v d ) is an oriented ( d -1) -simplex. We fix some field F and linearly extend the boundary operator to free F -sums of simplices. We consider the ( n d ) × ( n d +1 ) matrix form of ∂ d by choosing arbitrary orientations for ( d -1) -simplices and d -simplices in K d n . Note that changing the orientation of a d -simplex (resp. d -1 -simplex) results in multiplying the corresponding column (resp. row) by -1 . Thus the d -boundary of a weighted sum of d simplices, viewed as a vector z (of weights) of dimension ( n d +1 ) is just the matrix-vector product ∂ z d . We denote by M X the submatrix of ∂ d restricted to the columns associated with d -faces of a d -complex X .

The specific underlying fields that we consider in this paper are Q or F 2 . (In the latter case orientation is redundant). It is very interesting to extend the discussion to the case where everything is done over a commutative ring, and especially over Z , but we do not do this here. We associate each column in the matrix form of ∂ d with the corresponding d -simplex σ . This is an ( n d ) -dimensional vector of 0 , ± 1 whose support corresponds to the boundary of σ . It is standard and not hard to see that for every choice of ground field, the matrix ∂ d has rank ( n -1 d ) . A fundamental (easy) fact is that ∂ d -1 · ∂ d = 0 for any d .

## Rank Function and other notions:

If S is a collection of n -vertex d -simplices, then we define 1 its rank as the F -rank of the set of the corresponding columns of ∂ d . (It clearly does not depend on the choice of orientations). The set of all d -faces of K d n has rank ( n -1 d ) , with basis being, e.g., the collection of all d -simplices that contain the vertex 1 .

If rank( S ) = | S | , we say that S is acyclic over F . A maximal acyclic set of d -faces is called a d -hypertree , and an acyclic set of size ( n -1 d ) -1 is called an almost-hypertree . Hypertrees over Q were studied e.g., by Kalai [9] and others [1, 7] in the search for high-dimensional analogs of Cayley's formula for the number of labeled trees. A d -dimensional hypercut (or d -hypercut in short) is an inclusion-minimal set of d -faces that intersects every hypertree. It is a standard fact in matroid theory that for every hypercut C , there is a hypertree T such that | C ∩ T | = 1 .

glyph[negationslash]

The shadow SH S ( ) of a set S of d -simplices consists of all d -simplices σ ∈ S which are in the F -linear span of S , i.e., such that rank( S ∪ σ ) = rank( S ) . A set of d -faces is a hypercut iff its complement is the union of an almost-hypertree and its shadow. If SH S ( ) = ∅ , we say that S is closed or shadowless . For instance, a set of edges in a graph is closed if it is a disjoint union of cliques.

We turn to define d -collapsibility . A ( d -1) -face τ in a d -complex K is called exposed if it is contained in exactly one d -face σ of K . An elementary d -collapse on τ consists of the removal of τ and σ from K . We say that K is d -collapsible if it is possible to eliminate all the d -faces of K by a series of elementary d -collapses. It is an easy observation that the set of d -faces in a d -collapsible d -complex is acyclic over every field.

We refer the reader to Section 2 for some more background material.

1 In the language of simplicial homology, consider the d -complex K S ( ) whose set of d -faces is S . Then, rank( S ) is just the dimension of B d -1 , the linear space of ( d -1) -boundaries of K S ( ) , and | S | -rank( S ) is the dimension of the homology group H d ( K S ( )) .

## Results:

In this paper we study extremal problems concerning the possible sizes of hypercuts and shadows in simplicial complexes.

We begin with some trivial observations on n -vertex graphs, starting with the (non-tight) claim that no cut can have more than ( n 2 ) -n +2 edges. This follows, since for every cut there is a tree that meets it in exactly one edge. Actually the largest number of edges of a cut is glyph[floorleft] n 2 4 glyph[floorright] . We investigate here the 2 -dimensional situation and discover that it is completely different from the graphical case. When we discuss 2 -complexes, we refer to 2 -faces as faces (and keep the terms vertex and edge for 0 and 1 dimensional faces).

A 2 -dimensional hypertree has ( n -1 2 ) faces. So, by the same reasoning, every hypercut has at most ( n 3 ) -(( n -1 2 ) -1 ) faces. A hypercut of this size (if one exists) is called perfect . We show that Q -perfect hypercuts exist for certain integers n , and if a well-known conjecture by Artin 2 in number theory is true, there are infinitely many such n . The construction is based on the 2 -complex of length3 arithmetic progressions in Z n , and is of an independent interest.

Over the field F 2 , surprisingly, the situation changes. There are no perfect hypercuts for n &gt; 6 , and the largest possible hypercut has ( n 3 ) -3 4 n 2 -Θ( n ) faces. We completely describe all the extremal hypercuts.

Staying with F = F 2 and with d &gt; 2 the situation depends on the parity of d . As we show, for d even the largest d -hypercuts have ( n d +1 ) · (1 -o n (1)) d -faces. When d is odd, all d -hypercuts have density that is bounded away from 1.

Equivalently, this subject can be viewed from the perspective of shadows of acyclic complexes. Thus the complement of a perfect 2 -hypercut over Q is an almost-hypertree (i.e. acylic complex with ( n -1 2 ) -1 2 -faces) with an empty shadow. Our results over F 2 can be restated as saying that the least possible size of the shadow of a 2 -dimensional F 2 -almost-hypertree is n 2 4 +Θ( ) n .

Many questions suggest themselves: Let X be an F -acyclic d -dimensional n -vertex simplicial complex with a full skeleton and a given size. What is the smallest possible shadow of such X ? More specifically, what is the largest possible size of X if it is shadowless?

One construction that we present here applies to all fields at once, since it is based on the combinatorial notion of collapsibility. This is a collapsible 2 -complex with f = ( n -1 2 ) -( n + 1) 2 -faces which remains collapsible after the addition of any other 2 -face. This yields, for every field F , a shadowless F -acyclic 2 -complex with f 2 -faces

We note that Bj¨ orner and Kalai's work [3] determines the largest possible shadow of an acyclic d -complex with f faces. The extremal examples are maximal acyclic subcomplexes of a shifted complex with f faces.

The rest of the paper is organized as following. In Section 2 we introduce some additional notions in the combinatorics of simplicial complexes. Section 3 deals with the problem of largest 2 -hypercuts over Q . In Section 4 we study the same problem over F 2 . In Section 5 we construct large d -hypercuts over F 2 for even d ≥ 4 . In Section 6 we deal with large acyclic shadowless 2 -dimensional sets. Lastly, in Section 7 we present some of the many open questions in this area.

## 2 Additional Notions and Facts from Simplicial Combinatorics

Recall that we view the d -boundary operator as a linear map over F , that maps vectors supported on oriented d -simplices to vectors supported on ( d -1) -simplices, given explicitly by the matrix ∂ d , as defined in the Introduction.

The right kernel of ∂ d is the linear space of d -cycles . The left image of ∂ d is the linear space B d ( X ) of d -coboundaries of X . With some abuse of notation we occasionally call a set of d -simplices a cycle or a coboundary if it is the support of a cycle or a coboundary. Clearly over F 2 , this makes no difference. In this case each d -coboundary is associated with a set A of ( d -1) -faces, and consists of those d -faces whose boundary has an odd intersection with A .

2 There is strong evidence for this conjecture. In particular it follows from the generalized Riemann Hypothesis.

A d -coboundary is called simple if its support does not properly contain the support of any other non-empty d -coboundary. As observed e.g., in [15], a coboundary is simple if and only if its support is a hypercut.

If σ is a face in a complex X , we define its link via link σ ( X ) = { τ ∈ X : τ ∩ σ = ∅ , τ ∪ σ ∈ X } . This is clearly a simplicial complex. For instance, the link of a vertex v in a graph G is v 's neighbour set which we also denote by N G ( v ) or N v ( ) . For a 2 -coboundary C over F 2 and a vertex v ∈ [ n ] , it is easy to see that the graph link v ( C ) generates C , i.e. C = link ( v C ) · ∂ 2 . Namely, the characteristic vector of the 2 -faces of C equals to the vector-matrix left product of the characteristic vector of the edges of link v ( C ) with the boundary matrix ∂ 2 . We recall a necessary and sufficient condition that G = link v ( C ) generates a 2 -hypercut C rather than a general coboundary.

Two incident edges uv uw , in a graph G = ( V, E ) are said to be Λ -adjacent if vw / E ∈ . We say that G is Λ -connected if the transitive closure of the Λ -adjacency relation has exactly one class.

Proposition 2.1. [15] A 2 -dimensional coboundary B is a hypercut if and only if the graph link v ( B ) is Λ -connected for every v .

## 3 Shadowless Almost-Hypertrees Over Q

The main result of this section is a construction of 2 -dimensional shadowless Q -almost-hypertrees. As mentioned above, the complement of such a complex is a perfect hypercut having ( n 3 ) -( n -1 2 ) +1 faces which is the most possible.

Theorem 3.1. Let n ≥ 5 be a prime for which Z ∗ n is generated by {-1 2 , } . Let X = X n be a 2-dimensional simplicial complex on vertex set Z n whose 2 -faces are arithmetic progressions of length 3 in Z n with difference not in { 0 , ± } 1 . Then,

- · X n is 2 -collapsible, and hence it is an almost-hypertree over every field.
- · SH X ( n ) = ∅ over Q . Consequently, the complement of X n is a perfect hypercut over Q .

The entire construction and much of the discussion of X n is carried out over Z n . However, in the following discussion, the boundary operator M X of X n is considered over the rationals.

We start with two simple observations. First, note that X n has a full 1 -skeleton, i.e., every edge is contained in some 2 -face of X .

↦

Also, we note that the choice of omitting the arithmetic triples with difference ± 1 is completely arbitrary. For every a ∈ Z ∗ n , the automorphism r → ar of Z n maps X n to a combinatorially isomorphic complex of arithmetic triples over Z n , with omitted difference ± a . Consequently, Theorem 3.1 holds equivalently for any difference that we omit. In what follows we indeed assume for convenience that the missing difference is not ± 1 , but rather ± 2 -1 ∈ Z n .

For d ∈ Z ∗ n , define E d = E d,n = ((0 , d ) , (1 , d +1) , . . . , ( n -1 , d + n -1) ) , where all additions are mod n . This is an ordered subset of directed edges in X n .

Similarly, we consider the collection of arithmetic triples of difference d ,

$$F _ { d } \, = \, F _ { d, n } \, = \, \left ( \, ( 0, d, 2 d ), ( 1, d + 1, 2 d + 1 ), \dots, ( n - 1, d + n - 1, 2 d + n - 1 ) \, \right ).$$

Clearly every directed edge appears in exactly one E d and then its reversal is in E -d . Likewise for arithmetic triples and the F d 's. Since we assume that Z ∗ n is generated by {-1 2 , } , it follows that the powers { 2 i } ⊂ Z ∗ n , i = 0 , . . . , n -1 2 -1 , are all distinct, and, moreover, no power is an additive inverse of the other. Therefore, the sets { E 2 i } , i = 0 , . . . , n -1 2 -1 , constitute a partition of the 1 -faces of X n . Similarly, the sets { F 2 j } , j = 0 , . . . , n -1 2 -2 , constitute a partition of the 2 -faces of X n . The omitted difference is 2 n -1 2 -1 ∈ {± 2 -1 } , as assumed (the sign is determined according to whether 2 n -1 2 = 1 or -1 ).

Lemma 3.2. Ordering the rows of the adjacency matrix M X by E 2 i 's, and ordering the columns by the F 2 i 's, the matrix M X takes the following form:

$$M _ { X } \, = \, \begin{pmatrix} I + Q & 0 & 0 & \dots \\ - I & I + Q ^ { 2 } & 0 & \dots \\ 0 & - I & \ddots & \dots \\ 0 & 0 & \ddots & I + Q ^ { 2 ^ { \frac { n - 1 } { 2 } - 2 } } \\ 0 & 0 & \dots & - I \end{pmatrix} \quad \quad \, ( 1 )$$

↦

where each entry is an n × n matrix (block) indexed by Z n , and Q is a permutation matrix corresponding to the linear map b → b +1 in Z n .

Proof. Consider an oriented face σ ∈ F 2 i ⊂ X n . Then, σ = ( b, b + 2 i , b + 2 i +1 ) for some b ∈ Z n and 0 ≤ i ≤ n -1 2 -2 , i.e., σ is the b -th element in F 2 i . By definition, ∂σ = ( b, b +2 )+( +2 i b i , b +2 i +1 ) -( b, b +2 i +1 ) . The first two terms in ∂σ are the b -th and ( b +2 ) i -th elements in E 2 i respectively; the third term corresponds to the b -th element in E 2 i +1 . Thus, the blocks indexed by E 2 i × F 2 i are of the form I + Q 2 i , the blocks E 2 i +1 × E 2 i are -I , and the rest is 0.

We may now establish the main result of this section.

Proof. (of Theorem 3.1) We start with the first statement of the theorem. Let m = n -1 2 .

Lemma 3.2 implies that the edges in E 2 m -1 are exposed. Collapsing on these edges leads to elimination of E 2 m -1 and the faces in F 2 m -2 . In terms of the matrix M X , this corresponds to removing the rightmost 'supercolumn'. Now the edges in E 2 m -2 become exposed, and collapsing them leads to elimination of E 2 m -2 , and F 2 m -3 . This results in exposure of E 2 m -3 , etc. Repeating the argument to the end, all the faces of X n get eliminated, as claimed.

To show that X n is an almost-hypertree we need to show that the number of its 2 -faces is ( n -1 2 ) -1 . Indeed,

$$| X _ { n } | \ = \ \sum _ { j = 0 } ^ { \frac { n - 1 } { 2 } - 2 } | F _ { 2 ^ { j } } | \ = \ \left ( \frac { n - 1 } { 2 } - 1 \right ) \cdot n \ = \ \binom { n - 1 } { 2 } - 1 \.$$

We turn to show the second statement of the theorem, i.e., that SH X ( n ) = ∅ . Let u ∈ Q ( n 2 ) , be a vector indexed by the edges of X n , where u e = 2 i when e ∈ E 2 i . Here we think of 2 i as an integer (and not an element in Z n ). We claim that for every σ ∈ K 2 n ,

$$\langle u, \partial \sigma \rangle \, = \, 0 \ \Longleftrightarrow \ \sigma \in X _ { n } \,.$$

Indeed, for every face σ ∈ K (2) n , exactly three coordinates in the vector ∂σ are non-zero, and they are ± 1 . Since the entries of u are successive powers of 2 , the condition 〈 u, ∂σ 〉 = 0 holds iff ∂σ (or -∂σ ) has two 1 's in E 2 i and one -1 in E 2 i +1 for some 0 ≤ i ≤ n -1 2 -1 . This happens if and only if σ is of the form ( b, b +2 i , b +2 i +1 ) , i.e., precisely when σ ∈ X n .

This implies that X n is closed, i.e. SH X ( n ) = ∅ , since any 2-face σ ∈ K (2) n spanned by X n must satisfy 〈 u, ∂σ 〉 = 0 , this being precisely the characterisation of X n . Thus, X n is a closed set of co-rank 1. Therefore, its complement is a hypercut. Moreover, since X n is almost-hypertree, this hypercut is perfect.

When the prime n does not satify the assumption of Theorem 3.1 we can still say something about the structure of X n . Let the group G n = Z ∗ n / {± } 1 , and let H n be the subgroup of G n generated by 2 . Then,

Theorem 3.3. For every prime number n , rank Q ( X n ) = | X n | -( n -1) · ([ G n : H n ] -1) . In particular, X n is acyclic if and only if Z ∗ n is generated by {± 1 2 , } .

We only sketch the proof. We saw that the partition of X n 's edges and faces to the sets E i and F i . We consider also a coarser partition by joining together all the E i 's and F i 's for which i belongs to some coset of H n . This induces a block structure on M X with [ G n : H n ] blocks. An argument as in the proof of Lemma 3.2 yields the structure of these blocks. Finally, an easy computation shows that one of these blocks is 2 -collapsible, and each of the others contribute precisley n -1 vectors to the right kernel.

We conclude this section by recalling the following well-known conjecture of Artin which is implied by the generalized Riemann hypothesis [14].

Conjecture 3.4 (Artin's Primitive Root Conjecture) . Every integer other than -1 that is not a perfect square is a primitive root modulo infinitely many primes.

This conjecture clearly yields infinitely many primes n for which Z ∗ n is generated by 2 . (It is even conjectured that the set of such primes has positive density). Clearly this implies that the assumptions of Theorem 3.1 hold for infinitely many primes n .

## 4 Largest Hypercuts over F 2

In this section we turn to discuss our main questions over the field F 2 . The main result of this section is:

Theorem 4.1. For large enough n , the largest size of a 2 -dimensional hypercut over F 2 is ( n 3 ) -( 3 4 n 2 -7 2 n +4 ) for even n and ( n 3 ) -( 3 4 n 2 -4 n + 25 4 ) for odd n .

Remark 4.2. The proof provides as well a characterization of all the extremal cases of this theorem.

Since no confusion is possible, in this section we use the shorthand term cut for a 2 -dimensional hypercut. The first step in proving Theorem 4.1 is the slightly weaker Theorem 4.3. A further refinement yields the tight upper bound on the size of cuts.

Note that since ( [ n ] 3 ) is a coboundary, the complement ¯ = C ( [ n ] 3 ) \ C of any cut C is a coboundary. Moreover, the complement of the ( n -1) -vertex graph, link v ( C ) , is a link of ¯ C . In what follows, link v ( C ) is always considered as an ( n -1) -vertex graph with vertex set [ n ] \ { v } . Occasionally, we will consider the graph link v ( C ) ∪ { v } which has v as an isolated vertex.

Theorem 4.3. The size of every n -vertex cut is at most ( n 3 ) -3 4 · n 2 + ( o n 2 ) . In every cut C that attains this bound there is a vertex v for which the graph G = link v ( C ) satisfies either

- 1. ¯ G has one vertex of degree n 2 ± o n ( ) and all other vertices have degree o n ( ) . Moreover, | E G ( ) | = n -1 + o n ( ) .
- 2. ¯ G has one vertex of degree n -o n ( ) , one vertex of degree n 2 ± o n ( ) , and all other vertices have degree o n ( ) . Moreover | E G ( ) | = 2 n ± o n ( ) .

We need to make some preliminary observations.

Observation 4.4. Let G = ( V, E ) be a graph with n vertices, m edges and t triangles and let C be the coboundary generated by G . Then | C | = nm -∑ v ∈ V d 2 v +4 t .

glyph[negationslash]

Proof. Let e = ( u, v ) ∈ E G ( ) . Then link ( e C ) consists of those vertices x = u, v that are adjacent to both or none of u, v . Namely, | link ( e C ) | = n -d u -d v +2 | N v ( ) ∩ N u ( ) | . Clearly | N v ( ) ∩ N u ( ) | is the number of triangles in G that contain e . But ∑ e ∈ E G ( ) | link ( e C ) | counts every two-face in C three times or once, depending on whether or not it is a triangle in G . Therefore

$$| C | + 2 t = \sum _ { ( u, v ) \in E } \left ( n - d _ { u } - d _ { v } + 2 | N ( v ) \cap N ( u ) | \right ).$$

The claim follows.

Two vertices in a graph are called clones if they have the same set of neighbours (in particular they must be nonadjacent).

Observation 4.5. For every nonempty cut C and x ∈ V the graph link x ( ¯ ) C is connected and has no clones, or it contains one isolated vertex and a complete graph on the rest of the vertices.

$$\text{Proof. Directly follows from the fact that link} _ { x } ( C ) \text{ is } \Lambda \text{-connected (Proposition 2.1).}$$

The size of a cut C for which link x ( ¯ ) C is the union of a complete graph on n -2 vertices and an isolated vertex equals to n -2 , which is much smaller than the bound in Theorem 4.3. We restrict the following discussion to cuts C for which ¯ = link G x ( ¯ ) C is connected and has no clones. Let V = V ( ¯ ) G , and we denote by N v ( ) := N ¯ G ( v ) . For every S ⊆ V , an S -atom is a subset A ⊆ V which satisfies: ( u, v ) ∈ E G ( ¯ ) ⇐⇒ ( u , v ′ ) ∈ E G ( ¯ ) for every u, u ′ ∈ A and v ∈ S .

The next claim generalizes Observation 4.5.

Claim 4.6. Suppose C is a cut and G = ( V, E ) = link x ( C ) for some vertex x / V ∈ . Let S ⊆ V , and G ′ = ¯ G S \ . Then, for every non-empty S -atom A , at least | A | -2 of the edges in G ′ meet A .

Proof. Let H be the subgraph of G ′ induced by an atom A . If H has at most two connected components, the claim is clear, since a connected graph on r vertices has at least r -1 edges. We next consider what happens if H has three or more connected components. We show that every component except possibly one has an edge in ¯ E that connects it to V \ ( S ∪ A ) . This clearly proves the claim.

So let C , C , C 1 2 3 be connected components of H , and suppose that neither C 1 nor C 2 is connected in ¯ G to V \ ( S ∪ A ) . Let F := ∪ 1 ≤ i&lt;j ≤ 3 C i × C j ⊆ E . Since G is Λ -connected, there must be a Λ -path connecting every edge in C 1 × C 2 to every edge in C 2 × C 3 . However, every path that starts in C 1 × C 2 can never leave it. Indeed, let us consider the first time this Λ -path exits C 1 × C 2 , say xy that is followed by yw , where x ∈ C , y 1 ∈ C 2 , w / C ∈ 1 ∪ C 2 and yw / E ∈ . By the atom condition, a vertex in S does not distinguish between vertices x, y ∈ A , whence w / S ∈ . Finally w cannot be in A , for xw / E ∈ would imply that w ∈ C 1 . Hence, C 1 is connected in ¯ G to V \ ( S ∪ A ) , a contradiction.

In the following claims, let G = ( V, E ) = link x ( C ) , for a cut C , and x / ∈ V , and let ¯ G = ( V, E ¯ ) = link x ( ¯ ) C . Denote by d = ( d 1 ≥ d 2 ≥ . . . ≥ d n -1 ≥ 1) the sorted degree sequence of ¯ G . We label the vertices v , . . . , v 1 n -1 so that d v ( i ) = d i for all i .

$$\text{Claim 4.7.} \ d _ { 1 } \leq m / 2 + 1.$$

Proof. Apply Claim 4.6 with S = { v 1 } and A = N v ( 1 ) . It yields the existence of at least | A | -2 edges in ¯ G that meet A but not v 1 . Since | A | = d 1 , m ≥ d 1 +( d 1 -2) , implying the claim.

$$\text{Claim 4.8.} \ d _ { 1 } + d _ { 2 } \leq \frac { m + n } { 2 }.$$

Proof. Apply Claim 4.6 with S = { v , v 1 2 } and A = N v ( 1 ) ∩ N v ( 2 ) to conclude that m ≥ d 1 + d 2 + | A | -3 (as ( v , v 1 2 ) might be an edge). By inclusion-exclusion, n -3 ≥ d 1 + d 2 -| A | . These two inequalities imply the claim.

$$\text{Claim 4.9.  For every } k, \sum _ { i = 1 } ^ { k } d _ { i } \leq m - \frac { n } { 2 } + \frac { k ^ { 2 } } { 2 } + 2 ^ { k }.$$

Proof. There are at most 2 k atoms of S = { v , ..., v 1 k } , and we apply Claim 4.6 to each of them. There are at least | A | -2 edges with one vertex in atom A and the other vertex not in S . Consequently, there are at least 1 2 ( n -k -2 · 2 ) k edges in ¯ G \ S (as each edge may be counted twice). In addition, there may be at most ( ) k 2 edges induced by S , hence the total number of edges is bounded by

$$m \geq \sum _ { i = 1 } ^ { k } d _ { i } - \binom { k } { 2 } + \frac { 1 } { 2 } ( n - k - 2 \cdot 2 ^ { k } )$$

Proof. of Theorem 4.3 Let C be a cut, and assume by contradiction that | ¯ C | ≤ γ 3 n 2 , for some γ &lt; 9 4 . By averaging, there is a link, say ¯ G = ( V, E ¯ ) = link ( ¯ ) v C , of at most 3 | ¯ C | n ≤ γn &lt; 9 n/ 4 edges, where V = [ n ] \ { v } . Let | ¯ E | = m ≤ γn for some γ &lt; 9 4 / . We will show that | ¯ C | ≥ 3 n / 2 4 -o n ( 2 ) contradicting the assumption.

Indeed, Observation 4.4 implies that | ¯ C | = mn -∑ v ∈ ¯ G d 2 v +4 t where t is the number of triangles in ¯ G . Hence it suffices to show that s C ( ¯ ) := mn -∑ v d 2 v ≥ 3 4 · n 2 -o n ( 2 ) .

Given a sequence of reals d = ( d 1 ≥ d 2 ≥ . . . ≥ d n -1 ≥ 1) , we denote f ( d ) := mn -∑ i d 2 i where m = 1 2 ∑ i d i . With this notation s C ( ¯ ) = f ( d ) where d is the sorted degree sequence of ¯ G and v , . . . v 1 n -1 the corresponding ordering of the vertices. I.e., d v ( i ) = d i ≥ d i +1 .

We want to reduce the problem of proving a lower bound on f ( d ) to showing a lower bound on f k ( d ) = mn -∑ k 1 d 2 i , where k = k n ( ) is an appropriately chosen slowly growing function. Clearly f k ( d ) -f ( d ) = ∑ n -1 j = +1 k d 2 j . But d j ≤ 2 m j for all j whence ∑ n -1 j = +1 k d 2 j ≤ 4 m 2 ∑ ∞ j = +1 k 1 j 2 &lt; 4 m 2 k , i.e, f k ( d ) ≤ f ( d ) + 4 m 2 k . Since m&lt; n 9 4 , it suffices to show that f k ( d ) ≥ 3 4 n 2 -o n ( 2 ) for an arbitrary k = ω n (1) , which is our next goal.

We first note that.

Claim 4.10. For every k = (log o n ) , f k ( d ) ≥ mn -d 2 1 -( m -n/ 2 -d 1 ) · d 2 -o n ( 2 ) .

Proof. f k ( d ) = mn -∑ k 1 d 2 i ≥ mn -d 2 1 -( ∑ k 2 d i ) · d 2 ≥ mn -d 2 1 -( m -n/ 2 -d 1 ) · d 2 -o n ( 2 ) , where the second step is by convexity, and the last step uses Claim 4.9.

We now normalize everything in terms of n , namely, write

$$m = \gamma \cdot n, \ \ d _ { 1 } = x \cdot n, \ \ d _ { 2 } = y \cdot n.$$

$$g ( \gamma, x, y ) \coloneqq \frac { 1 } { n ^ { 2 } } f _ { k } - o ( 1 ) = \gamma - x ^ { 2 } - \gamma \cdot y + \frac { y } { 2 } + x y,$$

The problem of minimizing f k subject to our assumptions on γ , d 2 ≤ d 1 , and Claims 4.7, 4.8, 4.9 becomes

## Optimization problem A

Minimize g γ, x, y ( ) , subject to:

$$1. \ 1 \leq \gamma \leq \frac { 9 } { 4 }.$$

$$2. \ 0 \leq y \leq x \leq \min \left ( \frac { \gamma } { 2 }, 1 \right ).$$

$$3. \ x + y \leq \gamma - \frac { 1 } { 2 }.$$

$$4. \ x + y \leq \frac { 1 + \gamma } { 2 }.$$

This problem is answered in the following Theorem whose proof is in the appendix.

Theorem 4.11. The answer to Optmization problem A is min g γ, x, y ( ) = 3 4 . The optimum is attained in exactly two points ( γ = 1 , x = 1 2 , y = 0) and ( γ = 2 , x = 1 , y = 1 2 ) .

Plugging the optimal values on γ, x, y back into Claim 4.10 completes the proof of the Theorem.

Proof of Theorem 4.1. Let us recall some of the facts proved so far concerning the largest n -vertex 2 -hypercut C . Pick an arbitrary vertex v . Since C is a coboundary, it can be generated by an n -vertex graph which consists of the isolated vertex v , and G = link v ( C ) , an ( n -1) -vertex Λ -connected graph. Similarly, ¯ C can be generated by the disjoint union of v and ¯ G . As we saw, there exists some v for which the corresponding ¯ G satisfies either

$$\text{CASE} \left ( \mathbf I \right ) \colon \quad m = n - 1 + o ( n ), \, d _ { 1 } = \frac { n } { 2 } \pm o ( n ) \text{ and } d _ { 2 } = o ( n ),$$

or

$$\text{or} \text{ Case (II) } \colon \quad m = 2 n \pm o ( n ), \ d _ { 1 } = n - o ( n ), \ d _ { 2 } = \frac { n } { 2 } \pm o ( n ) \text{ and } d _ { 3 } = o ( n ).$$

where, as before, m = | E G ( ¯ ) | , d 1 ≥ d 2 ≥ · · · ≥ d n -1 is the degree sequence of ¯ G , with d i = d v ( i ) . We denote by t the number of triangles in ¯ G . Since C is the largest cut, the graph ¯ G attains the minimum of f ( ¯ ) = G nm -∑ d 2 i +4 t among all graphs whose complement is Λ -connected.

We now turn to further analyse the structure of ¯ G , in CASE (I) .

Lemma4.12. Suppose that ¯ G satisfies CASE(I) and let H = ¯ G v \ 1 . Then H is either (i) A perfect matching, or (ii) A perfect matching plus an isolated vertex, or (iii) A perfect matching plus an isolated vertex and a 3-vertex path.

Proof. The proof proceeds as follows: for every H other than the above, we find a local variant ¯ G 1 of ¯ G with f ( ¯ G 1 ) &lt; f G ( ¯ ) . We then likewise modify G 1 to G 2 etc., until for some k ≥ 1 the graph G k is Λ -connected. The process proceeds as follows.

For every connected component U of H of even size | U | ≥ 4 , we replace H | U with a perfect matching on U , and connect v 1 to one vertex in each of these | U | 2 edges. Now all connected components of H are either an edge or have an odd size .

Consider now odd-size components. Note that H can have at most one isolated vertex. Otherwise ¯ G is disconnected or it has clones, so that G is not Λ -connected. As long as H has two odd connected components which together have 6 vertices or more, we replace this subgraph with a perfect matching on the same vertex set, and connect v 1 to one vertex in each of these edges. If the remaining odd connected components are a triangle and an isolated vertex, remove one edge from the triangle, and connect v 1 only to one endpoint of the obtained 3 -vertex path. In the last remaining case H has at most one odd connected component U .

If no odd connected components remain or if | U | = 1 , we are done.

In the last remaining case H has a single odd connected component of order | U | ≥ 3 . We replace H | U with a matching of ( | U | -1) / 2 edges, connect v 1 to one vertex in each edge of the matching and to the isolated vertex. If, in addition, there is a connected component of order 2 with both vertices adjacent to v 1 (Note that by the proof of Claim 4.6 there is at most one such component.), we remove as well one edge between v 1 and this component.

All these steps strictly decrease f . We show this for the first kind of steps. The other cases are nearly identical.

Recall that | E H ( ) | = n 2 ± o n ( ) and that H has at most one isolated vertex. Therefore every connected component in H has only o n ( ) vertices. Let U be a connected component with 2 u ≥ 4 vertices of which 0 &lt; r ≤ 2 u are neighbours of v 1 , and let β = | E H ( | U ) | -(2 u -1) ≥ 0 . Let ¯ G ′ be the graph after the aforementioned modification w.r.t. U . We denote its number of edges and triangles by m ′ and t ′ resp., and its degree sequence by d ′ i . Then,

$$f ( \bar { G } ) - f ( \bar { G } ^ { \prime } ) = n ( m - m ^ { \prime } ) - \sum ( d _ { i } ^ { 2 } - d _ { i } ^ { \prime 2 } ) + 4 ( t - t ^ { \prime } ) \geq$$

$$f ( \bar { G } ) - f ( \bar { G } ^ { \prime } ) = n ( m - m ^ { \prime } ) - \sum _ { i } ( d _ { i } ^ { 2 } - d _ { i } ^ { 2 } ) + 4 ( t - t ^ { \prime } ) \geq \\ n ( \beta + r - 1 ) - \left ( d _ { 1 } ^ { 2 } - ( d _ { 1 } - r + u ) ^ { 2 } \right ) - \sum _ { i \in U } d _ { i } ^ { 2 } \geq \\ n ( \beta + r - 1 ) + ( u - r ) \left ( 2 d _ { 1 } + u - r \right ) - 2 u ( 4 u - 2 + 2 \beta + r ).$$

In the second row we use t ≥ t ′ , which is true since the modification on U creates no new triangles. In the third row we use ∑ i ∈ U d 2 i ≤ (max i ∈ U d i ) (∑ i ∈ U d i ) .

Let us express d 1 = n -w 2 where w = ( ) o n . What remains to prove is that

$$n ( \beta + u - 1 ) + ( u - r ) ( u - r - w ) \geq 2 u ( 4 u - 2 + 2 \beta + r ).$$

Or, after some simple manipulation, and using the fact r ≤ 2 u , that

$$\beta n + ( u - 1 ) n \geq 4 \beta u + u ( 7 u + w + 3 r - 4 ).$$

This is indeed so since u = ( ) o n implies that βn glyph[greatermuch] βu and 2 ≤ u ≤ o n ( ) implies ( u -1) n glyph[greatermuch] u (7 u + +4 w r -4) . The other cases are done very similarly, with only minor changes in the parameters. In the case of two odd connected components which together have 2 u ≥ 6 vertices, in the final step the main term is ( β + u -2) n ≥ n + βu since u &gt; 2 . In the case of changing a triangle to a 3-vertex path the main term in the final inequality is ( β + u -1) n = n .

The structure of ¯ G for CASE (I) is almost completely determined by Lemma 4.12. Since G is Λ -connected, in ¯ Gv 1 must have a neighbour in each component of H , and can be fully connected to at most one component. In addition, if P is a 3-vertex path in H , then v 1 has exactly one neighbour in P which is an endpoint. Otherwise we get clones. Therefore the only possible graphs are those that appear in Figure 1. The first row of the figure applies to odd n , where the optimal ¯ G satisfies f ( ¯ ) G = 3 4 n 2 -4 n + 25 4 . The other rows correspond to n even, with four optimal graphs that satisfy f ( ¯ ) = G 3 4 n 2 -7 2 n +4 .

Figure 1: The graphs ¯ G that are considered in the final stage of the proof of CASE (I) . The first row refers to the only possibility for odd n . The second row to even n , where H is a perfect matching. The third row refers to even n , where H a disjoint union of an isolated vertex, 3-path and a matching.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0602v3-figure-bbaf9d88-64e7-4634-9abc-f6029c08f5f4.jpg)

This concludes CASE (I) , and we now turn to Case (II) . Our goal here is to reduce this back to CASE (I) , and this is done as follows.

Claim 4.13. Let ¯ G = link ( ¯ ) v C be a graph on n -1 vertices with parameters as in CASE (II) . If H = ¯ G \ { v , v 1 2 } has an isolated vertex z that is adjacent in ¯ G to v 1 then f ( ¯ ) G is bounded by the extremal examples found in CASE (I) .

Proof. Let S be the star graph on vertex set V ∪{ } v with vertex v 1 in the center and n -1 leaves. Consider the graph F := ¯ G ⊕ S on the same vertex set, whose edge set is the symmetric difference of E S ( ) and E G ( ¯ ) . Since every triplet meets S in an even number of edges, the coboundary that F generates equals to the coboudnary that ¯ G generates, which is ¯ C .

In addition, z is an isolated vertex in F since its only neighbor in ¯ G is v 1 . Consequently, F = link ( ¯ ) z C , and the claim will follow by showing that F agrees with the conditions of CASE (I) . Indeed, deg F ( v 1 ) = n - -1 deg ¯ G ( v 1 ) = o n ( ) , and | deg F ( u ) -deg ¯ G ( u ) | ≤ 1 for every other vertex u . Hence, deg F ( v 2 ) = n 2 ± o n ( ) , and deg F ( u ) = o n ( ) for every other vertex u .

If H has no isolated vertex that is adjacent in ¯ G to v 1 , we show how to modify ¯ G to a graph ¯ G 1 , such that (i) G 1 is Λ -connected, (ii) ¯ G 1 \ { v , v 1 2 } has an isolated vertex which is adjacent to v 1 in ¯ G 1 , and (iii) f ( ¯ G 1 ) &lt; f G ( ¯ ) .

glyph[negationslash]

Since G is Λ -connected and using the proof of claim 4.6, H has at most one connected component U 1 in H where all vertices are adjacent to v 1 and not to v 2 in ¯ G . Similarly, it has at most one connected component U 2 where all vertices are adjacent to both v 1 and v 2 . Also, since d 1 = n -o n ( ) , d 2 = n 2 ± o n ( ) and H has at most 3 isolated vertices, there exists an edge xy ∈ E H ( ) such that xv , xv 1 2 , yv 1 ∈ E G ( ¯ ) , but yv 2 ∈ E G ( ¯ ) .

G 1 is constructed as following:

- 1. If neither components U 1 nor U 2 exist, remove the edge xy and the edge v v 1 2 , if it exists. Otherwise, let r := | U 1 ∪ U 2 | .
- 2. If r is even, replace it in H with a perfect matching on u -2 vertices and two isolated vertices. Connect v 1 to every vertex in U 1 ∪ U 2 . Make v 2 a neighbor of one of the isolated vertices, and one vertex in each of the edges of the matching. Additionally, remove the edge v v 1 2 if it exists.
- 3. If u is odd, replace it in H by a perfect matching on u -1 vertices and one isolated vertex. Connect v 1 to every vertex in U 1 ∪ U 2 , and v 2 to one vertex in each edge of the matching.

.

The fact that value of f decreased is shown similarly to the calculation in CASE (I)

## 5 Large d -hypercuts over F 2 in even dimensions

In this section we consider large d -dimensional hypercuts over F 2 for d &gt; 2 . We show that for d even the largest d -hypercuts have ( n d +1 ) (1 -o n (1)) d -faces. In contrast, for odd d we observe that the density of every d -hypercut is bounded away from 1 .

Theorem 5.1. For every d ≥ 2 even there exists an n -vertex d -hypercut over F 2 with ( n d +1 ) (1 -o n (1)) d -faces.

Before we prove the theorem, let us explain why the situation is different in odd dimensions. Recall that Turan's problem (e.g., [10]) asks for the largest density ex n, K ( d +1 d +2 ) of a ( d +1) -uniform hypergraph that does not contain all the hyperedges on any set of ( d +2) vertices. For d odd a hypercut has this property, because (see Section 2), the characteristic vector C ∈ F ( n d +1 ) 2 of a d -hypercut is a coboundary, i.e., C · ∂ d +1 = 0 . A simple double-counting argument shows that the density of C cannot exceed 1 -1 d +2 , and in fact, a better upper bound of 1 -1 d +1 is known [17]. One of the known constructions for the Turan problem yields d -coboundaries with density 3 4 -1 2 d +1 -o (1) for d odd [4]. In particular for d = 3 this gives a lower bound of 11 16 = 0 6875 . . In YP's MSc thesis [16] an upper bound of 0 6917 . was found using flag algebras.

We now turn to prove the theorem for some d ≥ 4 even. As before, a d -hypercut C is an inclusion-minimal set of d -faces whose characteristic vector is a coboundary. In addition, every d -coboundary C and every vertex v satisfy C = link ( v C ) · ∂ d . Recall that C is a 2 -hypercut iff link v ( C ) is Λ -connected for some vertex v . In dimension &gt; 2 we do not have such a charaterization, but as we show below, an appropriate variant of the sufficient condition for being a hypercut does apply in all dimensions.

Let τ, τ ′ be two ( d -1) -faces in a ( d -1) -complex K . We say that they are Λ -adjacent if their union σ = τ ∪ τ ′ has cardinality d + 1 , and τ, τ ′ are the only d -dimensional subfaces of σ in K . We say that K is Λ -connected if the transitive closure of the Λ -adjacency relation has exactly one class.

Claim 5.2. Let C be a d -dimensional coboundary such that the ( d -1) -complex K = link v ( C ) is Λ -connected for some vertex v . Then C is a d -hypercut.

Proof. Suppose that ∅ glyph[negationslash] = C ′ glyph[subsetnoteql] C is a d -coboundary and let K ′ = link ( v C ′ ) . Note that ∅ glyph[negationslash] = K ′ glyph[subsetnoteql] K and therefore there are ( d -1) -faces τ, τ ′ which are Λ -adjacent in K such that τ ′ ∈ K ′ and τ / K ∈ ′ . Consider the d -dimensional simplex σ = τ ∪ τ ′ . On the one hand, since exactly two of the facets of σ are in K , it does not belong to C = K ∂ · d . On the other hand, it does belong to C ′ since exactly one of its facets ( τ ′ ) is in K ′ . This contradicts the assumption that C ′ ⊂ C .

Proof of Theorem 5.1. We start by constructing a random ( n -1) -vertex ( d -1) -dimensional complex K that has a full skeleton, where each ( d -1) -face is placed in K independently with probability p := 1 -n -1 3 d -3 . We show that with probability 1 -o n (1) the complex K is Λ -connected, whence C := K ∂ · d is almost surely a d -hypercut of the desired density.

We actually show that K satisfies a condition that is stronger than Λ -connectivity. Namely, let τ, τ ′ ∈ K be two distinct ( d -1) faces. We find π, π ′ where π is Λ -adjacent to τ and π ′ is Λ -adjacent to τ ′ and in addition the symmetric differences get smaller | π ⊕ π ′ | &lt; τ | ⊕ τ ′ | . To this end we pick some vertices u ∈ τ \ τ ′ , u ′ ∈ τ ′ \ τ and aim to show that with high probability there is some x / τ ∈ ∪ τ ′ for which the following event P x holds:

$$d \, \pi ^ { \prime } \, \dashv \, - \, \pi ^ { \prime } + \, \tilde { I } \, \tilde { r } \, \lambda \, \vee \, \tilde { r } \, \tilde { r } \, \alpha \, \text{a}$$

$$\pi _ { x } \coloneqq \tau \cup \{ x \} \, \sum \{ u \} \, \text{and} \, \pi _ { x } ^ { \prime } \coloneqq \tau ^ { \prime } \cup \{ x \} \, \sum \{ u ^ { \prime } \} \, \text{are in} \, K, \text{ and} \\ \tau \text{ is } \Lambda - \text{ adjacent to } \pi _ { x } \text{ and } \tau ^ { \prime } \text{ is } \Lambda \text{- adjacent to } \pi _ { x } ^ { \prime }$$

In other words, it is required that π x ∈ K and τ ∪ { x } \ { w } ∈ / K for every w ∈ τ \ { u } , and similarly for τ , π ′ ′ x . Therefore Pr( P x ) = p 2 · (1 -p ) 2 d -2 . Moreover, the events { P x | x / τ ∈ ∪ τ ′ } are independent. Hence, the claim fails for some τ, τ ′ with probability at most ( 1 -p 2 · (1 -p ) 2 d -2 ) n -2 d = exp[ -Θ( n 1 3 / )] . The proof is concluded by taking the union bound over all pairs τ, τ ′ .

## 6 Large Collapsible 2 -dimensional Hyperforests with no Shadow

The main result of this section is a construction of a shadowless F -acyclic 2 -complex over every field F . Recall that assuming Artin's conjecture there are infinitely many shadowless 2 -dimensional Q -almost hypertrees. We saw in Section 4 that every F 2 -almost hypertree has a shadow and there we discussed its minimal caridnality. We now complement this by seeking the largest number of 2 -faces in shadowless hyperforests. Our construction works at once for all fields since it is based on the combinatorial property of 2 -collapsibility.

Theorem 6.1. For every odd integer n , there exists a 2 -collapsible 2 -complex A = A n with ( n -1 2 ) -( n +1) faces that remains 2 -collapsible after the addition of any new face. In particular, this complex is acyclic and shadowless over every field.

Proof. The vertex set V = V ( A ) is the additive group Z n . All additions here are done mod n . Edges in A are denoted ( x, x + ) a with a &lt; n/ 2 , and such an edge is said to have length a . Also, for a &gt; 1 , b = ⌊ a 2 ⌋ is uniquely defined subject to 1 ≤ b &lt; a &lt; n/ 2 . For every x ∈ Z n and n/ 2 &gt; a &gt; 1 we say that the edge ( x, x + ) a yields the face ρ x,a := { x, x + a, x + ⌊ a 2 ⌋ } of length a . These are A 's 2 -faces:

glyph[negationslash]

$$\{ \rho _ { x, a } \, | \, n / 2 > a \neq 1, 3, \, x \in \mathbb { Z } _ { n } \}$$

It is easy to 2 -collapse A by collpasing A 's faces in decreasing order of their lengths. In each phase of the collapsing process, the longest edges in the remaining complex are exposed and can be collapsed.

It remains to show that the complex A ∪ { σ } is 2 -collapsible for every face σ = { x, y, z } ∈ / A . To this end, let us carry out as much as we can of the 'top-down' collapsing process described above. Clearly some of the steps of this process become impossible due to the addition of σ , and we now turn to describe the complex that remains after all the possible steps of the previous collapsing process are carried out. Subsequently we show how to 2 -collapse this remaining complex and conclude that A ∪ { σ } is 2 -collpasible, as claimed.

glyph[negationslash]

For every n/ 2 &gt; a ≥ 1 , x ∈ Z n we define a subcomplex C x,x + a ⊂ A . If a = 1 or 3 , this is just the edge ( x, x + ) a . For all n/ 2 &gt; a = 1 3 , it is defined recursively as C x, x + glyph[floorleft] a 2 glyph[floorright] ∪ C x + glyph[floorleft] a 2 glyph[floorright] , x + a ∪ { ρ x,a } .

Note that C x,y is a triangulation of the polygon that is made up of the edge ( x, y ) and C x,y ( ) 's edges of lengths 1 and 3 .

Our proof will be completed once we (i) Observe that this remaining complex is ∆ := σ { σ }∪ C x,y ∪ C x,z ∪ C y,z , and (ii) Show that ∆ σ is 2 -collapsible.

Indeed, toward (i), just follow the original collapsing process and notice that ∆ σ is comprised of exactly those faces in A that are affected by the introduction of σ into the complex.

We will show (ii) by proving that the face σ can be collapsed out of ∆ σ . Consequently, ∆ σ is 2 -collapsible to a subcomplex of the 2 -collapsible complex A .

As we show below

Claim 6.2. There exists a vertex in ∆ σ which belongs to exactly one of the complexes C x,y , C x,z or C y,z .

This allows us to conclude that the face σ can be collapsed out of ∆ σ . Say that the vertex v is in C x,y and only there, and let e be some edge of length 1 or 3 in C x,y that contains v . Follow the recursive consturction of C x,y as it leads from ( x, y ) to e . Every edge that is encountered there appears only in the polygon C x,y . By traversing this sequence in reverse, we collpase σ out of ∆ σ .

Proof of Claim 6.2. By translating mod n if necessary we may assume that x = 0 and 0 &lt; y, z -y &lt; n 2 . If z &gt; n 2 , then V ( C 0 ,y ) ⊆ { 0 , ..., y } , V ( C y,z ) ⊆ { y, ..., z } and V ( C z, 0 ) ⊆ { z, ..., n -1 0 , } , so their vertex sets are nearly disjoint altogether.

We now consider the case z &lt; n 2 and assume by contradiction that the claim fails for σ = { 0 , y, z } . We want to conclude that σ ∈ A , and in fact σ ∈ C 0 ,z . By the recursive construction of C 0 ,z , this, in other words, means that both edges (0 , y ) and ( y, z ) are in C 0 ,z . We only prove that (0 , y ) ∈ C 0 ,z , and the claim ( y, z ) ∈ C 0 ,z follows by an essentially identical argument.

So we fix 0 &lt; y &lt; z &lt; n 2 and we want show that glyph[negationslash]

$$\text{If } ( 0, y ) \not \in C _ { 0, z } \text{ then } V ( C _ { 0, z } ) \cap [ 0, y ] \not = V ( C _ { 0, y } ).$$

Consequently, there is a vertex v in [0 , y ] which belongs to exactly one of the complexes C 0 ,z and C 0 ,y . If such a v &lt; y exists, we are done, since C y,z has no vertices in [0 , y -1] . Otherwise,

$$V ( C _ { 0, z } ) \cap [ 0, y - 1 ] = V ( C _ { 0, y } ) \, \wedge \, \{ y \} \ \text{ and } \ y \notin C _ { 0, z }.$$

But the vertices of C 0 ,z form an increasing sequence from 0 to z with differences 1 or 3 , so either ( y -2 , y +1) ∈ C 0 ,z or ( y -1 , y +2) ∈ C 0 ,z . In the former case, both y -2 and y are vertices in C 0 ,y , and therefore y -1 ∈ C 0 ,y and consequently y -1 ∈ C 0 ,z , contrary to the assumption that the edge ( y -2 , y +1) is in C 0 ,z . In the latter

case, y +2 ∈ C 0 ,z and y +1 / C ∈ 0 ,z . Which vertex succeeds y in C y,z ? If ( y, y +1) ∈ C y,z then y +1 belongs only to C y,z . If ( y, y +3) ∈ C y,z then y +2 is only in C 0 ,z .

glyph[negationslash]

glyph[negationslash]

We prove the implication (2) by induction on y . The base cases where y = 1 or y = 3 , are straightforward. If (0 , ⌊ y 2 ⌋ ) / C ∈ 0 ,z then by induction V ( C 0 ,z ) ∩ [0 , ⌊ y 2 ⌋ ] = V ( C 0 , glyph[floorleft] y 2 glyph[floorright] ) . But V ( C 0 ,y ) ∩ [0 , ⌊ y 2 ⌋ ] = V ( C 0 , glyph[floorleft] y 2 glyph[floorright] ) and the conclusion that V ( C 0 ,z ) ∩ [0 , y ] = V ( C 0 ,y ) follows. We now consider what happens if (0 , ⌊ y 2 ⌋ ) ∈ C 0 ,z . Which edge has yielded the 2 -face of C 0 ,z that contains the edge (0 , ⌊ y 2 ⌋ ) ? It can be either (0 2 , · ⌊ y 2 ⌋ ) or (0 2 , · ⌊ y 2 ⌋ +1) . But one of these two edges is (0 , y ) which, by assumption, is not in C 0 ,z , so it must be the other one. Namely, either y = 2 r and (0 2 , r +1) ∈ C 0 ,z or y = 2 r +1 and (0 , 2 ) r ∈ C 0 ,z .

Let us deal first with the case y = 2 r . Assume, in contradiction to (2), that V ( C 0 ,z ) ∩ [0 , 2 ] = r V ( C 0 2 , r ) . In particular V ( C 0 ,z ) ∩ [ r, 2 ] = r V ( C 0 2 , r ) ∩ [ r, 2 ] r . But since (0 2 , r +1) is an edge of C 0 ,z it also follows that V ( C 0 2 , r +1 ) ∩ [ r, 2 ] = r V ( C 0 ,z ) ∩ [ r, 2 ] r . Therefore,

$$V ( C _ { 0, 2 r + 1 } ) \cap [ r, 2 r ] = V ( C _ { 0, 2 r } ) \cap [ r, 2 r ].$$

By the recursive consturction of C 0 2 , r +1 and C 0 2 , r we obtain that V ( C r, 2 +1 r ) ∩ [ r, 2 ] = r V ( C r, 2 r ) . By using the rotational symmetry of A we can translate this equation by r to conclude that V ( C 0 ,r +1 ) ∩ [0 , r ] = V ( C 0 ,r ) . By induction, using the contrapositive of Equation (2) this implies that (0 , r ) ∈ C 0 ,r +1 hence r = 1 . However, C 0 ,z cannot contain both (0 , 3) and (0 1) , so we are done.

The argument for y = 2 r +1 is essentially the same and is omitted.

## 7 Open Problems

- · There are several problems that we solved here for 2 -dimensional complexes. It is clear that some completely new ideas will be required in order to answer these questions in higher dimensions. In particular it would be interesting to extend the construction based on arithmetic triples for d &gt; 2 .
- · An interesting aspect of the present work is that the behavior over F 2 and Q differ, some times in a substantial way. It would be of interest to investigate the situation over other coefficient rings.
- · How large can an acyclic closed set over F 2 be? Theorem 6.1 gives a bound, but we do not know the exact answer yet.
- · We still do not even know how large a d -cycle can be. In particular, for which integers n, d and a field F does there exist a set of ( n -1 d ) +1 d -faces on n vertices such that removing any face yields a d -hypertree over F ?
- · Many basic (approximate) enumeration problems remain wide open. How many n -vertex d -hypertrees are there? What about d -collapsible complexes? A fundamental work of Kalai [9] provides some estimates for the former problem, but these bounds are not sharp. In one dimension there are exactly ( n -1)! 2 inclusionminimal n -vertex cycles. We know very little about the higher-dimensional counterparts of this fact.

## References

- [1] Ron M. Adin. Counting colorful multi-dimensional trees. Combinatorica , 12(3):247-260, 1992.
- [2] Eric Babson, Christopher Hoffman, and Matthew Kahle. The fundamental group of random 2-complexes. Journal of the American Mathematical Society , 24(1):1-28, 2011.
- [3] Anders Bj¨ orner and Gil Kalai. An extended euler-poincar´ e theorem. Acta Mathematica , 161(1):279-303, 1988.

- [4] D. de Caen, D.L. Kreher, and J. Wiseman. On constructive upper bounds for the Tur´ an numbers T(n,2r+1,r). Congressus Numerantium , 65:277-280, 1988.
- [5] Daniel Cohen, Armindo Costa, Michael Farber, and Thomas Kappeler. Topology of random 2-complexes. Discrete Computational Geometry , 47(1):117-149, 2012.
- [6] Rajendraprasad Deepak, Ilan Newman, Rogers Matthews, and Yuri Rabinovich. Extremal problems on cycles in simplicial complexes. in preparation .
- [7] Art Duval, Caroline Klivans, and Jeremy Martin. Simplicial matrix-tree theorems. Transactions of the American Mathematical Society , 361(11):6073-6114, 2009.
- [8] Mikhail Gromov. Singularities, expanders and topology of maps. part 2: From combinatorics to topology via algebraic isoperimetry. Geometric and Functional Analysis , 20(2):416-526, 2010.
- [9] Gil Kalai. Enumeration of Q -acyclic simplicial complexes. Israel Journal of Mathematics , 45(4):337-351, 1983.
- [10] Peter Keevash. Hypergraph tur´ an problems. Surveys in combinatorics , 392:83-140, 2011.
- [11] Nathan Linial and Roy Meshulam. Homological connectivity of random 2-complexes. Combinatorica , 26(4):475-487, 2006.
- [12] Nathan Linial, Roy Meshulam, and Mishael Rosenthal. Sum complexes - a new family of hypertrees. Discrete &amp; Computational Geometry , 44(3):622-636, 2010.
- [13] Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Ramanujan complexes of type ˜ A d . Israel Journal of Mathematics , 149(1):267-299, 2005.
- [14] Pieter Moree. Artin's primitive root conjecture-a survey. 2012.
- [15] Ilan Newman and Yuri Rabinovich. On multiplicative λ -approximations and some geometric applications. SIAM Journal on Computing , 42(3):855-883, 2013.
- [16] Yuval Peled. Combinatorics of simplicial cocycles and local distributions in graphs. Master's thesis, Hebrew University of Jerusalem, 2012.
- [17] A. Sidorenko. The method of quadratic forms and tur´ an's combinatorial problem. Moscow University Mathematics Bulletin , 37(1):1-5, 1982.

## A Appendix - Proof of Theorem 4.11

Let h γ, x, y ( ) = g γ, x, y ( ) -3 4 = γ -x 2 -3 4 -y γ ( -1 2 -x ) . We need to show that h ≥ 0 under the conditions of the optimization problem. This involves some case analysis.

First note γ -1 2 -x ≥ 0 by condition 3, so that for fixed γ, x we have that h is a decreasing function of y . Thus, to minimize h , we need to determine the largest possible value of y .

- 1. We first consider the range γ ≤ 2 . Here condition 4 is redundant, and y ≤ min { x, γ -1 2 -x } .
- (a) We further restrict to the range x ≤ γ 2 -1 4 , where x ≤ γ -1 2 -x , so the largest feasible value of y is y = x . Note that h | y = x = γ -3 4 -x γ ( -1 2 ) . But γ -1 2 ≥ 0 by condition 1, so h is minimized by maximizing x , namely taking x = γ 2 -1 4 . This yields h = 1 8 -1 2 ( γ -1)( γ -2) which is positive in the relevant range 2 ≥ γ ≥ 1 .

- (b) In the complementary range γ 2 -1 4 ≤ x the largest value for y is y = γ -1 2 -x which yields h = γ -x 2 -3 4 -( γ -1 2 -x ) 2 = -2( x -γ 2 )( x -γ -1 2 ) -( γ -1)( γ -2) 2 . It suffices to check that h ≥ 0 at both extreme value of x , namely γ 2 -1 4 and γ/ 2 . Also h = 0 only at x = γ/ 2 with γ = 1 or 2 .
- 2. In the complementary range γ ≥ 2 , condition 3 is redundant and condition 4 takes over.
- (a) Assume first that x ≤ 1+ γ 4 , then x ≤ 1+ γ 2 -x and the extreme value for y is y = x . Again h | y = x = γ -3 4 -x γ ( -1 2 ) and now the largest possible value of x is x = 1+ γ 4 which yields h = (5 -2 γ )( γ -1) 8 . This is positive at the range 9 4 ≥ γ ≥ 2 .
- (b) When x ≥ 1+ γ 4 the minimum h is attained at y = 1+ γ 2 -x , so that

$$h = \gamma - x ^ { 2 } - \frac { 3 } { 4 } - ( \frac { 1 + \gamma } { 2 } - x ) \cdot ( \gamma - \frac { 1 } { 2 } - x ) = - 2 ( x - 1 ) ( x + 1 - \frac { 3 \gamma } { 4 } ) - \frac { 1 } { 2 } ( \gamma - 2 ) ( \gamma - \frac { 5 } { 2 } ).$$

For fixed γ it suffices to check that h ≥ 0 at the two ends of the range 1 ≥ x ≥ 1+ γ 4 . At x = 1 we get h = -1 2 ( γ -2)( γ -5 2 ) which is nonnegative when 9 4 ≥ γ ≥ 2 with h = 0 only at γ = 2 . When x = 1+ γ 4 , we get h = (5 -2 γ )( γ -1) 8 which is positive for 9 4 ≥ γ ≥ 2 .

To sum up, h ≥ 0 throughout the relevant range with two point where h = 0 , namely γ = 2 , x = 1 , y = 1 2 and γ = 1 , x = 1 2 , y = 0 .
Nati Linial Ilan Newman Yuval Peled Yuri Rabinovich
Extremal problems on shadows and hypercuts in simplicial complexes
Let $F$ be an $n$-vertex forest. We say that an edge $e\notin F$ is in the
shadow of $F$ if $F\cup\{e\}$ contains a cycle. It is easy to see that if $F$
is "almost a tree", that is, it has $n-2$ edges, then at least
$\lfloor\frac{n^2}{4}\rfloor$ edges are in its shadow and this is tight.
Equivalently, the largest number of edges an $n$-vertex cut can have is
$\lfloor\frac{n^2}{4}\rfloor$. These notions have natural analogs in higher
$d$-dimensional simplicial complexes, graphs being the case $d=1$. The results
in dimension $d>1$ turn out to be remarkably different from the case in graphs.
In particular the corresponding bounds depend on the underlying field of
coefficients. We find the (tight) analogous theorems for $d=2$. We construct
$2$-dimensional "$\mathbb Q$-almost-hypertrees" (defined below) with an empty
shadow. We also show that the shadow of an "$\mathbb F_2$-almost-hypertree"
cannot be empty, and its least possible density is $\Theta(\frac{1}{n})$. In
addition we construct very large hyperforests with a shadow that is empty over
every field.
  For $d\ge 4$ even, we construct $d$-dimensional $\mathbb{F}
_2$-almost-hypertree whose shadow has density $o_n(1)$.
  Finally, we mention several intriguing open questions.