ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 113-126
https://doi.org/10.26493/1855-3974.1414.58b
(Also available at http://amc-journal.eu)
Coloring properties of categorical product of general Kneser hypergraphs*
Roya Abyazi Sani, Meysam Alishahi t
School of Mathematical Sciences, Shahrood University of Technology,
Shahrood, Iran
Ali Taherkhani
Department of Mathematics, Institute for Advanced Studies in Basic Sciences (IASBS),
Zanjan 45137-66731, Iran
Received 26 May 2017, accepted 9 October 2017, published online 6 March 2018
More than 50 years ago Hedetniemi conjectured that the chromatic number of categorical product of two graphs is equal to the minimum of their chromatic numbers. This conjecture has received a considerable attention in recent years. Hedetniemi's conjecture was generalized to hypergraphs by Zhu in 1992. Hajiabolhassan and Meunier, in 2016, introduced the first nontrivial lower bound for the chromatic number of categorical product of general Kneser hypergraphs and using this lower bound, they verified Zhu's conjecture for some families of hypergraphs. In this paper, we shall present some colorful type results for the coloring of categorical product of general Kneser hypergraphs, which generalize the Hajiabolhassan-Meunier result. Also, we present a new lower bound for the chromatic number of categorical product of general Kneser hypergraphs which can be much better than the Hajiabolhassan-Meunier lower bound. Using this lower bound, we enrich the family of hypergraphs satisfying Zhu's conjecture.
Keywords: Categorical product, chromatic number, Hedetniemi's conjecture, general Kneser hypergraph.
Math. Subj. Class.: 05C15
* We thank the two anonymous referees for the carefully reading our paper and for all their useful remarks that helped in improving the presentation of the paper. t Corresponding author.
E-mail address: roya.abyazisani@shahroodut.ac.ir (Roya Abyazi Sani), meysam_alishahi@shahroodut.ac.ir (Meysam Alishahi), ali.taherkhani@iasbs.ac.ir (Ali Taherkhani)
©® This work is licensed under https://creativecommons.org/licenses/by/3.0/
Abstract
114
Ars Math. Contemp. 15 (2018) 113-126
1 Introduction and main results
For two graphs G and H, their categorical product G x H is the graph defined on the vertex set V(G) x V(H) such that two vertices (g, h) and (g', h') are adjacent whenever gg' G E(G) and hh' G E(H). The categorical product is the product involved in the famous long-standing conjecture posed by Hedetniemi which states that the chromatic number of G x H is equal to the minimum of x(G) and x(H). It was shown that the conjecture is true for several families of graphs, but it is wide open in general (see Tardif [21] and Zhu [23]). In spite of being investigated in several articles, there is no substantial progress in solving this conjecture. This conjecture was generalized to the case of hypergraphs by Zhu [22].
A hypergraph H is an ordered pair (V(H), E(H)) where V(H) is a set of vertices, and E(H) is a family of nonempty subsets of V(H). The elements of E(H) are called edges. All hypergraphs considered in the paper have no multiple edges and E(H) is thus a usual set. For a subset S C V(H), the subhypergraph induced by S, denoted by H[S], is a hypergraph with vertex set S and edge set {e G E(H) : e C S}. A hypergraph H is said to be r-uniform if E(H) is a family of r-subsets of V(H). In particular, a 2-uniform hypergraph is called a simple graph. From now on, by a graph we mean a simple graph. An r-uniform hypergraph H is called r-partite if V(H) can be written as a union of r pairwise disjoint subsets (parts) Ui,..., Ur such that each edge of H intersects each part U in one vertex. An r-partite hypergraph is called complete if it contains all possible edges. Also, it is said to be balanced if | U | - | Uj | < 1 for each i, j G [r].
Let H be a hypergraph and r be an integer, where r > 2. For pairwise disjoint subsets Ui,...,Ur C V (H), the hypergraph H[Ui,..., Ur ] is defined to be a subhypergraph of H whose vertex set is ur=iUj and whose edge set consists of all edges of H which are contained in ur=iUj and have exactly one element in each Uj. Note that H[Ui,..., Ur] is an r-uniform r-partite hypergraph.
A proper coloring of a hypergraph H is an assignment of colors to the vertices of H such that there is no monochromatic edge. The chromatic number of a hypergraph H, denoted by x(H), is the smallest number k such that there exists a proper coloring of H with k colors. If there is no such a k, we define the chromatic number to be infinite. Let c be a proper coloring of a complete r-partite hypergraph H with parts Ui,..., Ur. The hypergraph H is colorful (with respect to the coloring c) whenever for each i G [r], the vertices in Uj receive different colors, that is, |c(Uj)| = |Uj| for each i G [r].
Let Hi = (Vi,Ei) and H2 = (V2, E2) be two hypergraphs. For i = 1, 2, the projection nj is defined by nj: (vi, v2) ^ vj. The categorical product of two hypergraphs Hi and H2, defined by Dörfler and Waller in 1980 [10], is the hypergraph Hi x H2 with vertex set Vi x V2 and edge set
{e C Vi x V2 : ni(e) G Ei,nj(e) G E2}.
In 1992, Zhu [22] proposed the following conjecture as a generalization of Hedetniemi's conjecture.
Conjecture 1.1 ([22]). Let Hi = (Vi, Ei) andH2 = (V2, E2) be two hypergraphs. Then x(Hi xH2)=min{x(Hi),x(H2)}.
One can easily derive a proper coloring of Hi x H2 from a proper coloring of Hi or of H2. Therefore the hard part is to show that x(Hi x H2) > min{x(Hi), x(H2)}. Let
R. Abyazi Sani et al.: Coloring properties of categorical product of general Kneser hypergraphs 115
F be a subhypergraph of Hi x H2 with the same vertex set and whose edge set consists of minimal edges of H1 x H2. It is clear that any proper coloring of F is also a proper coloring of H1 x H2. This observation shows that Conjecture 1.1 is a generalization of Hedetniemi's conjecture.
For an integer r and a hypergraph H, the r-colorability defect of H, denoted by cdr (H), is the minimum number of vertices that shall be removed from H so that the hypergraph induced by the remaining vertices admits a proper coloring with r colors.
Let Zr = {w, w2,..., wr } be a multiplicative cyclic group of order r with generator w. For X = (x1,..., xn) € (Zr U {0})n, a sequence xil,..., xim with 1 < i1 < • • • < im < n is called an alternating subsequence of X if xij = 0 for each j € [m] and xij = xij+1 for each j € [m - 1]. The alternation number of X, denoted by alt(X), is the length of the longest alternating subsequence of X. We set 0 = (0,..., 0) and define alt(0) = 0. Also, for an X = (x1,..., xn) € (Zr U {0})n and for e € Zr, define Xe = {i : xi = e} . Note that the r-tuple (Xe)£eZ uniquely determines X and vice versa. Therefore, with abuse of notations, we can write X = (Xe)£eZ . The notation |X| stands for the number of nonzero coordinates of X, i.e., |X| = £ez |Xe|. For two vectors X, Y € (Zr U {0})n, we write X C Y whenever Xe C Ye for each e € Zr .
For a hypergraph H and a bijection a: [n] ^ V(H), the r-alternation number of H with respect to the permutation a is defined as follows:
alt; (H) = max {alt(X) : E(H[a(Xe)]) = 0 for all e € Zr} .
The r-alternation number of H, denoted by altr (H), is equal to min; alt; (H) where the minimum is taken over all bijections a: [n] ^ V(H) (for more details see [3]).
For any hypergraph H = (V(H), E(H)) and positive integer r > 2, the general Kneser hypergraph KGr (H) is an r-uniform hypergraph whose vertex set is E(H) and whose edge set is the set of all r-subsets of E(H) containing r pairwise disjoint edges of H. Note that by this notation the well-known Kneser hypergraph KGr (n, k) is the Kneser hypergraph
KGr ([n], (M)) .For r = 2, we will rather use KG(H) than KGr (H).
Lovisz in 1978, by using tools from algebraic topology, proved that x(KG(n, k)) = n - 2k + 2. His paper showed an inspired and deep application of algebraic topology in combinatorics [15]. As a generalization of this result and to confirm a conjecture of Erdos [11], Alon, Frankl, and Lovisz [5] proved that the chromatic number of KGr (n, k)
is equal to
(k- 1)r
A different kind of generalization of Lovisz's theorem has been
1
obtained by Dol'nikov [9]. He proved that
X(KG(H)) > cd2(H). Then, in 1992, Krfz [13] extended the both latter results by proving that
" cdr (H)"
x(KGr(H)) >
r1
Alishahi and Hajiabolhassan [3] introduced the alternation number as an improvement of colorability defect. Using the Zp-Tucker lemma, they proved that
x(KGr(H)) >
|V(H)| - altr (H) r1
116
Ars Math. Contemp. 15 (2018) 113-126
It can be verified that |V(H)| - altr (H) > cdr (H) and the inequality is often strict [3]. Therefore, the preceding lower bound for chromatic number surpasses the Dol'nikov-Kriz lower bound. Recently, by an innovative use of the Zp-Tucker lemma, Hajiabolhassan and Meunier [12] extended the Alishahi-Hajiabolhassan result (as well as the Dol'nikov-Kriz result) to the categorical product of general Kneser hypergraphs as follows.
Theorem A ([12]). Let Hi,..., Ht be hypergraphs and r be an integer, where r > 2. Then
x(KGr(Hi) x ••• x KGr(Hi)) >
1
r — 1 ie[t]
min(|V (Hi )| — altr (Hi))
Using Theorem A, Hajiabolhassan and Meunier introduced new families of hypergraphs satisfying Zhu's conjecture.
From another point of view, Simonyi and Tardos [20] generalized the Dol'nikov result. Indeed, they proved that for any hypergraph H, if t = cd2(H), then any proper coloring of KG(H) contains a complete bipartite subgraph K^t/2j, \t/2-\ such that all vertices of this subgraph receive different colors and these different colors occur alternating on the two parts of the bipartite graph with respect to their natural order. Then, this result as well as the Dol'nikov-Kriz result was extended to Kneser hypergraphs by Meunier [19] as the following theorem.
Theorem B ([19]). Let H be a hypergraph and p be a prime number. Any proper coloring of KGp(H) contains a colorful, balanced, and complete p-partite subhypergraph F with cdp(H) vertices.
It should be mentioned that, in his paper [19], Meunier also generalized Theorem B and proved that this theorem remains true by replacing cdp(H) with |V(H)| — altp(H). In his proof, Meunier used a Zq-generalization of a theorem by Ky Fan which is stated in terms of chain maps. Later, by introducing an appropriate generalization of the Zp-Tucker lemma, the present second author [2] gave a simple proof for Meunier's result. Moreover, several extensions of Meunier's result can be found in [2]. Another common generalization of the Simonyi-Tardos result and a result by Chen [7, Theorem 7] can be found in [4].
As an improvement of r-colorability defect, the equitable r-colorability defect was introduced in [1]. For a hypergraph H, the equitable r-colorability defect of H, denoted by ecdr (H), is the minimum number of vertices that shall be removed so that the sub-hypergraph induced by the remaining vertices admits a proper equitable r-coloring, i.e., a proper r-coloring in which the sizes of color classes differ by at most one. Clearly, ecdr (H) > cdr (H). As a generalization of Theorem B, it was proved [1] that any proper coloring of KGp (H) contains a colorful, balanced, and complete p-partite subhypergraph F with ecdp(H) vertices. It is not difficult to construct a hypergraph H for which ecdr (H) — cdr (H) is arbitrary large. Surpassing the Dol'nikov-Kriz lower bound, Abyazi Sani and Alishahi [1] proved
x(KGr(H)) >
ecdr (H) r1
It is worth mentioning that they indeed proved a more general result which in particular implies the prior lower bound. To be more specific, they gave a new lower bound for the chromatic number of a generalization of Kneser hypergraphs introduced by Ziegler which
R. Abyazi Sani et al.: Coloring properties of categorical product of general Kneser hypergraphs 117
improves substantially Ziegler's lower bound [24, 25]. Furthermore, they compared their lower bound with the Dol'nikov-Krfz lower bound and the Alishahi-Hajiabolhassan lower bound. In this regard, it was shown that there is a family of hypergraphs H such that for each hypergraph H G H,
x(KGr (H))
ecdr (H)
r — 1
|V (H)|-altr (H) r-1
are both unbounded
while x(KGr(H)) - £drJTi and x(KGr(H)) -for the hypergraphs H in H. Although there are hypergraphs H for which ecdr (H) -(|V(H)| - altr(H)) is arbitrary large, one can construct some hypergraphs H making (|v(h)| - altr (H)) - ecdr (H) arbitrary large, see [1].
As the main results of this paper, motivated by the preceding discussion, we simultaneously extend the results by Abyazi Sani and Alishahi [1] and by Hajiabolhassan and Meunier [12] to the following theorems.
Theorem 1.2. Let H1;..., Ht be hypergraphs. Let p be a prime number and
n = max(minecdp(Hi), min (|V(H,)| - altp(H,)U.
L ¿e [t]	¿e [t]	J
Any proper coloring of KGp(H1) x • • • x KGp(Ht) contains a colorful, balanced, and complete p-partite subhypergraph F with n vertices.
Remark. The question of whether Theorem 1.2 holds for an arbitrary positive integer r instead of a prime number p is an interesting open question.
Let c be the proper coloring with color set [C]. Let F be the colorful, balanced, and complete p-partite subhypergraph whose existence is ensured by Theorem 1.2. Clearly, any color appears in at most p - 1 vertices of F. Consequently, the previous theorem implies
x(KGp(Hi) x ••• x KGp(Ht)) >
which can be extended for an arbitrary r > 2 as follows.
" n "	>
p - 1	
1
p - 1 ¿e[t]
min ecdp(Hi)
Theorem 1.3. Let H1;..., Ht be hypergraphs and r be a positive integer, where r > 2. Then
x(KGr(H1) x • • • x KGr(Ht)) >	minecdr(Hi)
r - 1 ¿e[t]
Example. In what follows, by introducing some hypergraphs, we compare the two lower bounds presented in Theorems A and 1.3. Let n, k, r and a be positive integers, where n > rk, n > a and r > 2. Define H(n, k, a) to be a hypergraph with vertex set [n] and edge set
{B C [n] : |B| = k and B % [a]}. Let KGr (n, k, a) denote the hypergraph KGr (H(n, k, a)). It was proved [1, Proposition 7] that if either a < 2k - 2 or a > rk - 1, then x (KGr(n, k, a)) = Indeed, for a > rk - 1 , it was proved that
X (KGr (H(n, k, a)))
n-max{a,r(k-1)}
ecdr(H(n, k, a))		n - a
r - 1		r - 1
118
Ars Math. Contemp. 15 (2018) 113-126
One should notice that the chromatic number of KGr (H(n, k, a)) was left open for several values of a with 2k — 1 < a < rk — 2. Note that Theorem 1.3 implies the validity of Zhu's conjecture for the family of hypergraphs KGr (n, k, a) provided that a > rk — 1. What is interesting about the hypergraph KGr (H(n, k, a)) is the fact that for r > 4 and a > rk — 1, the value of ecdr(H(n, k, a)) — (n — altr(H(n, k, a))) is unbounded. Thus, by the lower bound presented in Theorem A, we cannot derive that the family of hyper-graphs KGr (n, k, a) satisfies Zhu's conjecture. On the other hand, there is a family H of hypergraphs (see [1]) such that for H G H, the value of (n — altr(H(n, k, a))) — ecdr (H(n, k, a)) is unbounded. Hence, Theorem A and Theorem 1.3 introduce two somehow complementary lower bounds.
2 Proofs
This section is devoted to the proofs of Theorem 1.2 and Theorem 1.3. In the first subsection, we define some necessary tools which will be needed in the rest of the paper. We assume basic knowledge in topological combinatorics. For more details, see [16].
2.1 Notations and tools
A simplicial complex is a pair (V, K) where V is a finite nonempty set and K is a family of nonempty subsets of V such that for each A g K, if 0 = B C A, then B G K. Respectively, the set V and the family K are called vertex set and simplex set of the simplicial complex (V, K). For simplicity of notation and since we can assume that V = U AeK A, with no ambiguity, we can point to a simplicial complex (V, K) just by its simplex set K. The barycentric subdivision of K, denoted by sd K, is a simplicial complex whose vertices are the simplices of K and whose simplices are the chains of simplices of K ordered by inclusion.
Let V and W be two sets. We write V I W for the set V x {1} U W x {2}. Let K and L be two simplicial complexes with vertex sets V and W, respectively. We define K * L, the join of K and L, to be a simplicial complex with vertex set V I W and simplex set {A I B : A G K, B G L}. The join operation is obviously associative: if K, L, M are simplicial complexes, then the simplicial complexes K * (L * M) and (K * L) * M are the same up to a natural relabeling of their vertices. This allows us, if we do not care about the names of the vertices, to use K * L * M for both of K * (L * M) and (K * L) * M. The n-fold join of K, denoted by K*", is a simplicial complex obtained by joining n copies of K. By relabeling the vertices of K*", we assume that K*n has vertex set V(K) x [n] where for each vertex (v, i) g V(K) x [n], the index i indicates that the vertex v is considered as a vertex of the ith copy of K.
For a prime number p, we also consider Zp as a simplicial complex with vertex set Zp and simplex set {{w}, {w2},..., {wp}}. Clearly Zpn is a simplicial complex whose vertex set is Zp x [n] and whose simplices are all nonempty subsets A C Zp x [n] such that for each i g [n], the number of e's for which (e, i) G A is at most one. This observation implies that the simplex set of Zpn can be identified with the set (Zp U {0})n \ {0}, i.e., for each simplex A in Zpn, define A ^ (xi,..., xn) where xj = e if (e, i) G A and xj =0 otherwise. Also, the simplicial complex ap-1 is a simplicial complex with vertex set Zp
and with simplex set consisting of all nonempty proper subsets of Zp. Note that (ap- J is a simplicial complex with vertex set Zp x [n] and 0 = t C Zp x [n] is a simplex of
R. Abyazi Sani et al.: Coloring properties of categorical product of general Kneser hypergraphs 119
/ _ \ tn	r _. \ tn
(ap_2j if and only if |t n (Zp x {i}) | < p -1 foreach i G [n]. It is clear that (0^-2)
is a free simplicial complex where for each e G Zp and (e', i) G Zp x [n], the action is
i - *n
defined by e • (e', i) = (e • e', i). Let t g (opP-2 J be a simplex. For each e G Zp, define
te = {(e, j) : (e, j) G t}. Also, define
¿(t)= p • h(T) + |{e G Zp : |te| > h(T)}|, where h(T) = min£eZp |re|. As stated above, each X G (Zp U {0})n \ {0} represents a
/ _ j\ tn
simplex in Z*vn C i op— j and vice versa. Therefore, speaking about h(X) and ¿(X) is meaningful. Indeed, we have
h(X) = min |Xe| and ¿(X)= p • h(X) + |{e G Zp : |Xe| > h(X)}|.
Note that Zp acts freely on (Zp U {0})n \ {0} by the action e • X = (e • x2,..., e • xn), where e • 0 is defined to be 0 for each e G Zp.
Now, we are ready to present the proof of Theorem 1.2. For simplicity, we first assume that n = minie[t] ecdP(Hj) and then, in Subsection 2.2.2, we sketch the proof for n = minie[t] (|V(Hi)| - altP(Hj)). The proof will follow by applying Dold's theorem on a Zp-equivariant simplicial map
A: sd(Zpn)	Zptm
X	(s(X), v(X))
with n = J2¡= 1 |V(Hi)| and m as small as possible. Indeed, Dold's theorem implies that if there is such a map A, then m > n. It is worth noting that the idea of using Dold's theorem or some of it specializations such as the Zp-Tucker lemma has been used in several articles initiated by a fascinating paper of Matousek [17]. For instance, see [1, 4, 6, 7, 12, 18, 19, 24]. Usually, the most challenging task in using Dold's theorem is how to define the map A, especially the sign part s(X). In what follows, we show that some of the techniques used in these works can be fruitfully mixed and extended to get a common generalization. However, some additional tricks are introduced to make these techniques work together. In particular, in our approach, we use a different way to define the sign map s(X) and also we appropriately modify the value function v(X). Being more specific, to define the map A, we partition sd(Zpn) = (Zp U {0})n \ {0} into two subsets S2 and £2, where S2 is the set of vectors X g sd(Zpn) such that for each j g [t] and e G Zp,
the set {i G [nj]: xi+y>j-1 n ,, = e} contains some edge of Hj = ([nj], Ej), and hence
j = 1 j
Xe somehow contains a vertex of the hypergraph KGP(H2) x • • • x KGP(Ht). For each X G £2, we define v(X) g {a + 1,..., m}, where a = n - n + p -1, according to a given proper coloring of KGP(H2) x • • • x KGP(Ht) and we define s(X) G Zp with the help of an auxiliary sign map s3(-). Defining A(X) for the remaining vectors X, i.e., X G £2, is even more difficult and technical which will be done by the use of two auxiliary sign maps s2 (-) and s2 (-). A larger value of n will allow us to make a smaller and consequently m smaller, giving a better bound in the end.
2.2 Proof of Theorem 1.2
When n = 0, there is nothing to prove. If 1 < n < p - 1, then consider pairwise disjoint sets Ui,...,Up C V(KGP(Hi) x • • • x KGP(Ht)) such that |Ui| = 1 for i < n and
120
Ars Math. Contemp. 15 (2018) 113-126
\Ui \ = 0 otherwise. Note that for at least one i, we have U = 0. In view of the definitions, the subhypergraph KGp(Hi) x • • • x KGp(Ht)[U^..., Up] which has no edge is clearly balanced and p-partite. Furthermore, for any proper coloring of KGp(H1)x^ • xKGp(Ht), this subhypergraph is colorful which is desired. Henceforth, we assume that n > p.
For simplicity of notation, assume that H1 = ([n1], E1),..., Ht = ([nt], Et) and moreover, set n = J2¿=1 ni. For each X = (x1,..., xn) G (Zp U {0})n \ {0}, let X(1) G (Zp U {0})ni t»e the first n1 coordinates of X, X(2) G (Zp U {0})n be the next n2 coordinates of X, and so on, up to X(t) G (Zp U {0})nt be the last nt coordinates of X. Also, for each j g [t], define Aj (X) to be the set of signs e G Zp such that X(j)e contains at least one edge of Hj. We remind that X(j)e is the set of all i G [nj] such that j-1 n = e. Define
E1 = {X G (Zp U {0})n \ {0} : Aj (X) = Zp for at least one j G [t]|
and
£2 = {X G (Zp U {0})n \ {0} : Aj (X) = Zp for all j G [t]}.
Note that for an X g (Zp U{0})n\{0} and for each j g [t],if we set S = U£eZp X (j )e, then X (j) = (X (j)e) Z can be thought of as a partition of vertices of Hj [S] into p color classes, i.e., the vertices in X(j)e receive the color e. Intuitively, the value h(X(j)) is then the size of the smallest color class, ¿(X(j)) is the maximum possible number of vertices colored by an equitable sub-coloring (not necessarily proper), while Aj (X) is the set of colors e G Zp for which there is an e-monochromatic edge in Hj [S].
2.2.1 Proof of Theorem 1.2 when n = minie[t] ecdp(Hi)
In what follows, we first define two sign maps s1 and s2 playing important roles in the proof. These two maps will help us to define s(X) for each X g E1.
Definition of si(-). Let X g E1 be a vector such that Aj(X) g {0, Zp} for each j g [t]. Define
fX(j)	if Aj (X) = Zp,
Bj(X) = I {£^X(jr = 0} if Aj (X) = 0 and h(X(j)) = 0, iXj)	if Aj (X) = 0 and h(X (j)) > 0,
where X(j) G (Zp U {0})nj \ {0} and for each e G Zp, we have
Xj)e = |x(j)£ if \X(j)e\ = h(X(j)), 0 otherwise.
Note that Bj (X) may be of two different natures: a vector in (Zp U{0})nj \{0} or a proper subset of Zp. Now, set B(X) = fB1(X),..., Bt(X)) and
L1 = { B(X) : X G E1 and Aj (X) G {0,Zp} for all j G [t^.
Note that L1 is a subset of
(fZp U{0})ni U f2Zp \ {Zp})) x^^^x
(fZp U {0})nt U f2Zp \ {Zp})) \ ({0, 0} x • • • x {0,0}).
R. Abyazi Sani et al.: Coloring properties of categorical product of general Kneser hypergraphs 121
For an e G Zp and a vector B = (Bi,..., Bt) G Li, we define
£ • B = (e • B1,...,e • Bt),
where
„ j (e • xi,...,e • i„,) if Bi = (xi,...,x„i) G (Zp U{0})n \{0}, £ • Bi — < ,	.
i [{e • z : z G Bj if Bi C Zp.
With respect to this action, one can simply check that L1 is closed and free and furthermore, B(-) is a Zp-equivariant map, i.e., B(e • X) = e • B(X) for each e G Zp and for each X g E i such that Aj (X) g {0,Zp} for each j g [t].Now,let si: Li ^ Zp be an arbitrary Zp-equivariant map. Note that such a map can be defined by choosing one representative in each orbit and defining the value of the map arbitrarily on this representative.
Definition of s2(-). Clearly Zp acts freely on
L2 = 2Zp x • • • x 2Zp \ ({0, Zp} x • • • x {0, Zp})
by the action e • (Ci,..., Ct) = (e • Ci,..., e • Ct), where e • Ci = {e • z : z G Ci}. Similar to the definition of si(-), let s2: L2 ^ Zp be an arbitrary Zp-equivariant map.
Set a = n - mini£[t] ecdp(Hi) + p — 1. Note that since mini£[t] ecdp(Hi) > p, we have a < n. For every j G [t], define the function Vj : (Zp U {0})n \ {0} ^ N as follows:
f|X (j)|	if Aj (X )= Zp,
Vj(X) = 1 A(X )| + maX {¿(Z) : Z C X (j) and	, if Aj (X) = Zp.
[	E(Hj [Ze]) = 0 for all e G Zp j	j ( )= p
We remind the reader that |X(j)| denotes the number of nonzero coordinates in X(j). Now, let v(X) = Ej=i Vj(X).
Defining the map Ai. Set a = n — mineeZp ecdp(Hi) + p — 1. Define the map
Ai : Ei —> Zp x {1,..., a} X —^ (s(X), v(X)).
For defining s(X), we consider the following different cases.
•	If for each j g [t], we have Aj (X) g {0, Zp}, then s(X) = si (B(X)).
•	If for some j G [t], we have Aj (X) G {0,Zp}, then s(X) = S2(Ai(X),..., At(X)).
Lemma 2.1. The map Ai is a Zp-equivariant map with no X, Y G Ei such that X C Y, v(X) = v(Y) and s(X) = s(Y).
Proof. Clearly, Ai is a Zp-equivariant map since the two maps si( —) and s2(—) are Zp-equivariant and v(e • X) = v(X) for all e G Zp. For a contradiction, suppose that X and Y are two vectors in Ei such that X C Y, v(X) = v(Y) and s(X) = s(Y). Since X C Y, we have X(j) C Y(j) and consequently, Aj (X) C Aj (Y) for each j g [t]. Additionally, X(j) C Y(j) implies that
{¿(Z) : Z C X(j) and E(Hj[Ze]) = 0 Ve G Zp} C
{¿(Z) : Z C Y(j) and E(Hj[Ze]) = 0 Ve G Zp}.
122
Ars Math. Contemp. 15 (2018) 113-126
Thus, Vj(X) < Vj(Y) for each j e [t]. Therefore, the equality v(X) = v(Y) implies Vj (X) = Vj(Y). This equality together with above discussion results in Aj(X) = Aj(Y) for each j e [t]. This observation leads us to the following cases.
(I) Aj(X) e {0, Zp} for each j. Therefore, s(X) = si (B(X)). Since Aj(X) = Aj(Y) for each j, we have s(Y) = s1 (B(Y)), Consequently, the fact that s(X) = s(Y) implies that B(X) = B(Y). Now, let j0 be the smallest integer for which Bj0 (X) = Bj0 (Y). We consider the following different cases.
(1)	When Aj0 (X) = Aj0 (Y) = Zp. In view of the definition of Bj0 (-), we have X(j0) C Y(j0). Therefore, the definition of vj0 implies that vj0 (X) < vj0 (Y), which is not possible.
(2)	When Aj0 (X) = Aj0 (Y) = 0. Using j (X) = j (Y), we have ¿(X(jo)) = ¿(Y(j0)). Therefore,
p ■ h(X(jo)) + |{e : |X(jo)e| > h(X(jo))}| =
j0 j0
which clearly implies that h(X(j0)) = h(Y(j0)) and
|{e : |X(jo)e| > h(X(jo))}| = |{e : |Y(jo)£| > h(Y(jo))}|. The fact that X (j0) C Y (j0) results in
P ■ h(Y(jo)) + |{e : |Y(jo)e| > h(Y(jo))}|,
{£ : |X(jo)e| > h(X(jo))} = {£ : |Y(jo)£| > h(Y(jo))}.
Therefore, in view of the definition of B(-), we have Bj0 (X) = Bj0(Y) which is a contradiction.
(II) Aj (X) e {0, Zp} for some j e [t]. Since s(X) = s(Y), we have
s2(Ai(X),..., At(X)) = s2(Ai(Y),..., At(Y)).
Consequently, we must have (Ai(X),..., At(X)) = (Ai(Y),..., At(Y)). Therefore, there is at least one j for which Aj (X) = Aj (Y) which is not possible. □
In what follows, we will define some new notations needed in the rest of proof. Let c be a proper coloring of KGp(Hi) x ■ ■ ■ x KGp(Ht) with color set [C]. For each X e S2 and each e e Zp, define
E e(X) = j(ei,..., et) e Ei x ■ ■ ■ x E : ej C X (j)e for each j e [t^.
Note that, in view of the definition of S2, for each e e Zp, we have Ee(X) = 0. Now, set tx to be defined as follows:
tx = |(e, c(u)) : e e Zp and u = (ei,..., et) e Ee
Note that if we choose u£ e Ee(X) for each e e Zp, then {u£ : e e Zp} is an edge of KGp(Hi) x ■ ■ ■ x KGp(Ht). Consequently, since c is a proper coloring of KGp(Hi) x ■ ■ ■ x KGp(Ht), for each i e [C], there is at least one e e Zp for which (e, i) e tx. This
observation indicates that tx is a simplex of (^-2) . Furthermore, since Ee(X) = 0 for each e e Zp, we have ¿(tx ) > p.
R. Abyazi Sani et al.: Coloring properties of categorical product of general Kneser hypergraphs 123
Definition of s3(-). For a positive integer b e [C], let Ub be the set consisting of all simplices t e (^-2) such that |te| e {0, b} for each e e Zp. Define U = ug^U^.
Choose an arbitrary Zp-equivariant map s3 : U ^ Zp. Also, for each t e (^-2) with h = h(T) = min |te|, define
r = U t^.
e : |t e | = h
Note that r is a sub-simplex of t which is in U. Therefore, s3(r) is defined. Defining the map A2. Define the map
A2 : £2 —> Zp x {a + 1, ...,a - p + 1 + maxxes2 ¿(tx )} X	(s(X ),v (X)),
where s(X) = s3(TX) and v(X) = a -p + 1 + ¿(tx).
Lemma 2.2. The map A2 is a Zp-equivariant map with no X, Y e £2 such that X C Y,
v(X) = v(Y) and s(X) = s(Y).
Proof. Obviously, A2 is a Zp-equivariant map. Suppose for a contradiction that X and Y are two vectors in £2 such that X C Y, v(X) = v(Y) and s(X) = s(Y). In view of the definition of A2, we must have ¿(tx) = ¿(ty). Using the definition of ¿( —), it implies that h(TX) = h(TY). From the last equality and tx C ty, we deduce that TX = TY and consequently, s(X) = s3(TX) = s3(TY) = s(Y), which is a contradiction.	□
In the following lemma, we show that how the existence of an X with large ¿(X) completes the proof.
Lemma 2.3. If there is an X e £2 with ¿(tx ) > q, then KGp(Hi) x • • • x KGp(Ht) contains a colorful, balanced, and complete p-partite subhypergraph with q vertices.
Proof. Let X e £2 be a vector for which we have ¿(tx ) > q. Let t C tx be a subsimplex such that ¿(t) = |t| = q. For each i e [p], set Si = {j e [C] : (wJ, j) e t}. First note that |_ p J < |Si | < [ p ] for each i e [p]. Moreover, it is clear that J]P=2 |Si | = q. For each i e [p] and s e Si, in view of the definitions of t (X) and Si, there is a
ef,i,..., ei,t)
vertex ui,s = (ef 2,..., ef t) of KGp(H2) x • • • x KGp(Ht) such that c(ui,s) = s and
e| j C X(j)w for each j e [t]. Now, for i e [p], set Ui = {ui,s : s e Si}. Clearly, kGp(Hi) x • • • x KGp(Ht)[Ui,..., Up] is the desired subhypergraph.	□
Completing the proof of Theorem 1.2 when n = minie[t] ecdp(Hi). For completing the proof of Theorem 1.2, we need to use a generalization of the Borsuk-Ulam theorem by Dold, see [8, 16]. Indeed, Dold's theorem implies that if there is a Zp-equivariant simplicial map from a simplicial Zp-complex K2 to a free simplicial Zp-complex K2, then the dimension of K2 should be strictly larger than the connectivity of K2. For simplicity of notation, let
m = a — p +1+ max ¿(t(X)).
X6E2
124
Ars Math. Contemp. 15 (2018) 113-126
In view of Lemma 2.3, it suffices to show that
max ¿(tx) > minecdp(?{A
xeS2	ie[t]
To this end, define A: (Zp U {0})n \ {0} ^ Zp x [m] such that for each X G (Zp U {0})n \ {0}, if X G Ei, then A(X) = Ai(X), otherwise A(X) = A2(X). In view of Lemma 2.1 and Lemma 2.2, A(-) is a Zp-equivariant simplicial map from sd(Zpn) to Zpm. Consequently, according to Dold's theorem, the dimension of Zpm should be strictly larger than the connectivity of sd(Zpn), that is m - 1 > n - 2 as desired.	□
2.2.2 Proof of Theorem 1.2 when n = minie[t](|V (Hi) | - altp(Hi))
In this subsection, we sketch the proof of Theorem 1.2 for the n = mini£[t](|V(H)| -altp(Hj)) case. To this end, we need to slightly modify the proof of Theorem 1.2 in the case of n = minie[t] ecdp(Hi) as follows.
•	Throughout Subsection 2.2.1, replace mini£[t] ecdp(Hi) by mini£[t](|V(Hi)| -altp(Hi)).
•	Use alt(-) instead of function ¿(-) to define each Vj (X).
•	For any X such that Aj(X) G {0, Zp} for each j G [t], in the definition of A1(X), set s(X) to be the first nonzero entry of X.
With the same approach as in Subsection 2.2.1, it is straightforward to check that Lemmas 2.1, 2.2, and 2.3 are still valid with the preceding modifications. Therefore, again applying Dold's theorem leads us to the desired assertion.
2.3 Proof of Theorem 1.3
To prove Theorem 1.3, we reduce this theorem to the prime case of r which is known to be true by the discussion right after Theorem 1.2. One should notice that this reduction is a refinement of the well-known reduction originally due to Kriz [14], which has been used in some other papers as well, for instance see [3, 12, 24, 25]. In what follows, we use a similar approach as in [12].
Lemma 2.4. Let r' and r" be two positive integers. If Theorem 1.3 holds for both r' and r", then it holds also for r = r'r''.
For two positive integers s and C and a hypergraph H, define a new hypergraph Tn,c,s as follows:
V(Tn,c,s) = v (H)
E(Tu,c,s) = {A C V(H) : ecds(H[A]) > (s - 1)c}.
The following lemma can be proved with a similar approach as in [12, Lemma 3].
Lemma 2.5. Let r and s be two positive integers. Then
ecdrs(H) < r(s - 1)C + ecdr(Tn,c,s).
Proof of Lemma 2.4. Using Lemma 2.5 instead of Lemma 3 in the proof of Lemma 1 in [12] leads us to the proof.	□
R. Abyazi Sani et al.: Coloring properties of categorical product of general Kneser hypergraphs 125
References
[1]	R. Abyazi Sani and M. Alishahi, A new lower bound for the chromatic number of general Kneser hypergraphs, 2017, arXiv:1704.07052v1 [math.CO].
[2]	M. Alishahi, Colorful subhypergraphs in uniform hypergraphs, Electron. J. Combin. 24 (2017), #P1.23, http://www.combinatorics.org/ojs/index.php/eljc/ article/view/v2 4i1p2 3.
[3]	M. Alishahi and H. Hajiabolhassan, On the chromatic number of general Kneser hypergraphs, J. Comb. Theory Ser. B 115 (2015), 186-209, doi:10.1016/j.jctb.2015.05.010.
[4]	M. Alishahi, H. Hajiabolhassan and F. Meunier, Strengthening topological colorful results for graphs, European J. Combin. 64 (2017), 27-44, doi:10.1016/j.ejc.2017.03.011.
[5]	N. Alon, P. Frankl and L. Loväsz, The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc. 298 (1986), 359-370, doi:10.2307/2000624.
[6]	G. J. Chang, D. D.-F. Liu and X. Zhu, A short proof for Chen's alternative Kneser coloring lemma, J. Comb. Theory Ser. A 120 (2013), 159-163, doi:10.1016/j.jcta.2012.07.009.
[7]	P.-A. Chen, A new coloring theorem of Kneser graphs, J. Comb. Theory Ser. A 118 (2011), 1062-1071, doi:10.1016/j.jcta.2010.08.008.
[8]	A. Dold, Simple proofs of some Borsuk-Ulam results, in: H. R. Miller and S. B. Priddy (eds.), Proceedings of the Northwestern Homotopy Theory Conference, American Mathematical Society, Providence, Rhode Island, volume 19 of Contemporary Mathematics, 1983 pp. 65-69, doi:10.1090/conm/019/711043, held at Northwestern University, Evanston, Illinois, March 22 -26, 1982.
[9]	V. L. Dol'nikov, A certain combinatorial inequality, Sib. Math. J. 29 (1988), 375-379, doi: 10.1007/bf00969645.
[10]	W. Dörfler and D. A. Waller, A category-theoretical approach to hypergraphs, Arch. Math. 34 (1980), 185-192, doi:10.1007/bf01224952.
[11]	P. Erdos, Problems and results in combinatorial analysis, in: Colloquio Internazionale sulle Teorie Combinatorie, Tomo II, Accademia Nazionale dei Lincei, Rome, pp. 3-17, 1976, proceedings of the Convegni Lincei, No. 17, held in Rome, September 3 - 15, 1973.
[12]	H. Hajiabolhassan and F. Meunier, Hedetniemi's conjecture for Kneser hypergraphs, J. Comb. Theory Ser. A 143 (2016), 42-55, doi:10.1016/j.jcta.2016.05.002.
[13]	I. Kriz, Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc. 333 (1992), 567-577, doi:10.2307/2154049.
[14]	I. Kriz, A correction to: "Equivariant cohomology and lower bounds for chromatic numbers" [Trans. Amer. Math. Soc. 333 (1992), 567-577], Trans. Amer. Math. Soc. 352 (2000), 19511952, doi:10.1090/s0002- 9947-99- 02494- 0.
[15]	L. Loväsz, Kneser's conjecture, chromatic number, and homotopy, J. Comb. Theory Ser. A 25 (1978), 319-324, doi:10.1016/0097-3165(78)90022-5.
[16]	J. Matousek, Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer-Verlag, Berlin, 2003, written in cooperation with Anders Björner and Günter M. Ziegler.
[17]	J. Matousek, A combinatorial proof of Kneser's conjecture, Combinatorica 24 (2004), 163170, doi:10.1007/s00493-004-0011-1.
[18]	F. Meunier, The chromatic number of almost stable Kneser hypergraphs, J. Comb. Theory Ser. A 118 (2011), 1820-1828, doi:10.1016/j.jcta.2011.02.010.
126
Ars Math. Contemp. 15 (2018) 113-126
[19]	F. Meunier, Colorful subhypergraphs in Kneser hypergraphs, Electron. J. Combin. 21 (2014), #P1.8, http://www.combinatorics.org/ojs/index.php/eljc/ article/view/v21i1p8.
[20]	G. Simonyi and G. Tardos, Colorful subgraphs in Kneser-like graphs, European J. Combin. 28 (2007), 2188-2200, doi:10.1016/j.ejc.2007.04.015.
[21]	C. Tardif, Hedetniemi's conjecture, 40 years later, Graph Theory Notes N. Y. 54 (2008), 46-57, http://gtn.kazlow.info/GTN54.pdf.
[22]	X. Zhu, On the chromatic number of the products of hypergraphs, Ars Combin. 34 (1992), 25-31.
[23]	X. Zhu, A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998), 1-24, doi:10. 11650/twjm/1500406890.
[24]	G. M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), 671-691, doi:10.1007/s002220100188.
[25]	G. M. Ziegler, Erratum: "Generalized Kneser coloring theorems with combinatorial proofs" [Invent. Math. 147 (2002), 671-691], Invent. Math. 163 (2006), 227-228, doi:10.1007/ s00222-005-0466-8.