format: text

text:
# Generalized Kneser Coloring Theorems with Combinatorial Proofs

## 1 Introduction

Kneser’s conjecture \[Kne55\] stated that every coloring of the graph $`\mathrm{KG}^2\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, which has vertex set $`\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, and in which two $`k`$-subsets of an $`n`$-set are connected by an edge if they are disjoint, needs $`n2k+2`$ colors for a proper vertex coloring, if $`n2k4`$.

Kneser’s conjecture was first proved by Lovász \[Lov78\], in one of the first, and most spectacular, applications of an Algebraic Topology result (the Borsuk-Ulam theorem) to a combinatorial problem. An alternative proof was later given by Bárány \[Bár78\], extensions by Schrijver \[Sch78\], Alon, Frankl & Lovász \[AFL86\], Dol’nikov \[Dol’88\], Sarkaria \[Sar90\], and finally by Kriz \[Kri92, Kri00\], whose result implies the theorems by Lovász, Dol’nikov and Alon-Frankl-Lovász. All of these were proved using Algebraic Topology results, namely the Borsuk-Ulam theorem and its extensions. This established them as a part of the “classical core” of Topological Combinatorics \[Bjö95\] \[BMZ01\].

A curious aspect of this is that the basic topological result used in this context, the Borsuk-Ulam theorem, has a variety of “combinatorial proofs,” that is, reductions via simplicial approximation to combinatorial results such as Tucker’s lemma \[Tuc46\], the Ky Fan lemma \[Fan52\], etc.

In 2000, Jiří Matoušek provided two breakthroughs for this situation. *First*, in \[Mat01\] he provided a combinatorial bypass of the Borsuk-Ulam theorem, and thus a combinatorial proof of Kneser’s conjecture. This used only an entirely combinatorial special case of the Tucker lemma. *Secondly*, in \[Mat00\], Matoušek gave a simple and elegant derivation of Kriz’ theorem from Dold’s theorem.

Here, we shall demonstrate the power and extend the scope of Matoušek’s approach, by establishing

* a simple combinatorial proof of Dol’nikov’s theorem (an extension of Matoušek’s proof \[Mat01\] of the Kneser conjecture),
* a new, fairly general hypergraph coloring theorem (which has the theorems by Lovász \[Lov78\], Alon, Frankl & Lovász \[AFL86\], Dol’nikov \[Dol’88\], Sarkaria \[Sar90\], and Kriz \[Kri92, Kri00\] as special cases), together with a combinatorial proof, and
* a combinatorial proof of Schrijver’s theorem (via cyclic oriented matroids).

The proofs that we give are combinatorial (“elementary”) in the sense that they do not rely on topological concepts (such as continuous maps, simplicial approximations, homology) or results. We do, however, phrase some proofs in terms of simplicial complexes and maps, chain complexes, etc.: their use can be eliminated at the price of making the phrasing of the proofs more cumbersome. More importantly, topological knowledge, interpretation and inspiration is “behind” the proofs of this paper: it is neither desirable nor practical to eliminate this background intuition.

## 2 Some Tools and Notation

We use $`[n]`$ to denote the set $`\{1,\mathrm{},n\}`$ of $`n`$ integers, and $`2^N`$ for the set of all subsets of a finite set $`N`$. A *hypergraph* is a set family $`\mathrm{SS}2^N`$; the set $`N`$ is its *ground set*. The hypergraphs that appear in the following will have *no loops*, that is, all their edges $`S\mathrm{SS}`$ have cardinality at least $`2`$. A hypergraph is *$`r`$-uniform* if all of its *edges* $`S\mathrm{SS}`$ have the same cardinality $`r`$. The *restriction* of a hypergraph $`\mathrm{SS}2^N`$ to a subset $`MN`$ of its ground set is the hypergraph $`\mathrm{SS}|_M=\{S\mathrm{SS}:SM\}2^M`$.

In the following $`\text{s}=(s_1,\mathrm{},s_n)`$ will be a vector of *multiplicities*, with $`1s_i<r`$. The sum of multiplicities will be denoted by $`\overline{n}:=s_1+\mathrm{}+s_n`$. Usually s will be *constant*, that is, $`s_1=\mathrm{}=s_n`$, with $`\overline{n}=ns`$. An $`r`$-tuple of subsets $`R_1,\mathrm{},R_r`$ is *s-disjoint* if each $`i[n]`$ is contained in at most $`s_i`$ of the sets $`R_j`$, that is, if $`|\{j[r]:iR_j\}|s_i`$ for all $`i`$. For example, an $`(1,\mathrm{},1)`$-disjoint family of sets is simply disjoint; in this case $`\overline{n}=n`$. An $`(s,\mathrm{},s)`$-disjoint family is what Sarkaria \[Sar90\] calls “$`(s+1)`$-wise disjoint.”

Interesting examples of hypergraphs that appear in the following include $`\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, the collection of all subsets of $`[n]`$ of cardinality $`k`$, and $`\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}}`$, the collection of all *stable $`k`$-subsets*, that is, all subsets that do not contain any two adjacent elements modulo $`n`$. More generally, a subset $`S[n]`$ is *$`t`$-stable* if any two of its elements are at least “distance $`t`$ apart” on the $`n`$-cycle, that is, if $`t|ij|nt`$ for distinct $`i,jS`$. Thus every set $`R[n]`$ is $`1`$-stable, while stable is the same as $`2`$-stable.

A *coloring* of a hypergraph $`\mathrm{SS}2^N`$ with $`m`$ *colors* is a function $`c:N[m]`$ that assigns colors to the ground set so that no edge $`S\mathrm{SS}`$ is monochromatic, that is, every edge contains two elements $`i,jS`$ with $`c(i)c(j)`$. Equivalently, no $`c^1(i)`$ contains a set $`S\mathrm{SS}`$. The *chromatic number* $`\chi (\mathrm{SS})`$ of a hypergraph is the smallest number $`m`$ such that a coloring of $`\mathrm{SS}`$ with $`m`$ colors exists. (Clearly $`\chi (\mathrm{SS})|N|`$ if $`\mathrm{SS}`$ has no loops.)

The *$`r`$-colorability defect* of $`\mathrm{SS}2^N`$ is the number of elements one has to remove from the ground set of $`\mathrm{SS}`$ so that the remaining hypergraph can be colored with $`r`$ colors, that is, the smallest cardinality of a subset $`NM`$ of $`N`$ such that $`\chi (\mathrm{SS}|_M)r`$. (This is Matoušek’s terminology for a concept introduced by Dol’nikov and Kriz.) More generally, the *s-disjoint $`r`$-colorability defect* of $`\mathrm{SS}2^N`$ is
$`\mathrm{cd}_\text{s}^r\mathrm{SS}:=\overline{n}\mathrm{max}\{\underset{j=1}{\overset{r}{}}|R_j|:R_1,\mathrm{},R_rN\text{ }\text{s}\text{-disjoint },SR_j\text{ for }S\mathrm{SS}\},`$
that is, the number of elements that have to be removed from the multiset $`N^\text{s}`$ so that the remaining multiset can be covered by an s-disjoint $`r`$-family of sets (“color classes”) such that none of the sets contains a set from $`\mathrm{SS}`$ (“there is no monochromatic $`\mathrm{SS}`$-set”).

The *$`r`$-th Kneser hypergraph* $`\mathrm{KG}^r\mathrm{SS}`$ of $`\mathrm{SS}`$ is the $`r`$-uniform hypergraph with ground set $`\mathrm{SS}`$ whose edges are formed by the $`r`$-sets of disjoint edges of $`\mathrm{SS}`$. For example, if $`\mathrm{SS}\left(\genfrac{}{}{0pt}{}{N}{2}\right)`$ is a graph, then the edges of $`\mathrm{KG}^r\mathrm{SS}`$ correspond to the matchings in $`\mathrm{SS}`$ of size $`r`$. More generally, the *$`r`$-th s-disjoint Kneser hypergraph* of $`\mathrm{SS}`$, denoted $`\mathrm{KG}_\text{s}^r\mathrm{SS}`$, is the $`r`$-uniform hypergraph with ground set $`\mathrm{SS}`$ whose edges are the s-disjoint $`r`$-sets of edges in $`\mathrm{SS}`$.

We write $`\{+,,0\}^N`$ for the set of all *signed subsets* of $`N`$, that is, the family of all pairs $`(X^+,X^{})`$ of disjoint subsets of $`N`$. For $`N=[n]`$, such subsets can alternatively be encoded by *sign vectors* $`X\{+,,0\}^n`$, where $`X_i=+`$ denotes that $`iX^+`$, while $`X_j=`$ means that $`jX^{}`$. The *positive part* of $`X`$ is $`X^+:=\{i[n]:X_i=+\}`$, and analogously for the *negative part* $`X^{}`$. In the following, we shall switch freely between the different notations for signed sets. For sign vectors, we use the usual partial order from oriented matroid theory \[BSZ<sup>+</sup>99\], which is defined componentwise with $`0+`$ and $`0`$. Thus $`XY`$, that is $`(X^+,X^{})(Y^+,Y^{})`$, holds if and only if $`X^+Y^+`$ and $`X^{}Y^{}`$. We write $`\mathrm{alt}(X)`$ for the length of the longest alternating subsequence of non-zero signs in $`X`$. For example, $`\mathrm{alt}(0+++00+0)=3`$, while $`\mathrm{alt}(0+++0+0)=5`$.

$`Z_p`$ denotes a cyclic group of order $`p`$. We interpret it as the group of $`p`$-th complex roots of unity, $`Z_p=\{1=\omega ^p,\omega ,\mathrm{},\omega ^{p1}\}`$, and so its elements are called *signs*. This will below be used for more general “signed sets,” where elements get signs from $`Z_p`$.

The Borsuk-Ulam theorem asserts that there is no $`Z_2`$-equivariant (continuous) map from $`S^d`$ to $`S^{d1}`$. Dold’s theorem \[Dol83\] is a transformation group extension of this: for every $`Z_p`$-equivariant map $`f:XY`$ between free $`Z_p`$-spaces (compact CW complexes, say) the dimension of $`Y`$ is larger than the connectivity of $`X`$.

The following sketch of proof for Dold’s theorem (following \[Dol83\]) is a “blueprint” for the combinatorial proofs in the following. Assume that $`f:XY`$ is a simplicial or cellular map. If $`\mathrm{connectivity}(X)dim(Y)`$, then one can construct an equivariant map back, $`g:YX`$, whose image is contained in a cone. Since $`gf`$ is an equivariant map, its Lefschetz number $`\mathrm{\Lambda }(gf)`$, which *counts* the simplices/cells that are mapped to themselves (with signs according to dimension and orientation reversal), is divisible by $`p`$. On the other hand, one can restrict $`gf`$ to a cone in $`X`$, and from this derive that $`\mathrm{\Lambda }(gf)=1`$, a contradiction.

For combinatorial proofs, the hard work is usually in the explicit construction of the map back, $`g:YX`$, without use of, or reference to, connectivity information. The Lefschetz number of a chain map on a cone is dealt with by Lemma 6.1.

## 3 Colorings and Colorability Defects

For $`\text{s}=(1,\mathrm{},1)`$, the following coloring of the Kneser hypergraphs is due to Kneser \[Kne55\] in the case $`r=2`$ and to Erdős \[Erd76\] in the general case. It corrects the coloring given in \[Sar90, (3.3)\].

###### Lemma 3.1.

For $`r2`$, $`k2`$, constant $`\text{s}=(s,\mathrm{},s)`$ with $`1s<r`$, and $`snkr`$,

$$\chi \left(\mathrm{KG}_\text{s}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)\right)1+\frac{1}{{\scriptscriptstyle \frac{r1}{s}}}\frac{nsrk+1}{s}.$$

###### Proof.

Set $`P:=\frac{r1}{s}`$ and $`M:=\frac{1}{P}\frac{nsrk+1}{s}`$. With this an explicit coloring is given by

$$S\mathrm{min}\{\frac{1}{P}\mathrm{min}(S),M+1\}.$$

This rule assigns to each $`k`$-set $`S`$ an integer between $`1`$ and $`M+1`$.

If $`\{S_1,\mathrm{},S_r\}`$ is an s-disjoint $`r`$-family, then every minimal element $`\mathrm{min}(S_j)`$ can appear at most $`s`$ times in the family; thus if $`\frac{1}{P}\mathrm{min}(S_j)M`$, then this value is assigned to at most $`Ps`$ sets in an s-disjoint $`r`$-family, where $`Ps=\frac{r1}{s}sr1`$.

On the other hand, if all the $`k`$-sets $`S_j`$ get the color $`M+1`$, then they are contained in the set $`\{PM+1,\mathrm{},n\}`$, of cardinality $`nPM=nP\frac{1}{P}\frac{nsrk+1}{s}nP\frac{1}{P}\frac{nsrk+1}{s}=\frac{rk1}{s}<\frac{rk}{s}`$. But the pigeonhole principle demands that an $`s`$-disjoint $`r`$-family of $`k`$-sets uses at least $`\frac{rk}{s}`$ elements. ∎

The colorings of Lemma 3.1 will be shown to be optimal whenever $`s`$ divides $`r1`$: see Section 7, where we also analyze a case where the coloring is far from optimal.

Lemma 3.1 also provides colorings for the induced sub-hypergraphs $`\mathrm{KG}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{t\text{-}\mathrm{stab}}\mathrm{KG}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, for $`t1`$, so $`\chi \left(\mathrm{KG}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{t\text{-}\mathrm{stab}}\right)\frac{n(k1)r}{r1}`$. This coloring is still optimal for $`r=t=2`$: this is Schrijver’s theorem (see Section 8). For $`r>2`$, see Section 9.

