I am trying to prove a certain statement that seems true based on computational data, and there is a nice argument that proves it, assuming all cycles are the simplest ones (e.g., when the only 1-cycles are triangles and never squares, pentagons, etc.). In real life these are not the only cycles, so this is not a real proof. I'll state the proposition and the "proof" to begin with.

First some definitions. A set $S$ of integers is said to be coprime-free if for all $i,j\in S$ with $i\ne j$, $\gcd(i,j)>1$. A coprime-free subset $S\subseteq [n]$ is said to be maximal if $S\cup \{x\}$ is not coprime free for all $x\in [n]\setminus S$. Let $\Delta_n$ be the simplicial complex whose vertices are the maximal coprime-free subsets of $n$, with a face for every set of vertices with nonempty intersection. In the following, when we speak of homology of $\Delta_n$ and write $H_k(\Delta_n)$, we mean homology over ${\bf Z}$.

Proposition. For all $k\ge 1$, $H_k(\Delta_n)=0$.

"Proof". Let $k\ge 1$ be given and suppose that $x_1,x_2,\ldots,x_{k+2}$ are vertices in $\Delta_n$ such that $\{x_1,\ldots,x_{k+2}\}$ is not a face but for all $1\le i \le k+2$, the set $F_i = \{x_1,\ldots,x_{k+2}\}\setminus\{x_i\}$ does form a face. In other words, $\bigcap_{i=1}^{k+2} x_i = \emptyset$, but for all $i$, the set $\bigcap F_i$ does contain some element, call it $a_i$. Now consider the set $A=\{a_1,\ldots,a_m\}$. If for some pair $i\ne j$ we have $\gcd(a_i,a_j) = 1$ for some $i$ and $j$, then we use the fact that $k+2\ge 3$ to pick $t\in [k+2]\setminus\{i,j\}$ and note that $a_i$ and $a_j$ are both in $x_t$, which would imply that $x_t$ is not coprime-free. So we conclude that $a_i$ and $a_j$ are not coprime for all $i\ne j$. Thus $\{a_1,\ldots,a_{k+2}\}$ is a subset of some maximal coprime-free subset of $[n]$, call it $x$. The above reasoning shows that $\{x,x_1,\ldots,x_{k+2}\}$, viewed as a simplicial subcomplex of $\Delta_n$, is a $(k+2)$-simplex missing its interior as well as exactly one of its $(k+1)$-faces, namely $\{x_1,\ldots,x_{k+2}\}$. The $k$th homology of this simplicial subcomplex is zero, so the $(k+2)$-tuple $(x_1,\ldots,x_{k+2})$ contributes nothing to the $k$th homology of $\Delta_n$. Since $x_1,\ldots,x_{k+2}$ were arbitrary, we are done."▮"

In the general case where a $k$-cycle may be formed by more than $k+2$ vertices (in the way that a square is still a $1$-cycle, being a formal sum of two triangles), I am wondering if there is some way of taking this result that we have and stacking it upon itself in some way. Or if there is some other way of amending the proof above. The reason that I would like to amend the proof above rather than start from scratch is that, under some delusion many months ago, I wrote some other "proofs" just like the one above, forgetting about the general case of $k$-cycles, and it is a naive hope of mine that there is some general schema for taking all of my false homology proofs and promoting them to real ones.

Sorry if the second part of my question is a bit wobbly and ill-defined, but really any help on this would be much appreciated. Thanks in advance!

Edit. I think I was able to prove it using the nerve complex that Andy Putman suggested below. Here is what I have. The part about retracting simplices down I feel is correct, but perhaps I have not expressed it rigorously enough. Any feedback on this proof would be much appreciated.

Applying Borsuk's nerve theorem to Andy Putman construction and observations,$\Delta_n$ is homotopy equivalent to the simplicial complex $X_n$ whose vertex set is $[n]$ and in which a subset $J\subseteq [n]$ is a face if and only if $J$ is coprime-free. We also know that $X_n$ has $C(n)+2$ connected components, $C(n)+1$ of which are singletons. The nontrivial connected component, call it $X_n'$, consists of all primes in the range $[2,n/2]$ as well as all composite numbers in $[n]$. The claim is that $X_n'$ is contractible.

