I’m weak with high-dimensional stuff, so I wanted to translate the statement into one about graphs. We characterize graphs by the following property:
Property P: every j-clique in the graph has an equal number of extensions to (j+1)-cliques. (I.e., an equal number of nodes not in the clique that are connected to every node in the clique.)
(A simplex we translate into a graph has property P: every vertex has an equal number of edges it’s a part of, every edge an equal number of faces it’s a part of, and so on. That is, except for the vertices/edges at the… well, edges of the triangulation. Those have already made problems in Ex4.)
We now prove by induction that, given any k∈N and a graph with property P where the largest cliques are k-cliques, and any coloring c:V→{1,...,k}, the graph has an even number of k-chromatic cliques.
Base case is k=2. The only such graph with property P is the cycle graph Cn. Lemma follows from Ex. 1. (We need that n≥3 here, but that’s fine.)
Inductive step: suppose the claim is true for some k∈N and we have a graph where the largest cliques are k+1 cliques and some coloring c:V→{1,...,k+1}. We prove the step by constructing c starting with the trivial coloring c′ where c′≡1. This coloring has no k+1-chromatic cliques, so in particular, the number of such cliques is even. We can transform c′ into c by repeatedly recoloring nodes, as in Ex4 -- and as in Ex4, the claim follows if we can prove that any step changes the number of k+1-chromatic cliques by an even number.
Let x∈V, and suppose we change the color of x from n to m. Recoloring x can only change the k+1-chromatic-ness of cliques which contain x. Let ω be such a clique. Then ω changes its k+1-chromatic-ness iff (a) precisely one of the nodes in ω−{x} has color n or m, and (b) the remaining k−1 colors of nodes in ω−{x} are the set {1,...,k+1}−{n,m}. In other words, let (V′,E′) be the subgraph consisting of the neighbors of x plus edges and let c− be the coloring obtained by c if we merge colors m and n into one, then the number of cliques that change their k+1-chromaticness in (V,E) is equal to the number of k-chromatic cliques in (V′,E′).
It now follows from the inductive assumption that the number of such cliques is even. We verify that (V′,E′) has property P: let ρ be a j-clique in (V′,E′). Then, the claim follows from the fact that there is a one-to-one correspondence between j+1 cliques extending ρ in (V′,E′) and j+2 cliques extending ρ∪{x} in (V,E). Furthermore, (V′,E′) has at most k-large cliques since every node was connected to x and thus lost one degree.
Given this, one can start with a triangulation where precisely one simplex is k-chromatic (this is pretty straight-forward) and then use the Lemma to repeatedly recolor vertices without changing the number of k-chromatic simplexes. Except, again, for the simplexes at the edges of the triangulation, but those should work similarly… I hope.
Ex 9
I’m weak with high-dimensional stuff, so I wanted to translate the statement into one about graphs. We characterize graphs by the following property:
Property P: every j-clique in the graph has an equal number of extensions to (j+1)-cliques. (I.e., an equal number of nodes not in the clique that are connected to every node in the clique.)
(A simplex we translate into a graph has property P: every vertex has an equal number of edges it’s a part of, every edge an equal number of faces it’s a part of, and so on. That is, except for the vertices/edges at the… well, edges of the triangulation. Those have already made problems in Ex4.)
We now prove by induction that, given any k∈N and a graph with property P where the largest cliques are k-cliques, and any coloring c:V→{1,...,k}, the graph has an even number of k-chromatic cliques.
Base case is k=2. The only such graph with property P is the cycle graph Cn. Lemma follows from Ex. 1. (We need that n≥3 here, but that’s fine.)
Inductive step: suppose the claim is true for some k∈N and we have a graph where the largest cliques are k+1 cliques and some coloring c:V→{1,...,k+1}. We prove the step by constructing c starting with the trivial coloring c′ where c′≡1. This coloring has no k+1-chromatic cliques, so in particular, the number of such cliques is even. We can transform c′ into c by repeatedly recoloring nodes, as in Ex4 -- and as in Ex4, the claim follows if we can prove that any step changes the number of k+1-chromatic cliques by an even number.
Let x∈V, and suppose we change the color of x from n to m. Recoloring x can only change the k+1-chromatic-ness of cliques which contain x. Let ω be such a clique. Then ω changes its k+1-chromatic-ness iff (a) precisely one of the nodes in ω−{x} has color n or m, and (b) the remaining k−1 colors of nodes in ω−{x} are the set {1,...,k+1}−{n,m}. In other words, let (V′,E′) be the subgraph consisting of the neighbors of x plus edges and let c− be the coloring obtained by c if we merge colors m and n into one, then the number of cliques that change their k+1-chromaticness in (V,E) is equal to the number of k-chromatic cliques in (V′,E′).
It now follows from the inductive assumption that the number of such cliques is even. We verify that (V′,E′) has property P: let ρ be a j-clique in (V′,E′). Then, the claim follows from the fact that there is a one-to-one correspondence between j+1 cliques extending ρ in (V′,E′) and j+2 cliques extending ρ∪{x} in (V,E). Furthermore, (V′,E′) has at most k-large cliques since every node was connected to x and thus lost one degree.
Given this, one can start with a triangulation where precisely one simplex is k-chromatic (this is pretty straight-forward) and then use the Lemma to repeatedly recolor vertices without changing the number of k-chromatic simplexes. Except, again, for the simplexes at the edges of the triangulation, but those should work similarly… I hope.