The theorems by Dol’nikov and Kriz and our Theorem 5.1 give lower bounds for chromatic numbers of hypergraphs in terms of $`r`$-colorability defects. These lower bounds are useful only since they are easy to evaluate, e. g. as follows.

###### Lemma 3.2.

Let $`r2`$, $`nk2`$, $`t1`$, and constant $`\text{s}=(s,\mathrm{},s)`$ with $`1s<r`$. If $`ntk`$ (otherwise $`\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{t\text{-}\mathrm{stab}}=\mathrm{}`$), then

$`\mathrm{cd}_\text{s}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{t\text{-}\mathrm{stab}}`$ $`=`$ $`\mathrm{max}\{nstr(k1),0\}.`$
$`\mathrm{cd}_\text{s}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$ $`=`$ $`\mathrm{max}\{nsr(k1),0\},`$
$`\mathrm{cd}_\text{s}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}}`$ $`=`$ $`\mathrm{max}\{ns2r(k1),0\}.`$
###### Proof.

No set $`R[n]`$ of $`t(k1)`$ contiguous elements mod $`n`$ contains a $`t`$-stable $`k`$-set. (Note $`t(k1)<n`$.) Furthermore, there is an s-disjoint packing of (at most $`ns`$ elements from) $`r`$ such contiguous subsets into $`[n]`$: Such a packing can be written down as
$`R_j:=\{(j1)t(k1)+1\text{ mod }n,(j1)t(k1)+2\text{ mod }n,\mathrm{},jt(k1)\text{ mod }n\}.`$
This proves that $`\mathrm{cd}_\text{s}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{t\text{-}\mathrm{stab}}\mathrm{max}\{nstr(k1),0\}`$.

To prove that $`\mathrm{cd}_\text{s}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{t\text{-}\mathrm{stab}}\mathrm{max}\{nstr(k1),0\}`$, it suffices to verify that every set $`R[n]`$ of cardinality $`t(k1)+1`$ contains a $`t`$-stable $`k`$-subset. Take $`R`$, and let $`S[N]R`$ be an arbitrary set of size $`t1`$; this exists since $`ntk`$. Now $`RS`$ has cardinality $`tk`$, and we can partition it into $`t`$ disjoint $`t`$-stable $`k`$-subsets, by taking “every $`t`$-th element” to go into the same $`k`$-subset. At least one of these $`t`$ $`k`$-subsets contains no element from $`S`$, since $`|S|<t`$. ∎

## 4 Dol’nikov’s Theorem

Tucker’s lemma \[Tuc46\] says that if we take a suitable triangulation of an $`n`$-ball, and label its vertices by labels in $`\{\pm 1,\mathrm{},\pm n\}`$ in a way that is antipodal on the boundary, then there is a “complementary edge” whose endpoints receive opposite labels $`\pm i`$. Matoušek’s proof \[Mat01\] of the Kneser conjecture relies on the following combinatorial lemma, which corresponds to Tucker’s lemma applied to (the boundary of) the barycentric subdivision of the $`n`$-cube, $`\mathrm{sd}([1,+1]^n)`$, whose vertex set can be identified with $`\{+,,0\}^n`$.

###### Lemma 4.1 (Octahedral Tucker lemma).

If $`\lambda :\{+,,0\}^n\{0\}^n\{\pm 1,\mathrm{},\pm (n1)\}`$ satisfies $`\lambda (X)=\lambda (X)`$ for all $`X`$, then there are signed sets $`(A^+,A^{})`$ and $`(B^+,B^{})`$ such that $`\lambda (A^+,A^{})=\lambda (B^+,B^{})`$, with $`A^+B^+`$ and $`A^{}B^{}`$.

This lemma has simple combinatorial proofs, e. g. by the method of Freund & Todd \[FT81\]; see \[Mat01\]. (For further combinatorial Tucker lemmas, see Aigner \[Aig01\].)

###### Theorem 4.2 (Dol’nikov \[Dol’88\]).

For every hypergraph $`\mathrm{SS}2^{[n]}`$, the $`2`$-colorability defect is a lower bound for the chromatic number,

$$\chi (\mathrm{KG}^2\mathrm{SS})\mathrm{cd}^2\mathrm{SS}.$$

###### Combinatorial Proof. .

Let $`c:\mathrm{SS}[m]`$ be a proper $`m`$-coloring, and assume that $`\mathrm{cd}^2\mathrm{SS}>m`$, that is, if any subset of $`[n]`$ of size at least $`nm`$ is colored by two colors, then it contains a monochromatic subset from $`\mathrm{SS}`$. Fix an arbitrary linear ordering $``$ on the subsets of $`[n]`$. Then define a map $`\lambda :\{+,,0\}^n\{0\}^n\{\pm 1,\mathrm{},\pm (n1)\}`$, as follows:

1. If $`|A^+|+|A^{}|nm`$, then define $`\lambda (A^+,A^{})`$ as $`\pm c(S)`$, where $`S`$ is the smallest set (according to “$``$”) from $`𝒮`$ that is contained either in $`A^+`$, or in $`A^{}`$. Take the sign to indicate which of $`A^+`$ or $`A^{}`$ you took $`S`$ from. Thus we obtain a value $`\lambda (A^+,A^{})`$ in the set $`\{\pm 1,\pm 2,\mathrm{},\pm m\}`$.
2. If $`|A^+|+|A^{}|nm1`$, then define $`\lambda (A^+,A^{})`$ as $`\pm (m+|A^+|+|A^{}|)`$, where the sign indicates which of $`A^+`$ or $`A^{}`$ is nonempty, and if they both are, then it indicates which is smaller (according to “$``$”). Thus we obtain a value $`\lambda (A^+,A^{})`$ in the set $`\{\pm (m+1),\mathrm{},\pm (n1)\}`$.

This map $`\lambda `$ is antipodal. Thus by the Octahedral Tucker lemma 4.1, there are signed sets $`(A^+,A^{})`$, $`(B^+,B^{})`$ with $`\lambda (A^+,A^{})=\lambda (B^+,B^{})=\pm i`$, where $`A^+B^+`$, $`A^{}B^{}`$, not equality in both cases, and so $`|A^+A^{}|<|B^+B^{}|`$. This is possible only if both signed sets are labeled according to the first case. But then (assume without loss of generality that above we have “$`+i`$”) there are sets $`S,T\mathrm{SS}`$ with $`c(S)=c(T)=i`$ and $`SA^+B^+`$, $`TB^{}`$, where $`B^+`$ and $`B^{}`$ are disjoint: so also $`S`$ and $`T`$ are disjoint, but they get the same color from $`c`$, contradiction. ∎

## 5 A Hypergraph Coloring Theorem

###### Theorem 5.1.

For every hypergraph $`\mathrm{SS}2^{[n]}`$, for $`r2`$, and for multiplicities $`\text{s}=(s_1,\mathrm{},s_n)`$ with $`1s_i<r`$, the s-disjoint $`r`$-colorability defect yields a lower bound for the chromatic number of the associated $`r`$-th s-disjoint Kneser hypergraph,

$$\chi (\mathrm{KG}_\text{s}^r\mathrm{SS})\frac{1}{r1}\mathrm{cd}_\text{s}^r\mathrm{SS}.$$

This theorem, in combination with Lemma 3.2, has many well-known special cases, for constant s:
$`\mathrm{SS}=\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, $`r=2`$, $`\text{s}=(1,\mathrm{},1)`$: Lovász \[Lov78\] (the Kneser conjecture),
$`r=2`$, $`\text{s}=(1,\mathrm{},1)`$: Dol’nikov \[Dol’88\] (Theorem 4.2),
$`\mathrm{SS}=\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, $`\text{s}=(1,\mathrm{},1)`$: Alon, Frankl & Lovász \[AFL86\],
$`\text{s}=(1,\mathrm{},1)`$: Kriz \[Kri92, Kri00\], and
$`\mathrm{SS}=\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$: Sarkaria \[Sar90\].
The generalization to non-constant s is not done for it’s own interest, but since it is needed for the first part of our proof, where we show that one may assume that $`\overline{n}1`$ is divisible by $`r1`$. Under this assumption, and if $`p:=r2`$ is a prime, the second part of the proof derives the theorem from the “$`Z_p`$-Tucker lemma” 5.3 (this is where “the topology is hidden”). The third part reduces the general case of the theorem to the prime case. Finally, in Section 6, the $`Z_p`$-Tucker lemma is proved combinatorially.