We will construct the deformation retraction to a single point in steps. First note that the set $V_2$ all even vertices, viewed as a subcomplex of $X_n'$, is a simplex, so we may retract this down to a point without altering the homotopy of $X_n'$. Call this point $\bar 2$. Now in this new complex, consider the set $V_3$ of all vertices whose smallest prime divisor is $3$ ($V_3$ includes all remaining multiples of $3$, since all multiples of $6$ were retracted to the point $\bar 2$). The subcomplex on $V_3\cup \{\bar 2\}$ is a simplex, since in the original complex $X_n'$, the set of vertices divisible by $3$ was a simplex, and all we have done is retract some subsimplex consisting of vertices divisible by $6$ to a point, call it $\bar 3$. The same will be possible when we define the set $V_5$ of all integers whose smallest prime divisor is $5$, and then consider $V_5\cup \{\bar 3\}$. Continuing this reasoning, we may perform a retraction for every prime $p\in [2,p/2]$ until all we are left with is a single point.

  • 2
    $\begingroup$ Isn't $S=\{2\cdot 3, 3\cdot 5,5\cdot 7,7\cdot 2\}$ a counterexample? All coprime-free subsets have $\leq 2$ elements, and the maximal ones form a cycle of length $4$. $\endgroup$ Sep 12 at 7:55
  • $\begingroup$ I think in this question we do not start with an arbitrary subset of the natural numbers, but only with sets of the form ${1,..,n}$ and then we consider its coprime-free subsets. So the statement could still be true. However, I do not see where the proof makes use of that, so your example suggests that the proof might not be fixable. $\endgroup$ Sep 12 at 8:35
  • $\begingroup$ Another (possibly equivalent) way of defining a simplicial complex is to drop the maximality condition and say that a subset of vertices $S_1,\ldots,S_n$ forms a simplex, if the sets form a chain $S_1\subset \ldots \subset S_n$ (possibly after reordering). $\endgroup$ Sep 12 at 8:39
  • 1
    $\begingroup$ Note that the given argument doesn't use that the ambient set is $\{1,\ldots,n\}$, so there is really something extra needed to rule out examples like @AchimKrause's comment. You cannot just bootstrap from the given argument. $\endgroup$ Sep 13 at 0:02
  • 1
    $\begingroup$ Discrete morse theory is often useful to prove this kind of thing. $\endgroup$
    – Jim Conant
    Sep 13 at 3:21

4 Answers 4


Let $G_n$ be the graph with vertex set $\{2,\ldots,n\}$ in which there is an edge $ij$ if and only if $\mathrm{gcd}(i,j)>1$. The simplicial complex mentioned in Andy Putman's answer, as well as in your other StackExchange question is flag, and it is the clique complex $\mathrm{Cl}(G_n)$ of this graph (modulo the isolated one-point components of primes $p>n/2$). Ie. the simplices of the complex are the cliques (complete subgraphs) of the graph.

The homotopy type of $\mathrm{Cl}(G_n)$ can be analyzed using some standard techniques for flag complexes. Let $N_G[v]$ denote the closed neighborhood of $v$ in $G$, that is the set of vertices adjacent to $v$ plus also $v$ itself. If $N_G[v]\subseteq N_G[u]$ for two different vertices $u,v$ then $\mathrm{Cl}(G)$ collapses to $\mathrm{Cl}(G\setminus v)$, in particular they are homotopy equivalent. This is because the link of $v$ in $\mathrm{Cl}(G)$ is a cone with apex $u$, hence contractible. In Barmak and Minian's papers this would be called a strong collapse and the vertex $v$ would be called dominated by $u$. We can use that terminology.