###### Reduction of Theorem 5.1 to the case when $`𝒓1`$ divides $`\overline{𝒏}1`$..

For this, we watch what happens if we increase the ground set, by extending $`[n]`$ to $`[n+1]`$, with $`s_{n+1}:=1`$, where $`\mathrm{SS}2^{[n]}2^{[n+1]}`$ is not changed. Since $`\mathrm{SS}`$ is not changed, the Kneser hypergraph $`\mathrm{KG}_\text{s}^r\mathrm{SS}`$ and its chromatic number don’t change, either. On the other hand, with this operation $`\overline{n}1`$ increases by $`1`$, and
$`\mathrm{max}\left\{\underset{j=1}{\overset{r}{}}|R_j|:\text{s}\text{-disjoint }r\text{-family }\{R_1,\mathrm{},R_r\}\text{ with no }SR_j\right\}`$
also increases by $`1`$, since we may extend exactly one of the $`R_j`$s by an extra element $`n+1`$. Thus, in summary, extending the ground set with $`s_{n+1}=1`$ changes neither the chromatic number of the Kneser hypergraph, nor the colorability defect, so validity of the theorem is unchanged. By applying this operation, which increases $`\overline{n}1`$ by $`1`$, at most $`r2`$ times, we get the required divisibility. ∎