Our graph $G_n$ is very susceptible to strong collapsing because it has a lot of dominating vertex pairs. If the set of primes dividing $i$ is a subset of the set of primes dividing $j$ then $i$ is dominated by $j$ (every number not-coprime to $i$ is not-coprime to $j$), so $i$ can be removed without affecting the homotopy type of the clique complex by the above discussion. We can easily implement the iterative procedure of finding if there is a dominated vertex and removing it in a few lines in any programming language. I will not include it because it is not very illuminating and also it is better is you write your own to have an independent check.

Using this we find a collapsing sequence of the main component of $\mathrm{Cl}(G_n)$ to a point for $n\leq 142$. For $n=143=11\cdot 13$ we collapse to something nontrivial: the graph induced by $$\{2\cdot 3\cdot 7,\ 2\cdot 3\cdot 11,\ 2\cdot 3\cdot 13,\ 7\cdot 11,\ 7\cdot 13,\ 11\cdot 13\}$$ (Actually we may end up with other numbers, like $2^2\cdot 3\cdot 11$, but only the prime number matter and not their exponents, so we can just as well stick to this). This graph is the complement of the matching on three coprime pairs of numbers, so its clique complex is the 2-dimensional cross-polytope on 6 vertices, or the surface of the octahedron. (This is the smallest that a nontrivial generator of $H_2$ in a flag complex can be).

So, up to a bunch of isolated points, $\mathrm{Cl}(G_{143})$ is homotopy equivalent (collapses, strongly collapses) to $S^2$, so $n=143$ is the first counterexample to your claim.

Side remark: here is a little funny "sanity check". One could ask why not replace this example with a example using smaller primes, namely the cross-polytope induced by $$\{2\cdot 3\cdot 5,\ 2\cdot 3\cdot 7,\ 2\cdot 3\cdot 11,\ 5\cdot 7,\ 5\cdot 11,\ 7\cdot 11\}$$ which would give us a class already in $H_2(\mathrm{Cl}(G_{77}))$. The reason is that $2\cdot 5\cdot 7=70$ is adjacent to all those 6 numbers and therefore cones this sphere off in $\mathrm{Cl}(G_{77})$, trivializing it in homology. On the other hand in $G_{143}$ the analogous attempt with $2\cdot 7\cdot 11=154$ does not work because $154>143$!

  • $\begingroup$ Thank you for this detailed answer! I will accept it as it settles that my claim is unprovable. $\endgroup$ Sep 25 at 16:36

This is too long for a comment, but isn't an answer. It gives a complex that is homotopy equivalent to $\Delta_n$ and appears to me to be easier to think about.

Define $[n]' = \{2,\ldots,n\}$. Since a coprime-free set cannot contain $1$, each vertex $S$ of $\Delta_n$ is contained in $[n]'$. For $k \in [n]'$, let $X_k$ be the full subcomplex of $\Delta_n$ on the vertices $S$ with $k \in S$. The $X_k$ cover $\Delta_n$.

What I claim is that $\Delta_n$ is homotopy equivalent to the nerve of the cover $\{X_k\}_{k \in [n]'}$. For this, it is enough to prove that every intersection of finitely many $X_k$ is either empty or contractible. Consider $I \subset [n]'$, and let $X_I$ be the intersection of the $X_k$ as $k$ ranges over $I$. Thus $X_k$ is the full subcomplex on the vertices $S$ of $\Delta_n$ with $I \subset S$. If this is nonempty, then all the vertices $S$ of $X_I$ intersect, so by the definition of $\Delta_n$ the complex $X_I$ is actually the simplex on its vertices (and in particular is contractible).

Now, if $I$ is not coprime-free then clearly $X_I$ is empty. However, if $I$ is coprime-free then $I$ must be contained in a maximal coprime-free set, so $X_I$ is nonempty and hence contractible.

It follows that the nerve of the $X_I$ is the simplicial complex whose vertices are elements of $[n]' = \{2,\ldots,n\}$ and where a set $I$ of vertices forms a simplex precisely when $I$ is coprime-free. To my mind, this complex seems easier to think about than $\Delta_n$.

  • $\begingroup$ Wow, thanks! I do think this will be easier to work with than the original complex. I think it is okay to keep $1$ in the index set, since by the definition above, the set $\{1\}$ is a maximal coprime-free set (and there are already other isolated vertices for every prime $p$ in $(n/2,n]$, so adding $1$ alongside these primes shouldn't mess things up too much). Besides these primes and $1$, the rest of $\Delta_n$ should be connected. $\endgroup$ Sep 13 at 1:57
  • $\begingroup$ Because there are now far fewer vertices to work with, it almost seems like one can work by induction. There is a simplex consisting of the multiples of every prime, and whenever a new vertex $n$ is added, it becomes a vertex of intersection among all the simplices corresponding to primes that divide it. It feels like this should never cause any empty cycles to appear, but I'm still thinking about how to prove this rigorously. $\endgroup$ Sep 13 at 2:28
  • $\begingroup$ @MarcelK.Goh: When you add a new vertex, the effect is to cone off the link of that vertex. So to prove this inductively, you’ll need to understand the topology of that link. $\endgroup$ Sep 13 at 2:47
  • $\begingroup$ I don’t know if this helps in any way, but since whether a set of vertices determine a face of $X_I$ is defined by a pairwise condition, $X_I$ is what is called a flag simplicial complex (also known as a clique complex). $\endgroup$ Sep 13 at 3:39
  • 1
    $\begingroup$ @HenrikRüping: I just meant that according to the description of the complex in question at the end of Andy Putman's answer, it is clearly flag: a subset of integers being coprime-free is clearly a pairwise condition. (Sorry, I realize I meant "nerve of $X_I$" and not "$X_I$" above.) $\endgroup$ Sep 13 at 12:54

Edit: this is answering the wrong question (coprime subsets rather than coprime-free subsets), but in case it's useful, I will leave it here.

I believe that this simplicial complex should be a simplex, therefore contractible. I should probably have known about Bertrand's postulate before this, but it says that for any $k$, there is a prime number $p$ with $k < p < 2k$. If $n$ is even, let $n=2k$ and find such a $p$. If $n$ is odd, say $n=2k-1$, then find $p$ with $k<p<2k$, and so we have $n/2 < k < p \leq n$.

Once you have such a prime, it is contained in every maximal coprime subset, and so the intersection of all of those sets will be nonempty: every vertex in the simplicial complex is contained in a single simplex.

  • 2
    $\begingroup$ The question is about maximal coprime-free sets, not maximal coprime sets. $\endgroup$ Sep 12 at 21:45
  • $\begingroup$ Oops, yes of course you're right. $\endgroup$ Sep 12 at 22:17
  • $\begingroup$ Thanks for the answer anyway! I have thought about this easier simplicial complex as well, and thought it was fun that Bertrand's postulate plays a role here. $\endgroup$ Sep 13 at 2:00

Following Andy Putman's suggestion that we use the nerve complex, I believe I have found an inductive proof that $H_1(X_n) = 0$ for all $n$. Please point out errors if you see any!

Let $X_n$ denote the nerve complex as described in Andy Putman's answer, though for simplicity's sake we make the vertex set $[n]$. (So $\{1\}$ is always an isolated vertex of $X_n$.) All homologies below are reduced, but I'll write $H_k$ instead of $\tilde H_k$ to be lazy.

A note on notation. $X_n$ here is not the same as $X_k$ from Andy Putman's answer. Apologies for my unfortunate choice of letter. Here $X_n$ is the simplicial complex with $[n]$ as its vertex set, and a face for every set of vertices that is coprime-free.

We'll need this following fact later on, so I'll state it here, but I'll omit its proof. (It's not too difficult.)

Proposition. We have $$H_0(X_1) = 0,\qquad H_0(X_2) = {\bf Z},\qquad\hbox{and}\ H_0(X_3)={\bf Z}^2.$$ For $n\ge 4$, the vertex $1$ is isolated in $X_n$, and there is also an isolated vertex in $X_n$ for each prime in the range $(n/2,n]$. The rest of the vertices are in one connected component. In other words, $H_0(X_n) = {\bf Z}^{C(n)+1}$, where $C(n)$ is the number of primes in the range $(n/2,n]$. ▮

We'll also use the Mayer--Vietoris sequence, which for reduced homology states that

$$\eqalign{ \cdots \to H_s(A)\oplus H_s(B) \to H_s(X)\to H_{s-1}(A\cap B) \to H_{s-1}(A)\oplus H_{s-1}(B)\to\cr \cdots\to H_0(A\cap B) \to H_0(A)\oplus H_0(B) \to H_0(X) \to 0,\cr }$$

whenever $A$ and $B$ are subsimplicial complexes whose interiors cover $X$, and $A\cap B$ is nonempty.

Proof that $H_1(X_n)=0$ for $n\ge 1$. We begin the induction on $n$. For $n=1$ it is clear that $H_k(X_1)$ is $0$ for all $k$.

Now let $n>1$. If $n$ is prime, then $X_n$ is simply the union of $X_{n-1}$ and a new isolated vertex, so $H_0(X_n) = H_0(X_{n-1}) \oplus {\bf Z}$, but all other homologies remain unchanged, so by the induction hypothesis, $H_k(X_n) = 0$ for all $k>1$.

If $n$ is not prime, we let $A$ be the cone of the vertex $n$ in $X_n$, and let $B = X_{n-1}$, considered as a subset of $X_n$. The relevant section of the Mayer Vietoris sequence is

$$\cdots \to H_1(A)\oplus H_1(B) \to H_1(X_n) \to H_0(A\cap B) \to H_0(A)\oplus H_0(B) \to H_0(X_n) \to 0$$

Note that $A$, being the cone of a vertex, is contractible. Applying the proposition above, we have $H_0(X_n) = C(n)+1$ and $H_0(B) = C(n-1)+1$. By the induction hypothesis, $H_1(B) = 0$. Lastly, note that $A\cap B$ is a subset of the big connected component, unless $n/2$ is prime, in which case it also contains the isolated vertex $n/2$, which is isolated in $B$. Hence $$ \hbox{rank}(H_0(A\cap B)) = {\bf 1}_{[n/2\text{ is prime}]}.$$

Putting all these facts into the exact sequence above, we have

$$\cdots \to 0 \to H_1(X_n) \to {\bf Z}^{{\bf 1}_{[n/2\text{ is prime}]}} \to 0 \oplus {\bf Z}^{C(n-1)+1}\to {\bf Z}^{C(n)+1} \to 0$$

But since $n$ is composite, we have $$C(n) = \cases{C(n-1)-1, & if $n/2$ is prime;\cr C(n-1), & otherwise.}$$ Thus we conclude that $H_1(X_n) = 0$. ▮

I feel like this Mayer--Vietoris idea is very close to showing that $H_k(X_n) = 0$ for $k>1$ as well. Since $H_k(A) \oplus H_k(B) = 0$ for all $k>1$, we have $$H_k(X_n) = H_{k-1}(A \cap B)$$ for $k>1$, but it is not immediate to me that the homologies of the intersection are all trivial.

  • $\begingroup$ There is some notational inconsistency with Andy Putman's answer, right? Could you maybe just reintroduce your notation for clarity? $\endgroup$ Sep 13 at 10:15
  • $\begingroup$ Ah, you're right---I picked the worst possible letter for $X_n$. I'm not going to change it now, but I will add a note above. $\endgroup$ Sep 13 at 12:11
  • $\begingroup$ Is it clear that $A\cap B$ is connected if it is contained in the connected subset? $\endgroup$ Sep 13 at 21:10
  • $\begingroup$ Ah, I see, any number having a common divisor with $n$ is connected with some $2p$ for a prime $p$ dividing $n$ (except if $n/2$ is prime, which you discuss), and all those numbers $2p$ are directly connected to each other. $\endgroup$ Sep 13 at 21:24
  • $\begingroup$ @AchimKrause Yes, sorry, to be honest I wasn't super careful there but thanks for formalising it. I hope I'm not barking up the wrong tree with this $A\cap B$ business. But I'll keep trying to prove that $H_{k-1}(A\cap B)$ is $0$ and update if I get anything. $\endgroup$ Sep 13 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.