We write $`\sigma ^{n1}`$ for the $`(n1)`$-dimensional simplex with vertex set $`[n]`$: this corresponds to the set system of faces $`2^{[n]}`$. Further, $`\sigma _{k1}^{n1}`$ denotes the $`(k1)`$-dimensional skeleton of this simplex, which corresponds to the set system $`\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$.

###### Definition 5.2 (s-disjoint $`𝒑`$-fold joins).

If K is any simplicial complex on the ground set $`[n]`$, then $`\text{K}^p`$ is the join of $`p`$ disjoint copies of K, which is a simplicial complex on the ground set $`Z_p\times [n]`$; this complex has a natural $`Z_p`$-action.

Similarly, the *s-disjoint $`p`$-fold join* $`\text{K}_\text{s}^p`$ is the complex of all subsets $`A`$ of the ground set $`Z_p\times [n]`$, such that the elements with the same “sign” $`\omega ^kZ_p`$ correspond to a simplex in K, and such that every element $`i[n]`$ appears in $`A`$ with at most $`s_i`$ different signs $`\omega ^k`$. This complex again has a natural $`Z_p`$-action. If $`p`$ is prime, and if $`s_i<p`$ for all $`i`$, then the $`Z_p`$-action on $`\text{K}_\text{s}^p`$ is free.

We identify the ground set of $`\text{K}_\text{s}^p`$ with the index set of an $`n\times p`$ matrix — that is, with an $`n\times p`$ *chessboard* in the terminology of \[BLŽV94\]. Thus the faces of $`\text{K}_\text{s}^p`$ may be viewed as $`0/1`$-matrices of size $`n\times p`$, where

* in each column, the rows that contain a $`1`$ correspond to a face of K,
* the $`i`$-th row contains at most $`s_i`$ ones, and
* the $`Z_p`$-action cyclically permutes the columns of the matrix.

The inclusion relation on faces of $`\text{K}_\text{s}^p`$ translates into the componentwise $``$-partial order on $`0/1`$-matrices. We write these matrices column-wise as $`A=(A_1,\mathrm{},A_p)`$, where each $`A_j`$ is the characteristic vector of a face of K.

###### Lemma 5.3 ($`𝒁_𝒑`$-Tucker lemma).

Let $`p2`$ be a prime, $`n1`$, $`\text{s}=(s_1,\mathrm{},s_n)`$ with $`1s_i<p`$, and let

$`\lambda :(\sigma ^{n1})_\text{s}^p\{\mathrm{}\}`$ $``$ $`Z_p\times [m]`$
$`A=(A_1,\mathrm{},A_p)`$ $``$ $`(\lambda _1(A),\lambda _2(A))=\lambda (A)`$
be a $`Z_p`$-equivariant map from non-zero faces/matrices in $`(\sigma ^{n1})_\text{s}^p`$ to signed integers.

If $`m\frac{\overline{n}1}{p1}`$, then there is a chain of faces/matrices

$$A^{(1)}A^{(2)}\mathrm{}A^{(p)}$$

with $`\lambda (A^{(i)})=\omega ^{\pi (i)}\lambda _2(A^{(p)})`$ for some permutation $`\pi \mathrm{\Pi }_p`$, that is, such that the $`A^{(i)}`$ get assigned to the same absolute value $`\lambda _2(A^{(i)})`$, but with $`p`$ distinct signs $`\lambda _1(A^{(i)})Z_p`$.

> Topologically, this $`Z_p`$-Tucker lemma can be derived from Dold’s theorem: If the conclusion does not hold, then $`\lambda `$ defines a $`Z_p`$-equivariant simplicial map
>
> $$\lambda :\mathrm{sd}\left(\sigma ^{n1}\right)_\text{s}^p\left(\sigma ^{m1}\right)_{(p1,\mathrm{},p1)}^p=\left(\sigma _{p2}^{p1}\right)^m$$
>
> from the barycentric subdivision of the complex of all $`0/1`$-matrices of size $`n\times p`$ with at most $`s_i`$ ones in the $`i`$-th row, to the complex of all $`0/1`$-matrices of size $`m\times p`$ with at most $`p1`$ ones per row; this space can be written in two different ways, depending on whether it is read “column-wise” as a deleted join, or “row-wise” as a proper join. On both spaces, the group $`Z_p`$ acts by cyclic permutation of the columns. If $`p`$ is prime and $`s_i<p`$, then the $`Z_p`$-actions are free.
>
> A maximal face of $`\left(\sigma ^{n1}\right)_\text{s}^p`$ has exactly $`s_i`$ ones in the $`i`$-th row, so the complex has dimension $`\overline{n}1`$. We write the complex as $`\sigma _{s_11}^{p1}\mathrm{}\sigma _{s_n1}^{p1}`$ to conclude from the connectivity lemma for joins that the connectivity of this complex (and of its barycentric subdivision) is $`\overline{n}2`$.
>
> The complex $`\left(\sigma _{p2}^{p1}\right)^m`$ is pure of dimension $`m\left(p1\right)1`$; we don’t even need that it is a simplicial sphere. Its $`Z_p`$-action is free since $`p`$ is a prime. Thus we have a contradiction to Dold’s theorem if $`\overline{n}2m\left(p1\right)1`$, that is, if $`m\frac{\overline{n}1}{p1}`$.

###### Proof of Theorem 5.1 for prime $`𝒑`$ and integral $`\frac{\overline{𝒏}1}{𝒓1}`$..

Let $`\chi (\mathrm{KG}_\text{s}^p\mathrm{SS})=K`$, and let $`c:\mathrm{SS}[K]`$ be a coloring such that no $`p`$ s-disjoint sets from $`\mathrm{SS}`$ get the same color. At the same time we assume that $`\mathrm{cd}_\text{s}^p\mathrm{SS}>(p1)K`$, that is, if $`\overline{n}(p1)K`$ elements of the multiset $`[n]^\text{s}`$ are colored by $`p`$ colors (which we take from $`Z_p`$), then some set from $`\mathrm{SS}`$ is monochromatic. We define a labeling

$$\lambda :(\sigma ^{n1})_\text{s}^p\{\mathrm{}\}Z_p\times \left[\frac{\overline{n}1}{p1}\right],$$

using an arbitrary linear ordering $``$ on the subsets of $`[n]`$, as follows:

1. If $`|A_1|+\mathrm{}+|A_p|\overline{n}(p1)K`$, then define $`\lambda _2(A)`$ as $`c(S)`$, where $`S`$ is the smallest set (according to “$``$”) from $`𝒮`$ that is contained in one of the $`A_i`$’s; take the sign $`\lambda _1(A):=\omega ^iZ_p`$ to indicate which $`A_i`$ you took $`S`$ from. Thus we obtain a value $`\lambda (A)=(\lambda _1(A),\lambda _2(A))`$ in the set $`Z_p\times [K]`$.
2. If $`|A_1|+\mathrm{}+|A_p|\overline{n}(p1)K1`$, then define $`\lambda _2(A):=K+\frac{|A_1|+\mathrm{}+|A_p|}{p1}`$, where the sign $`\lambda _1(A):=\omega ^i`$ indicates which of the nonempty sets $`A_i`$ is the smallest one according to “$``$”. In this case we obtain a value $`\lambda _2(A)`$ in the set $`\{K+1,\mathrm{},\frac{\overline{n}1}{p1}\}`$.

This labeling is $`Z_p`$-equivariant. By assumption $`\frac{\overline{n}1}{p1}`$ is an integer, that is, $`\frac{\overline{n}1}{p1}=\frac{\overline{n}1}{p1}`$. Thus we can apply the $`Z_p`$-Tucker lemma 5.3: there is a chain of $`p`$ $`0/1`$-matrices $`A^{(1)}A^{(2)}\mathrm{}A^{(p)}`$ such that $`\lambda (A^{(i)})=(\omega ^{\pi (i)},\lambda _2(A^{(p)}))`$, for some permutation $`\pi \mathrm{\Pi }_p`$.

Since at most $`p1`$ of the matrices $`A^{(i)}`$ can have the same $`\frac{|A_1^{(i)}|+\mathrm{}+|A_p^{(i)}|}{p1}`$, and thus the same “color” $`\lambda _2(A^{(i)})=k_0>K`$ according to the second case, the chain consists of $`p`$ matrices that fall into the first case in the definition of $`\lambda `$. Thus there are sets $`S_i\mathrm{SS}`$ that satisfy $`S_iA_{\pi (i)}^{(i)}A_{\pi (i)}^{(p)}`$, with the same $`c(S_i)=\lambda _2(A^{(i)})=k_0`$. The $`p`$ sets $`S_i`$ are s-disjoint, since they are contained in distinct parts of $`A^{(p)}`$, which is itself s-disjoint, but they all get the same color $`\lambda _2(A^{(i)})`$: contradiction. ∎

###### Reduction of Theorem 5.1 to the case when $`𝒓`$ is prime. .

We proceed by induction on $`r`$, where we assume that the result is true when $`r`$ is prime. Thus let $`\mathrm{SS}2^{[n]}`$, let $`r=r^{}r^{\prime \prime }`$ with $`2r^{},r^{\prime \prime }<r`$, let $`K:=\chi (\mathrm{KG}_\text{s}^r\mathrm{SS})`$, and assume that

$$\mathrm{cd}_\text{s}^r\mathrm{SS}>(r1)K.$$
($``$)
We construct an auxiliary hypergraph $`𝒯2^{[n]}`$ (on the same ground set as $`\mathrm{SS}`$) by

$$𝒯:=\{N[n]:\mathrm{cd}^r^{}\mathrm{SS}|_N>(r^{}1)K\}.$$

Note that for this we use “disjoint” colorability defect, corresponding to $`\text{s}=(1,\mathrm{},1)`$. Using induction and the definition of $`𝒯`$, we now get

$$(r^{}1)\chi (\mathrm{KG}^r^{}\mathrm{SS}|_N)\mathrm{cd}^r^{}\mathrm{SS}|_N>(r^{}1)K,$$

and thus

$$\chi (\mathrm{KG}^r^{}\mathrm{SS}|_N)>K\text{for each }N𝒯\text{.}$$
($`1`$)
*Claim*: $`\mathrm{cd}_\text{s}^{r^{\prime \prime }}(𝒯)>(r^{\prime \prime }1)K`$.
*Proof of the Claim*. Otherwise we could find an s-disjoint $`r^{\prime \prime }`$-family $`N_1,\mathrm{},N_{r^{\prime \prime }}[n]`$ such that no $`N_j`$ contains a set from $`𝒯`$ and such that $`_{j=1}^{r^{\prime \prime }}|N_j|\overline{n}(r^{\prime \prime }1)K`$. In particular, none of the sets $`N_j`$ lies in $`𝒯`$, so by definition of $`𝒯`$ we have $`\mathrm{cd}^r^{}(\mathrm{SS}|_{N_j})(r^{}1)K`$ for all $`j`$. Thus for each $`j`$ we can find $`r^{}`$ disjoint sets $`M_{j1},\mathrm{},M_{jr^{}}N_j`$, such that no $`M_{jk}`$ contains a set from $`\mathrm{SS}`$, with $`_{k=1}^r^{}|M_{jk}||N_j|(r^{}1)K`$.

Taking all the sets $`M_{jk}`$ together, we have $`r^{\prime \prime }r^{}=r`$ subsets of $`[n]`$, none of which contains a set from $`\mathrm{SS}`$, and they are s-disjoint: they form an s-disjoint union of disjoint families. We compute

$`{\displaystyle \underset{j=1}{\overset{r^{\prime \prime }}{}}}{\displaystyle \underset{k=1}{\overset{r^{}}{}}}|M_{jk}|`$ $``$ $`{\displaystyle \underset{j=1}{\overset{r^{\prime \prime }}{}}}|N_j|r^{\prime \prime }(r^{}1)K`$
$``$ $`\overline{n}(r^{\prime \prime }1)Kr^{\prime \prime }(r^{}1)K`$
$`=`$ $`\overline{n}(r1)K,`$
which contradicts ($``$). Thus we have established the Claim.
Using induction, together with the Claim, we get

$$(r^{\prime \prime }1)\chi (\mathrm{KG}_\text{s}^{r^{\prime \prime }}(𝒯))\mathrm{cd}_\text{s}^{r^{\prime \prime }}(𝒯)>(r^{\prime \prime }1)K,$$

and thus

$$\chi (\mathrm{KG}_\text{s}^{r^{\prime \prime }}(𝒯))>K.$$
($`2`$)
Now consider a coloring $`c:\mathrm{SS}[K]`$ of $`\mathrm{KG}_\text{s}^r\mathrm{SS}`$ by $`K`$ colors. By ($`1`$), in every set $`N𝒯`$ we find $`r^{}`$ disjoint sets from $`\mathrm{SS}|_N`$ which from $`c`$ get the same color $`i[K]`$. Using this, we construct a new coloring $`c^{}:𝒯[K]`$ which assigns to $`N𝒯`$ one of the (possibly several) colors $`i`$ which $`c`$ assigns to $`r^{}`$ disjoint sets in $`\mathrm{SS}|_N`$. By ($`2`$), there are $`r^{\prime \prime }`$ sets $`N_j𝒯`$, which are s-disjoint, and which from $`c^{}`$ get the same color $`i_0=c^{}(N_j)`$. Thus we have $`r^{\prime \prime }r^{}=r`$ sets $`M_{jk}\mathrm{SS}`$ with $`M_{jk}N_j`$, also s-disjoint, that get from $`c`$ the same color $`i_0=c(M_{jk})`$. This contradicts the definition of $`K`$ and $`c`$. ∎

## 6 Chain Complexes and the $`𝒁_𝒑`$-Tucker Lemma

For convenience, the following is phrased in terms of chain complexes – however, the argument is entirely combinatorial resp. easy to combinatorialize, since no homology, not even rank considerations, appear. For all the technology needed, Munkres \[Mun84, esp. §§12-13\] is an excellent reference.

We start with a brief review of chain complexes and chain homotopies, also intended to fix notation. Let K be a finite abstract simplicial complex. The *chain complex* $`𝒞(\text{K})`$ of K is

$$𝒞(\text{K}):\mathrm{}C_3\stackrel{_3}{}C_2\stackrel{_2}{}C_1\stackrel{_1}{}C_0\stackrel{_0}{}\{0\}\mathrm{},$$

where $`C_k`$ is the free abelian group of all formal linear combinations of oriented $`k`$-faces of K, with integral coefficients, and the boundary operators $`_k`$ satisfy $`_k_{k+1}=0`$. These are given by $`_k[v_0,\mathrm{},v_k]=_{i=0}^k(1)^i[v_0,\mathrm{},\widehat{v_i},\mathrm{},v_k]`$.

A *chain map* $`\nu :𝒞(\text{K})𝒞(\text{L})`$ is a collection of homomorphisms $`\nu _k:C_k(\text{K})C_k(\text{L})`$ such that $`\nu =\nu `$, that is, $`_k^𝖫\nu _k=\nu _{k1}_k^𝖪`$ for all $`k`$. Every simplicial map $`f`$ induces a chain map $`f_{\mathrm{}}=(f_\mathrm{}k)_{k0}`$. Barycentric subdivision induces a canonical chain map $`\mathrm{sd}`$. Furthermore, any composition of chain maps is a chain map.

A *chain homotopy* $`D`$ is a collection of homomorphisms $`D_k:C_k(\text{K})C_{k+1}(\text{L})`$, for all $`k`$, with no compatibility condition. $`^𝖫D+D^𝖪`$ is then automatically a chain map. If $`D+D=\nu \mu `$, then $`D`$ is a chain homotopy *between $`\nu `$ and $`\mu `$*.

If $`\nu :𝒞(\text{K})𝒞(\text{K})`$ is a chain self-map, then its *Lefschetz number* $`\mathrm{\Lambda }(\nu )`$ is

$$\mathrm{\Lambda }(\nu ):=\underset{k}{}(1)^k\mathrm{trace}(\nu _k).$$

This counts the nonempty simplices that are mapped to themselves according to the parity of their dimension and according to their effect on the orientation. For example, if $`a:\text{K}\text{K}`$ is a constant map to a vertex $`v_0\text{K}`$, then $`\mathrm{\Lambda }(a_{\mathrm{}})=1`$. For $`\mathrm{id}:\text{K}\text{K}`$, $`\mathrm{\Lambda }(\mathrm{id}_{\mathrm{}})`$ is the Euler characteristic of K.

###### Combinatorial proof of the $`𝒁_𝒑`$-Tucker lemma. .

Let us assume that, for some $`m`$, a $`Z_p`$-equivariant coloring $`\lambda `$ exists that does not produce a “fully colored chain of $`p`$ signed faces,” as promised by the $`Z_p`$-Tucker lemma.
(1) In the first half of the proof we will construct, under the assumption $`\overline{n}m(p1)`$, a square of $`Z_p`$-equivariant chain maps

$$\begin{array}{ccc}𝒞(\mathrm{sd}(\sigma ^{n1})_\text{s}^p)& \stackrel{\lambda _{\mathrm{}}}{}& 𝒞((\sigma _{p2}^{p1})^m)\\ \mathrm{sd}& & \mathrm{sd}\\ 𝒞((\sigma ^{n1})_\text{s}^p)& \stackrel{\kappa _{\mathrm{}}}{}& 𝒞(\mathrm{sd}(\sigma _{p2}^{p1})^m).\end{array}$$

Here the vertices of $`\mathrm{sd}(\sigma ^{n1})_\text{s}^p`$ correspond to $`0/1`$-matrices of size $`n\times p`$ with row sums at most $`s_i`$, as discussed above. The faces of the complex correspond to chains of such matrices, with respect to the entrywise $``$-partial order. The $`Z_p`$-action is free for prime $`p`$, if $`1s_i<p`$.

The faces of $`(\sigma _{p2}^{p1})^m`$ are $`0/1`$-matrices of size $`m\times p`$ with no full row of ones: we interpret them as admissible color sets. Again $`Z_p`$ acts cyclically on the columns; this is free for prime $`p`$. The map $`\lambda `$ of the $`Z_p`$-Tucker lemma yields a simplicial map, and thus the chain map $`\lambda _{\mathrm{}}`$ used here. The map is equivariant, by assumption.

The barycentric subdivision operators $`\mathrm{sd}`$, which yield the vertical arrows in the square above, have explicit combinatorial descriptions that we do not have to work out here. They are $`Z_p`$-equivariant.

Finally, $`\kappa :\mathrm{sd}(\sigma _{p2}^{p1})^m(\sigma ^{n1})_\text{s}^p`$ is a simplicial map that we construct orbitwise, as follows. The space to be mapped, $`\mathrm{sd}(\sigma _{p2}^{p1})^m`$, is the barycentric subdivision of a simplicial complex of dimension $`m(p1)1`$, so it is the order complex of a graded poset $`Q_{m(p1)}`$ with $`m(p1)`$ rank levels, $`\mathrm{sd}(\sigma _{p2}^{p1})^m=\mathrm{\Delta }(Q_{m(p1)})`$. The free $`Z_p`$-action on it respects the grading, so it decomposes the rank levels of the poset $`Q_{m(p1)}`$ into disjoint orbits of size $`p`$. The target space is a simplicial complex whose vertex set is identified with the positions in an $`n\times p`$ matrix; its faces are the $`0/1`$-matrices with at most $`s_i`$ ones in the $`i`$-th row, for all $`i`$; the $`Z_p`$-orbits of its vertices are exactly the rows of the matrix. An equivariant simplicial map can now be defined orbitwise, where the image of any element of an orbit determines the images for all others. We construct $`\kappa `$ such that the lowest $`s_1`$ rank levels are mapped to the lowest row of the $`n\times p`$ matrix. The next $`s_2`$ rank levels are mapped to the second lowest row of the matrix, etc. Thus the orbits in the $`\mathrm{}`$-th rank level of $`Q_{m(p1)}`$ are mapped to the row number $`\mathrm{min}\{t:\mathrm{}_{i=1}^ts_i\}`$. (The following figure illustrates this for $`n=4`$, $`p=5`$, $`s_i=2`$.)

This is well-defined if the target matrix has enough rows, that is, if $`m(p1)_{i=1}^ns_i=\overline{n}`$. The definition on the vertices indeed yields a simplicial map into the target space: any chain in $`Q_{m(p1)}`$ contains at most $`s_i`$ elements in the (at most $`s_i`$) adjacent rank levels that are mapped to the $`i`$-th row of the $`n\times p`$ matrix.

In summary, for $`\overline{n}m(p1)`$, we can combine the four $`Z_p`$-equivariant chain maps of the square into a chain self-map

$$\nu =\kappa _{\mathrm{}}\mathrm{sd}\lambda _{\mathrm{}}\mathrm{sd}:𝒞((\sigma ^{n1})_\text{s}^p)𝒞((\sigma ^{n1})_\text{s}^p).$$

Furthermore, the chain maps involved are induced either by simplicial maps, or by barycentric subdivision. Thus all four of them, and thus in particular $`\nu `$, are *augmentation preserving* in the sense that they preserve the sum of the coefficients of the vertices.
(2) In the second half of the proof, we compute the Lefschetz number of $`\nu `$ in two ways. First, the $`Z_p`$-actions are free and the chain maps are $`Z_p`$-equivariant, hence the Lefschetz number of $`\nu `$ satifies

$$\mathrm{\Lambda }(\nu )0(modp).$$

However, we will show that if $`\overline{n}m(p1)+1`$, then $`\nu `$ restricts to an augmentation preserving chain map of the chain complex of a cone, and thus necessarily has

$$\mathrm{\Lambda }(\nu )=1,$$

which yields a contradiction for $`m\frac{\overline{n}1}{p1}`$.

If $`\overline{n}m(p1)+1`$, then we can extend $`\kappa `$ to a simplicial map $`\widehat{\kappa }:\mathrm{\Delta }(Q_{m(p1)}\{\widehat{1}\})(\sigma ^{n1})_\text{s}^p`$, where $`\widehat{1}`$ denotes a new top element that is added to the poset $`Q_{m(p1)}`$. Indeed, just map this new element into the “top row” of the matrix; this gives a well-defined simplicial map (not $`Z_p`$-equivariant, of course). The order complex $`\mathrm{\Delta }(Q_{m(p1)}\{\widehat{1}\})`$ is a cone, and thus so is its image $`\text{K}:=\widehat{\kappa }(\mathrm{\Delta }(Q_{m(p1)}\{\widehat{1}\}))(\sigma ^{n1})_\text{s}^p`$: the image of a cone under a simplicial map is always a cone. We conclude that the image of $`\nu `$ is contained in $`𝒞(\text{K})`$, where the restriction of $`\nu `$ to $`𝒞(\text{K})`$ has the same Lefschetz number as $`\nu `$ itself. The following lemma thus completes the proof. ∎

(Barycentric subdivisions, as used in this proof, do not yield simplicial maps; that’s why the use of chain complexes for this proof is essential. The two barycentric subdivision operations that appear in the square may be taken as a measure of complexity for the proof; in that sense, the proof of Schrijver’s Theorem given below is more complex; it needs $`nd+1`$ barycentric subdivisions.)

###### Lemma 6.1.

Let $`\text{K}=\text{K}^{}v_0`$ be a finite simplicial cone, and let $`\nu :𝒞(\text{K})𝒞(\text{K})`$ be an augmentation preserving chain map. Then $`\mathrm{\Lambda }(\nu )=1`$.

###### Proof.

The following five simple observations combine into a proof.
(1) The identity map $`\mathrm{id}:\text{K}\text{K}`$ and the constant map to the apex $`a:\text{K}\{v_0\}\text{K}`$ are simplicial maps that induce chain maps $`\mathrm{id}_{\mathrm{}},a_{\mathrm{}}:𝒞(\text{K})𝒞(\text{K})`$. These are chain homotopic: An explicit chain homotopy $`D`$, with $`D_k:𝒞_k(\text{K})𝒞_{k+1}(\text{K})`$ for $`k0`$, is given by

$$D:\sigma \{\begin{array}{cc}v_0\sigma \hfill & \text{if }v_0\sigma \text{,}\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$

(2) If $`\nu :𝒞(\text{K})𝒞(\text{K})`$ is any augmentation preserving chain map, then

$$\mathrm{id}_{\mathrm{}}\nu =\nu \mathrm{and}a_{\mathrm{}}\nu =a_{\mathrm{}}.$$

The first equality is clear, the second one is equivalent to being augmentation preserving: $`a_\mathrm{}0`$ maps every $`0`$-chain to “sum of coefficients times $`[v_0]`$,” so we need that $`\nu `$ preserves “sum of coefficients.”
(3) $`\overline{D}:=D\nu `$ is a chain homotopy between $`\nu `$ and $`a_{\mathrm{}}`$. Indeed, using $`\nu =\nu `$ (since $`\nu `$ is a chain map), we get

$$\nu a_{\mathrm{}}=\mathrm{id}_{\mathrm{}}\nu a_{\mathrm{}}\nu =(\mathrm{id}_{\mathrm{}}a_{\mathrm{}})\nu =(D+D)\nu =(D\nu )+(D\nu ).$$

(4) If two chain self-maps are connected by a chain homotopy, then they have the same Lefschetz number. Indeed, let $`\overline{D}`$ be the chain homotopy, then we compute

$`\mathrm{\Lambda }(\overline{D}+\overline{D})`$ $`=`$ $`{\displaystyle \underset{k}{}}(1)^k\left[\mathrm{trace}(_{k+1}\overline{D}_k)+\mathrm{trace}(\overline{D}_{k1}_k)\right]`$
$`=`$ $`{\displaystyle \underset{k}{}}(1)^k\left[\mathrm{trace}(_{k+1}\overline{D}_k)+\mathrm{trace}(_k\overline{D}_{k1})\right],`$
which is a telescope sum that vanishes.
(5) $`\mathrm{\Lambda }(a_{\mathrm{}})=1`$. ∎

## 7 A Special Case

Consider the case of the complete $`k`$-uniform hypergraph $`\mathrm{SS}=\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$, and of constant $`\text{s}=(s,\mathrm{},s)`$, with $`\overline{n}=ns`$. We get a lower bound on the chromatic number of $`\mathrm{KG}_\text{s}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$ for this case by combination of Theorem 5.1 with Lemma 3.2, and an upper bound from Lemma 3.1:

###### Corollary 7.1.

Let $`nk2`$, $`r>s1`$ with $`r(k1)ns`$. Then

$$1+\frac{nsrk+1}{r1}\chi (\mathrm{KG}_{(s,\mathrm{},s)}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right))1+\frac{1}{{\scriptscriptstyle \frac{r1}{s}}}\frac{nsrk+1}{s}.$$

In particular, if $`s`$ divides $`r1`$, then

$$\chi (\mathrm{KG}_{(s,\mathrm{},s)}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right))=1+\frac{nsrk+1}{r1}.$$

This solves the generalized Kneser problem in the case when $`\frac{r1}{s}`$ is an integer, which is the case, in particular, if $`s=1`$ (the Alon-Frankl-Lovász case). However, if $`sr1`$, then — contrary to the claim in \[Sar90, (3.3)\] — we do not have matching lower and upper bounds. The smallest admissible parameters for this effect are $`s=2`$, $`r=4`$, and $`k=2`$, and the following analysis shows that in this case neither the lower bound nor the upper bound of Corollary 7.1 are sharp.

###### Example 7.2.

Let $`n4`$. The generalized Kneser hypergraph $`\mathrm{KG}_{(2,\mathrm{},2)}^4\left(\genfrac{}{}{0pt}{}{[n]}{2}\right)`$ has the vertex set $`E(K_n)`$ (that is, the edges of a complete graph on $`n`$ vertices), while its edges are the $`4`$-tuples of edges of $`K_n`$ that form a subgraph of maximal degree at most $`2`$.

The maximal sets $`E^{}E(K_n)`$ that don’t contain an edge of $`\mathrm{KG}_{(2,\mathrm{},2)}^4\left(\genfrac{}{}{0pt}{}{[n]}{2}\right)`$ are of two types: either they have a vertex of degree at least $`3`$, then they are “a star plus one edge” ($`K_{1,n1}+e`$), or every have no such vertex, then they consist of exactly three disjoint edges. Every $`K`$-coloring can be extended to a covering of $`E(K_n)`$ with $`K`$ such maximal sets. From this one obtains that there are optimal colorings for which the $`i`$-th color class is a $`K_{1,ni}+e`$, and thus derives that the chromatic number of $`\mathrm{KG}_{(2,\mathrm{},2)}^4\left(\genfrac{}{}{0pt}{}{[n]}{2}\right)`$ is

$$\chi (\mathrm{KG}_{(2,\mathrm{},2)}^4\left(\genfrac{}{}{0pt}{}{[n]}{2}\right))=\mathrm{min}\{K:_{i=1}^K(ni+1)\left(\genfrac{}{}{0pt}{}{n}{2}\right)\}=n\sqrt{2n+\frac{1}{4}}\frac{1}{2}.$$

Thus, the chromatic number is roughly $`n\sqrt{2n}`$ for $`r=4`$ and $`s=2`$. This is to be compared with the lower bound of Theorem 5.1, which is $`1+\frac{2n7}{3}\frac{2}{3}n`$, *not very good*, and with the upper bound of Lemma 3.1, which evaluates to $`1+\frac{2n7}{2}=n2`$, *useless*. Thus, in the case where $`r1`$ is not divisible by $`s`$, there is quite a gap between the upper and lower bounds in Corollary 7.1.

## 8 Cyclic Oriented Matroids and Schrijver’s Theorem

###### Theorem 8.1 (Schrijver \[Sch78\]).

For $`n2k>0`$,

$$\chi (\mathrm{KG}^2\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}})=n2k+2.$$

This result is a strengthening of Lovász’ theorem: In the chain

$$n2k+2\chi (\mathrm{KG}^2\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}})\chi (\mathrm{KG}^2\left(\genfrac{}{}{0pt}{}{[n]}{k}\right))n2k+2,$$

the first inequality is what we have to prove now, the second one is trivial (coloring an induced subgraph), and the third one is given by Kneser’s coloring (Lemma 3.1). Schrijver \[Sch78\] indeed verified elegantly that $`\mathrm{KG}^2\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}}`$ is a vertex-critical subgraph of the Kneser graph $`\mathrm{KG}^2\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$. It is not edge-critical in general, as one may observe for $`k=2`$, $`n=3`$, or less trivially for $`k=2`$, $`n=6`$.

Let us also note that Schrijver’s theorem is not implied by Dol’nikov’s, since Lemma 3.2 provides smaller (“worse”) values for $`\mathrm{cd}^2\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}}`$ than for $`\mathrm{cd}^2\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$.

###### Combinatorial proof of Schrijver’s theorem. .

Assume that we have a coloring

$$c:\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}}[n2k+1],$$

and set $`d:=n2k+1`$, so that $`n>d1`$. For $`nd`$ we define

$$\mathrm{\Sigma }^{d1}(n):=\mathrm{\Delta }(\{X\{+,,0\}^n:\mathrm{alt}(X)nd+1\},),$$

the simplicial complex of all chains of sign vectors that have an alternating subsequence with more than $`nd`$ components. It has a free $`Z_2`$-action, given by $`XX`$.

The coloring $`c`$ of $`\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}}`$ now yields a simplicial, $`Z_2`$-equivariant map

$`\widehat{c}:\mathrm{\Sigma }^{d1}(n)`$ $``$ $`\mathrm{\Sigma }^{d2}(d)`$
$`(X^+,X^{})`$ $``$ $`(c(\left(\genfrac{}{}{0pt}{}{X^+}{k}\right)_{\mathrm{stab}}),c(\left(\genfrac{}{}{0pt}{}{X^{}}{k}\right)_{\mathrm{stab}})).`$
If $`c`$ is a correct coloring, then the color sets $`c(\left(\genfrac{}{}{0pt}{}{X^+}{k}\right)_{\mathrm{stab}})`$ and $`c(\left(\genfrac{}{}{0pt}{}{X^{}}{k}\right)_{\mathrm{stab}})`$ are disjoint. Moreover, $`(X^+,X^{})\mathrm{\Sigma }^{d1}(n)`$ has $`\mathrm{alt}(X^+,X^{})n(d1)=2k`$, so both $`\left(\genfrac{}{}{0pt}{}{X^+}{k}\right)`$ and $`\left(\genfrac{}{}{0pt}{}{X^{}}{k}\right)`$ contain at least one stable $`k`$-set, so $`c(\left(\genfrac{}{}{0pt}{}{X^+}{k}\right)_{\mathrm{stab}})`$ and $`c(\left(\genfrac{}{}{0pt}{}{X^{}}{k}\right)_{\mathrm{stab}})`$ cannot be empty, thus $`\mathrm{alt}(c(\left(\genfrac{}{}{0pt}{}{X^+}{k}\right)_{\mathrm{stab}}),c(\left(\genfrac{}{}{0pt}{}{X^{}}{k}\right)_{\mathrm{stab}}))2`$, hence $`\widehat{c}`$ is well-defined for every vertex. Furthermore, any chain of sign vectors is mapped by $`\widehat{c}`$ to a (weak) chain of signed color sets, so we obtain a simplicial map. This map is equivariant.

> Topologically, $`\mathrm{\Sigma }^{d1}\left(n\right)`$ is a simplicial ($`d1`$)-sphere, namely the barycentric subdivision of the topological representation \[FL78\] of the alternating oriented matroid of rank $`d`$ on $`n`$ elements, see \[BL78, Ex. 3.8\] \[BSZ<sup>+</sup>99, Chap. 5/Sect. 9.4\] \[Zie93\]. Similarly, $`\mathrm{\Sigma }^{d2}\left(d\right)`$ is a simplicial ($`d2`$)-sphere. Both spheres have natural antipodal actions, and the map $`\widehat{c}`$ respects these. Thus, the Borsuk-Ulam theorem completes a topological proof at this point, but we keep going on the combinatorial track.

Our next step is a quite trivial simplicial map,

$`\delta :\mathrm{\Sigma }^{d2}(d)`$ $``$ $`\mathrm{\Sigma }^{d2}(d1)`$
$`(Y^+,Y^{})`$ $``$ $`(Y^+\{d\},Y^{}\{d\}),`$
which deletes the last component of each sign vector $`Y`$. This map is well-defined: deleting the last component reduces $`\mathrm{alt}(Y)`$ at most by $`1`$, the operation is compatible with the partial order, and it is $`Z_2`$-equivariant.

Now we use the canonical simplicial embedding maps of $`\mathrm{\Sigma }^{d2}(d1)`$ into a cone

$$\mathrm{cone}\mathrm{\Sigma }^{d2}(d1):=\mathrm{\Sigma }^{d2}(d1)\{v^+\}$$

and then into a suspension

$$\mathrm{susp}\mathrm{\Sigma }^{d2}(d1):=\mathrm{\Sigma }^{d2}(d1)\{v^+,v^{}\}.$$

Thus we have maps

$$\mathrm{\Sigma }^{d2}(d1)\stackrel{i^{}}{}\mathrm{cone}\mathrm{\Sigma }^{d2}(d1)\stackrel{i^{\prime \prime }}{}\mathrm{susp}\mathrm{\Sigma }^{d2}(d1),$$

where the composition $`i:=i^{\prime \prime }i^{}`$ is $`Z_2`$-equivariant (with the natural $`Z_2`$-action on the suspension that interchanges $`v^+`$ and $`v^{}`$).

Finally, we will construct an equivariant chain map

$$\xi :𝒞(\mathrm{susp}\mathrm{\Sigma }^{d2}(d1))𝒞(\mathrm{\Sigma }^{d1}(d)),$$

and sequence of equivariant chain maps

$$\zeta ^{\mathrm{}}:𝒞(\mathrm{\Sigma }^{d1}(\mathrm{}1))𝒞(\mathrm{\Sigma }^{d1}(\mathrm{})),$$

for $`d<\mathrm{}n`$. Once these maps have been constructed, the proof will be complete, since then we have a square of equivariant, augmentation preserving chain maps

$$\begin{array}{ccc}\hfill 𝒞(\mathrm{\Sigma }^{d1}(n))& \stackrel{\widehat{c}_{\mathrm{}}}{}& 𝒞(\mathrm{\Sigma }^{d2}(d))\\ \hfill \zeta ^n& & \delta _{\mathrm{}}\\ \hfill \mathrm{}& & 𝒞(\mathrm{\Sigma }^{d2}(d1))\\ \hfill \zeta ^{d+1}& & i_{\mathrm{}}\\ \hfill 𝒞(\mathrm{\Sigma }^{d1}(d))& \stackrel{\xi }{}& 𝒞(\mathrm{susp}\mathrm{\Sigma }^{d2}(d1)).\end{array}$$

Indeed, as in Section 6 we can then argue that the composition

$$i_{\mathrm{}}\delta _{\mathrm{}}\widehat{c}_{\mathrm{}}\zeta ^n\zeta ^{n1}\mathrm{}\zeta ^{d+1}\xi :𝒞(\mathrm{susp}\mathrm{\Sigma }^{d2}(d1))𝒞(\mathrm{susp}\mathrm{\Sigma }^{d2}(d1))$$

is $`Z_2`$-equivariant, so it has even Lefschetz number, but it also restricts to a cone (the image of $`i_{\mathrm{}}^{}`$ is contained in $`𝒞(\mathrm{cone}\mathrm{\Sigma }^{d2}(d1))`$), and thus its Lefschetz number is $`1`$ (Lemma 6.1).

The chain maps $`\xi `$ and $`\zeta ^{\mathrm{}}`$ (for $`d+1\mathrm{}n`$) can be written down combinatorially, by giving a formula for the image of an arbitrary $`k`$-simplex as a sum of $`k`$-simplices with $`\pm 1`$-coefficients. However, for the exposition we prefer to give a geometric description, from which the combinatorial one can then be derived.

For $`\xi `$, note that $`\mathrm{\Sigma }^{d1}(d)`$ can be interpreted as the boundary complex of $`\mathrm{sd}([1,1]^d)`$, whose “equator” subsphere naturally corresponds to $`\mathrm{\Sigma }^{d2}(d1)\mathrm{sd}([1,1]^{d1})`$.

This suggests a natural subdivision chain map $`𝒞(\mathrm{susp}\mathrm{\Sigma }^{d2}(d1))𝒞(\mathrm{\Sigma }^{d1}(d))`$, as indicated in the figure, where every simplex in $`\mathrm{\Sigma }^{d2}(d1)`$ is mapped “to itself” on the equator, the vertices $`v^\pm `$ are mapped to the north/south poles $`\pm e_d`$, and any $`k`$-simplex $`\sigma v^+`$, say, is mapped to a signed sum of $`k+1`$ $`k`$-simplices, $`k`$ of which triangulate the prism $`\sigma \times [0,1]`$, while the last one is $`+\sigma \times \{1\}e_d`$.

The construction of the chain maps $`\zeta ^{\mathrm{}}:𝒞(\mathrm{\Sigma }^{d1}(\mathrm{}1))𝒞(\mathrm{\Sigma }^{d1}(\mathrm{}))`$ is quite similar: $`\mathrm{\Sigma }^{d1}(\mathrm{}1)`$ is the face poset of the dual cyclic oriented matroid of rank $`d`$ on $`\mathrm{}1`$ elements, as described and analyzed in \[Zie93\].

The following figure illustrates the sign vectors associated to various faces (vertices and edges) of $`\mathrm{\Sigma }^{d1}(\mathrm{}1)`$, for $`\mathrm{}=5`$ and $`d=3`$.

The vertex set of $`\mathrm{\Sigma }^{d1}(\mathrm{}1)`$ is $`\{Y\{+,,0\}^{\mathrm{}}:\mathrm{alt}(Y)\mathrm{}d\}`$. Thus $`\mathrm{\Sigma }^{d1}(\mathrm{}1)`$ decomposes into a *positive hemisphere* $`\mathrm{\Gamma }^+`$, the induced subcomplex given by all vertices with $`\mathrm{alt}(Y,+)>\mathrm{}d`$, and the *negative hemisphere* $`\mathrm{\Gamma }^{}`$ of all vertices with $`\mathrm{alt}(Y,)>\mathrm{}d`$. Every simplex is contained in one of these two “hemispheres,” whose intersection is the *equator* $`\mathrm{\Gamma }^0`$, induced on all vertices $`Y`$ with $`\mathrm{alt}(Y)>\mathrm{}d`$. The equator is naturally isomorphic to $`\mathrm{\Sigma }^{d2}(\mathrm{}1)`$.

Similarly, the simplicial complex $`\mathrm{\Sigma }^{d1}(\mathrm{})`$ decomposes into a positive hemisphere $`\widehat{\mathrm{\Gamma }}^+`$, on the vertices $`X`$ with last component $`X_n\{+,0\}`$, and a negative hemisphere $`\widehat{\mathrm{\Gamma }}^{}`$, on the vertices $`X`$ with last component $`X_n\{,0\}`$, whose intersection is the equator $`\widehat{\mathrm{\Gamma }}^0`$, given by the vertices $`X`$ with $`X_n=0`$, which is again isomorphic to $`\mathrm{\Sigma }^{d2}(\mathrm{}1)`$.

For the construction of $`\zeta ^{\mathrm{}}`$, let $`\sigma `$ be an (oriented) simplex of $`\mathrm{\Sigma }^{d1}(\mathrm{})`$; since we are dealing with the order complex of a poset, all simplices have a natural ordering of their vertices, and thus they have natural orientations. We distinguish three cases.
(1) If $`\sigma `$ lies in the equator $`\mathrm{\Gamma }^0`$, then $`\zeta ^{\mathrm{}}(\sigma )`$ is the corresponding oriented simplex in $`\widehat{\mathrm{\Gamma }}^0`$.
(2) If $`\sigma `$ has more than one vertex that does not lie in the equator, then it is mapped to the corresponding simplex in the positive or negative hemisphere.
(3) Assume that $`\sigma =[Y_0<Y_1<\mathrm{}<Y_k]`$ has a facet in the equator, but does not itself lie in the equator; that is, all its vertices lie in the equator, except for $`Y_0`$, which lies in the interior of the positive hemisphere, say. Then $`\sigma `$ is mapped to a sum of $`k+1`$ oriented $`k`$-simplices in $`\widehat{\mathrm{\Gamma }}^+`$, which again correspond to $`k`$ simplices that triangulate a prism over $`\sigma `$, plus one extra simplex in the interior of the positive hemisphere, and which in the following formal description comes first:

$$\begin{array}{ccc}\hfill [Y_0<Y_1<\mathrm{}<Y_k]& \hfill & \\ & [(Y_0,+)<(Y_1,+)<(Y_2,+)<\hfill & \hfill \mathrm{}<(Y_{k1},+)<(Y_k,+)]\\ \hfill & [(Y_1,0)<(Y_1,+)<(Y_2,+)<\hfill & \hfill \mathrm{}<(Y_{k1},+)<(Y_k,+)]\\ \hfill +& [(Y_1,0)<(Y_2,0)<(Y_2,+)<\hfill & \hfill \mathrm{}<(Y_{k1},+)<(Y_k,+)]\\ & \mathrm{}\mathrm{}\hfill & \hfill \mathrm{}\\ \hfill +(1)^{k1}& [(Y_1,0)<(Y_2,0)<\mathrm{}\hfill & \hfill <(Y_{k1},0)<(Y_{k1},+)<(Y_k,+)]\\ \hfill +(1)^k& [(Y_1,0)<(Y_2,0)<\mathrm{}\hfill & \hfill <(Y_{k1},0)<(Y_{k1},\mathrm{\hspace{0.17em}0})<(Y_k,+)]\end{array}$$

Our figure tries to illustrate this for $`d=3`$ and $`\mathrm{}=5`$. In the left figure, which represents $`\mathrm{\Sigma }^{d1}(\mathrm{}1)=\mathrm{\Sigma }^2(4)`$, the equator arises as a subcomplex of the barycentric subdivision. The right figure, depicting $`\mathrm{\Sigma }^{d1}(\mathrm{})=\mathrm{\Sigma }^2(5)`$, has the equator as a regular subsphere. $`\zeta ^5`$ is a chain map from the left simplicial complex to the right one; it maps the shaded triangle $`[(+00)<(+0+)<(+++)]`$ on the left to the sum of the three triangles shaded on the right:

Now one verifies either geometrically (depending on the geometric realization of the spheres in question as barycentric subdivisions of arrangement spheres), or combinatorially, that these rules satisfy $`\zeta ^{\mathrm{}}\sigma =\zeta ^\mathrm{}1\sigma `$ for all $`\sigma `$, that is, they provide equivariant simplicial chain maps $`\zeta ^{\mathrm{}}`$, as required. ∎

## 9 Stable Kneser Hypergraphs

The stable Kneser hypergraphs $`\mathrm{KG}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{t\text{-}\mathrm{stab}}`$ are induced subgraphs of the usual Kneser hypergraphs $`\mathrm{KG}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)`$. For $`t=r2`$, $`k2`$ and $`nkr`$, it seems that these sub-hypergraphs have the same chromatic numbers as the full hypergraphs,

$$\chi \left(\mathrm{KG}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{r\text{-}\mathrm{stab}}\right)=\frac{n(k1)r}{r1}.$$

Here “$``$” holds by Lemma 3.1. Furthermore, if $`r1`$ divides $`nrk`$, then it appears that $`\mathrm{KG}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{r\text{-}\mathrm{stab}}`$ is vertex-critical, that is, for every $`S\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}}`$,

$$\chi \left(\mathrm{KG}^r\left(\genfrac{}{}{0pt}{}{[n]}{k}\right)_{\mathrm{stab}}\{S\}\right)<\frac{n(k1)r}{r1}.$$

On the other hand, the $`r`$-stable $`r`$-th Kneser hypergraph is not vertex critical in general, for example for $`nrk=1`$ and $`r>2`$.

### Acknowledgements

Thanks to Jirka Matoušek for inspiring preprints, lectures, and discussions.
Thanks to James Munkres for teaching me Algebraic Topology the combinatorial way \[Mun84\], and to Anders Björner for teaching me Combinatorics the topological way \[Bjö95\].
Thanks to Torsten Heldmann for special support in special times.


text:
# On the pulsation mode identification of short-period Galactic Cepheids

## 1 Introduction

Classical Cepheids are an important link between stellar and extragalactic research, and they are widely adopted not only to estimate cosmic distances (Feast 1999; Gieren, Fouqué, & Storm 2000) but also to investigate young stellar populations in external galaxies (Magnier et al. 1997; Macri et al. 2001). Given the extreme usefulness of Cepheids for various astrophysical fields, it is crucial to establish their physical properties with high accuracy. Even though both evolutionary and pulsational properties of Cepheids are based on robust theoretical predictions we are still dealing with several long-standing unsolved problems, such as the universality of both PL and Period-Luminosity-Color (PLC) relations (Bono et al. 1999a; Gieren et al. 1999; Caputo et al. 2000; Groenewegen 2000), and the explanation of the Fourier parameters of the Bump Cepheids (Feuchtinger, Buchler, & Kollath 2000). Moreover, the large photometric databases collected by the microlensing experiments (EROS, MACHO, OGLE) have provided the unique opportunity to investigate the occurrence of exotic objects in the Magellanic Clouds, such as mixed-mode Cepheids. At the same time, the excellent light curve phase coverage and the large sample of Cepheids measured by these projects gave also the opportunity to increase, by more than one order of magnitude, the number of detected first overtone (FO) Cepheids, and to settle (Beaulieu et al. 1995; Welch et al. 1995) the long-standing problem (Pel & Lub 1978; Gieren 1982; Böhm-Vitense 1988) concerning the occurrence of this mode among classical Cepheids.

One of the main results of these investigations was that fundamental (F) and FO Cepheids are distributed, as expected, along two distinct sequences in the magnitude-period plane and present quite different Fourier parameters in certain period ranges. The latter is a crucial finding for two different reasons: i) classical Cepheids, at variance with RR Lyrae stars, cannot be easily split into F and FO variables according to the shape of their light curves. ii) the result strongly supports the evidence originally brought forward by Antonello, Poretti & Reduzzi (1990), based on the light curve Fourier parameters, that the so-called s-Cepheids pulsate in the first overtone. This indication was further strengthened by the evidence that the Fourier parameters of Cepheid radial velocity curves do show a very similar behavior (Kienzle et al. 1999; Moskalik et al. 2001) as their light curve counterparts. However, even though the results disclosed by the massive microlensing data can hardly be questioned, it is worth mentioning that by comparing directly measured distances based on the infrared surface brightness method and distance estimates based on the PL relation, Gieren, Fouqué, & Gomez (1997, 1998; hereinafter GFG97, GFG98) found evidence that at least some short-period, s-Cepheids could rather be F than FO pulsators. The overall scenario is jazzed up by the fact that current Cepheid models do not account for the Fourier parameters of observed light and radial velocity curves (Antonello & Aikawa 1995; Feuchtinger et al. 2000). In view of these facts, it is desirable to have additional quantitative criteria which allow us a firm identification of Cepheid pulsation modes.

Parallel to the mentioned studies, several investigations in the recent literature have been devoted to the comparison between theoretically predicted, and empirical measurements of Galactic Cepheid radii (Laney & Stobie 1995; Bono, Caputo, & Marconi 1998, hereinafter BCM98; Ripepi et al. 1998; Gieren et al. 1999; Nordgren et al. 2000). Most of this work has focused on Cepheids pulsating in the fundamental mode, since these variables are characterized by larger luminosity and radial velocity amplitudes when compared to first overtones which makes it easier to obtain accurate radii for them, particularly when Baade-Wesselink type techniques of radius determination are employed. However, thanks to optical interferometric measurements Nordgren et al. (2000) recently succeeded in determining the mean angular diameter of the nearest Cepheid, $`\alpha `$ UMi (Polaris), from which they were able to estimate its radius. The pulsation behavior of this Cepheid is somewhat peculiar (Kamper & Fernie 1998) but it has been recently classified as a first overtone (Feast & Catchpole 1997). In order to compare the new radius evaluation with both empirical and theoretical PR relations, Nordgren et al. were forced to fundamentalise the period of Polaris, i.e. they added 0.148 to its logarithmic period, since at present we still lack both empirical and theoretical PR relations for first overtones.

The main aim of this Letter is to present a new theoretical PR relation for FO Galactic Cepheids constructed by adopting a fixed chemical composition (Y=0.28, Z=0.02) and several stellar masses ranging from 3.0 to 5.5 $`M_{}`$, and exploit this relation as a new tool for discriminating F and FOs among classical Cepheids. To account for current uncertainties on the predicted luminosity of intermediate-mass Cepheids, the models were constructed by adopting two different ML relations. In §2 we discuss current empirical evidence concerning the mode identification of short-period Cepheids. In §3 we compare the predicted PR relations with observed Cepheid radii. Conclusions about the mode identification from measured radii, and a few comments on the developments of this project close the paper.

## 2 Empirical facts and theoretical predictions

To assess the reliability of the mode identification for classical Cepheids based on their Fourier parameters, we selected four short-period Galactic Cepheids, namely EV Sct, SZ Tau, QZ Nor, and Polaris as test objects. These variables were selected because they have accurate, period-independent individual distance and radius estimates from the infrared surface brightness technique (GFG97,98) and trigonometric parallaxes (Nordgren et al. 2000), respectively, and all of them are generally considered to be FOs based on their short-periods and low-amplitude, nearly sinusoidal light curves. Also, they have accurate spectroscopic and photometric data and Table 1 summarizes their key empirical observables.

We already mentioned that Fourier parameters are widely adopted in the literature to identify the pulsation mode, and therefore we evaluated the Fourier parameters $`R_{21}`$ and $`\varphi _{21}`$ for the selected Cepheids. We estimated these parameters from the observed radial velocity curves, to avoid possible subtle errors affecting the transformation of the theoretical light curves onto the observational plane. Fig. 1 shows from top to bottom the Fourier parameters $`R_{21}`$, $`\varphi _{21}`$, and $`A_1`$ of the four Cepheids together with the Fourier parameters for FO and F Galactic Cepheids by Kienzle et al. (1999) and Moskalik et al. (2001). A glance at the data plotted in this figure shows quite clearly that the Fourier parameters of our sample are indeed typical for Cepheids classified as first overtones.

An independent observable we can adopt to assess whether a star is pulsating in the F or in the FO mode is the stellar radius. As a matter of fact, a star pulsating in the FO is brighter and larger than a star pulsating with the same period in the fundamental mode. Owing to the lack of empirical PR relations for FO Cepheids, we decided to use theoretical radii predicted by nonlinear models to perform this test for our four stars. New PR relations for fundamental mode Cepheids based on nonlinear, convective models were recently provided by BCM98. Even though the idea to compare predicted and empirical radii by artificially decreasing the fundamental period of the current theoretical PR relation is viable, it is quite risky. The reason is twofold: i) the width in temperature of the instability region where the F mode is unstable is on average larger than for the FO. As a consequence, the comparison between fundamentalised variables and truly fundamental PR relations can hardly be adopted to constrain the pulsation mode; ii) recent observational data (EROS, OGLE) on Magellanic Cepheids seem to support the evidence that the slope of the fundamental PL relation changes at very short periods (Bauer et al. 1999; Groenewegen 2000). Therefore the PR relations for F and FO Cepheids could have different slopes.

To avoid these complications we have constructed several new sequences of nonlinear, convective models by adopting a chemical composition typical of solar neighborhood Cepheids, i.e. Y=0.28, Z=0.02. In order to assess on a quantitative basis the difference, if any, between F and FO Cepheid PR relations we adopted the same theoretical framework as adopted by BCM98 and by Bono, Marconi, & Stellingwerf (1999b). The reader interested in the details of the input physics is referred to these papers. Moreover, to account for the difference in the luminosity of intermediate-mass Cepheids predicted by evolutionary models that include (noncanonical) or neglect (canonical) convective core-overshooting during hydrogen burning phases, we adopted, according to BCM98, two different ML relations. The mass/luminosity values adopted for canonical models are: $`M/M_{}`$-log $`L/L_{}`$=3.5-2.51, 4.0-2.72, 4.5-2.90, 5.0-3.97, and 5.5-3.07; while for the noncanonical models are: 3.0-2.52, 4.0-2.97, 4.6-3.19, and 4.75-3.24. In the former set the effective temperature of stable FO models ranges from 5800 to 6500 K, and from 5650 to 6200 K in the latter one. On the basis of these calculations we derived the following canonical and noncanonical PR relations:

$$\mathrm{log}R=1.250(\pm 0.005)+0.755(\pm 0.007)\mathrm{log}P\sigma =0.005$$

$$\mathrm{log}R=1.219(\pm 0.004)+0.737(\pm 0.005)\mathrm{log}P\sigma =0.004$$

where R is the radius (solar units), P the period (d), and $`\sigma `$ is the standard deviation. The pulsation properties of these models will be discussed in a forthcoming paper. The previous linear regressions bring out that the intrinsic dispersion of the FO PR relations is a factor of four smaller than for the F PR relations (0.005 against 0.02) derived by BCM98. Note also that the slopes of FO relations are significantly steeper than the one for F pulsators ($`0.75`$ against $`0.65`$). This difference is caused by two different effects: the FO instability region is both systematically narrower, and bluer than the F one. This means that FOs are, at fixed period, systematically brighter than F pulsators. These findings provide a clear argument that one should use pure F and FO PR relations to constrain the pulsation mode.

Fig. 2 shows the comparison of predicted Fourier parameters for both F (filled triangles) and FO pulsators (open circles) with those of our selected short-period Cepheids. The outcome of the comparison between theory and observations is not very comfortable, and indeed current models seem to suggest that for periods ranging from 2.7 to 4 d both F and FO Cepheids attain similar $`\varphi _{21}`$ values. The velocity amplitude $`A_1`$ and $`R_{21}`$ seem to be less affected by this degeneracy problem, since F pulsators attain values that are, at fixed period, larger than FO ones. The sequences of F and FO pulsators we constructed are too coarse to quantitatively assess the nature of the $`\varphi _{21}`$ jump located at $`P4.2`$ d (see Fig. 1). As a consequence, this finding is only a preliminary hint and more models are necessary to establish the extent of this degeneracy. Nevertheless it seems to be clear that, in the 3-4 d period range, the mode identification based on $`\varphi _{21}`$ values might be quite uncertain.

To shed new light on this problem we decided to investigate whether empirical radius measurements can be adopted to disentangle the mode identification problem. Fig. 3 shows the comparison of theoretical PR relations for both FO (solid and dotted lines) and F (BCM98, dashed and dashed-dotted lines) pulsators with empirical data for the selected objects. The data plotted in this figure disclose several interesting results. At odds with the mode identification based on the Fourier parameters, the comparison between predicted and observed radii yield strong evidence that both EV Sct and QZ Nor are fundamental pulsators. This result seems quite robust for three reasons: i) predicted F and FO radii are, in this period range, substantially different; ii) the empirical radii have quite small uncertainties (both random and systematic). iii) the predicted dependence on metallicity is marginal in this period range. In fact, a decrease in the metal content from Z=0.0.02 to Z=0.008 causes, according to BCM98, a decrease in $`\mathrm{log}R`$ of approximately 0.02 dex. Moreover, FO radii predicted by Bono, Castellani, & Marconi (2000) for Z=0.008 attain, at fixed period, values that are in very good agreement with FO radii at solar metallicity. Thus suggesting that FO radii for $`0.008Z0.02`$ marginally depend on metallicity.

As far as Polaris is concerned, its radius provides evidence that this object is indeed pulsating in the first overtone, as suggested by Feast & Catchpole (1997) on the grounds of the Hipparcos distance estimate, although this conclusion is somewhat weakened by the current observational uncertainties. A detailed analysis of both light and radial velocity curves (Kamper & Fernie 1998) suggest that Polaris is currently undergoing a transient phase during which both pulsation amplitudes and period are rapidly changing. Therefore, further accurate parallax measurements are needed to improve the accuracy of its radius determination. The empirical radius determination for SZ Tau seems to suggest that this object is also pulsating in the first overtone mode. We note here that to avoid any systematic uncertainty in the radius determination of this star due to the known variation of its pulsation period (Szabados 1977), we adopted the radius value based on the J-K solution in GFG97, since J and K data were collected simultaneously and do not present a potential phase misalignment problem as do the noncontemporaneous V and K data.

Summarizing, the comparison between theoretically predicted and measured radii is unveiling that among the selected short-period Cepheids two objects are almost certainly fundamental mode pulsators, in contrast to the mode identification based on their Fourier parameters. The data plotted in Fig. 3 show two further interesting results. In contrast with BCM we find that even at short-periods emprical radii are in very good agreement with theoretical predictions. The fundamental mode PR relations present an intrinsic dispersion of the order of 0.02 dex. Therefore empirical radius measurements of F pulsators can be hardly adopted to assess the accuracy of current ML relations. On the other hand, the intrinsic dispersion of FO PR relations is of the order of only 0.005 dex. This suggests that accurate FO radius determinations can supply useful constraints on both evolutionary and pulsational models.

## 3 Conclusions and final remarks

From the current work we find evidence that a comparison of accurately measured empirical Cepheid radii to theoretical radii for F and FO pulsators is a very useful tool to identify the pulsation modes of classical Cepheids. In fact, theoretical predictions based on nonlinear, convective models seem to suggest that F and FO radii are not affected by any degeneracy for periods ranging from 2.7 to 4 days. This is not true for the Fourier parameter $`\varphi _{21}`$ of radial velocity curves. In fact, two short-period Galactic Cepheids, namely EV Sct, and QZ Nor which on the basis of their Fourier parameters should be classified as FO pulsators are F mode pulsators, as revealed by their radii. The degeneracy between F and FO Fourier parameters is supported by current theoretical predictions. Even though the sequences of models we constructed are relatively coarse in the mass step, the Fourier parameters for fundamental pulsators ($`M=4.5÷5.0M`$) based on theoretical radial velocity curves attain values quite similar to FOs with stellar masses ranging from 4.6 to 5.5 $`M_{}`$. The radial velocity amplitude and $`R_{21}`$ seem to be less affected by this degeneracy.

On the other hand, the comparison between predicted and observed radii strongly suggests that both Polaris and SZ Tau are pulsating in the first overtone, supporting the mode identification suggested by Feast & Catchpole (1997) and by Laney (1997), respectively. In this context it is worth mentioning that our new PR relations for FO Cepheids present an intrinsic dispersion that is approximately a factor of four smaller that that for F PR relations. Moreover and even more importantly, we find that the slope of the former ones is steeper than that for the latter ones, suggesting that the mode identification is more robust if based on pure F and FO PR relations. Unfortunately, the number of short-period Cepheids, particularly s-Cepheids, for which accurate radius measurements are currently available is limited to a handful of objects. It goes without saying that new and accurate multiband, near-infrared photometric data and radial velocity measurements for such objects would be crucial to quantitatively assess the accuracy of the mode identification based on the PR relations. Finally, we remark that FO PR relations are much more sensitive to the ML relation and marginally dependent on the metallicity adopted to construct the pulsation models. Accurate radius measurements for FO Cepheids could therefore supply useful hints on this key relationship predicted by evolutionary models.

We would like to thank P. Moskalik for sending us his Fourier parameters for Galactic Cepheids in advance of publication and an anonymous referee for his/her pertinent suggestions. GB & MM acknowledge financial support by MURST-Cofin 2000, under the project ”Stellar observables of cosmological relevance”. WPG gratefully acknowledges partial financial support by Fondecyt projects 1000330 and 8000002.

| TABLE 1. empirical dataa | | | |  |
| --- | --- | --- | --- | --- |
|  | EV Sct | SZ Tau | QZ Nor | $`\alpha `$ UMi |
| Period (d) | 3.09097 | 3.148727 | 3.78673 | 3.97267 |
| Radius ($`R/R_{}`$) | $`32.5\pm 0.5`$ | $`45.6\pm 4.0`$ | $`38.5\pm 0.5`$ | $`46\pm 3`$ |
| Distance (pc) | $`1635\pm 25`$ | $`692\pm 61`$ | $`1656\pm 8`$ | $`132_8^{+9}`$ |
| $`R_{21}`$ (RV) | $`0.19\pm 0.05`$ | $`0.25\pm 0.03`$ | $`0.16\pm 0.02`$ | $`0.03\pm 0.02`$ |
| $`\varphi _{21}`$ (RV) | $`3.16\pm 0.37`$ | $`3.48\pm 0.13`$ | $`3.70\pm 0.15`$ | $`3.90\pm 0.38`$ |
| $`A_1`$ (RV) | $`7.74\pm 0.27`$ | $`9.72\pm 0.17`$ | $`7.38\pm 0.15`$ | $`0.80\pm 0.08`$ |

a Fourier parameters for EV Sct and SZ Tau were estimated according to data collected by Metzger et al. (1991) and Bersier et al. (1994), while for QZ Nor by Kienzle et al. (1999). Data for $`\alpha `$ UMi come from Hatzes & Cochran (2000, period), Kamper & Fernie (1998, $`A_1`$), Moskalik & Oglozova (2000, $`A_2`$, $`\varphi _{21}`$), and Nordgren et al. (2000, radius and distance).