Hedetniemi's conjecture for Kneser hypergraphs

Hedetniemi's conjecture for Kneser hypergraphs

Journal of Combinatorial Theory, Series A 143 (2016) 42–55 Contents lists available at ScienceDirect Journal of Combinatorial Theory, Series A www.e...

370KB Sizes 0 Downloads 13 Views

Journal of Combinatorial Theory, Series A 143 (2016) 42–55

Contents lists available at ScienceDirect

Journal of Combinatorial Theory, Series A www.elsevier.com/locate/jcta

Hedetniemi’s conjecture for Kneser hypergraphs Hossein Hajiabolhassan a,b , Frédéric Meunier c a

Department of Applied Mathematics and Computer Science, Technical University of Denmark, DK-2800 Lyngby, Denmark b Department of Mathematical Sciences, Shahid Beheshti University, G.C., P.O. Box 19839-69411, Tehran, Iran c Université Paris Est, CERMICS, 77455 Marne-la-Vallée CEDEX, France

a r t i c l e

i n f o

Article history: Received 13 November 2014 Available online xxxx Keywords: Categorical product Kneser graphs and hypergraphs Hedetniemi’s conjecture Zp -Tucker lemma

a b s t r a c t One of the most famous conjectures in graph theory is Hedetniemi’s conjecture stating that the chromatic number of the categorical product of graphs is the minimum of their chromatic numbers. Using a suitable extension of the definition of the categorical product, Zhu proposed in 1992 a similar conjecture for hypergraphs. We prove that Zhu’s conjecture is true for the usual Kneser hypergraphs of same rank. It provides to the best of our knowledge the first nontrivial and explicit family of hypergraphs with rank larger than two satisfying this conjecture (the rank two case being Hedetniemi’s conjecture). We actually prove a more general result providing a lower bound on the chromatic number of the categorical product of any Kneser hypergraphs as soon as they all have same rank. We derive from it new families of graphs satisfying Hedetniemi’s conjecture. The proof of the lower bound relies on the Zp -Tucker lemma. © 2016 Elsevier Inc. All rights reserved.

E-mail addresses: [email protected] (H. Hajiabolhassan), [email protected] (F. Meunier). http://dx.doi.org/10.1016/j.jcta.2016.05.002 0097-3165/© 2016 Elsevier Inc. All rights reserved.

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

43

1. Introduction 1.1. Categorical product and coloring Let G = (V, E) and G = (V  , E  ) be two graphs. Their categorical product, denoted G × G , is the graph defined by V (G × G ) = V × V  E(G × G ) = {{(u, u ), (v, v  )} : {u, v} ∈ E, {u , v  } ∈ E  }. Hedetniemi’s conjecture [13] – one of the most intriguing conjectures in graph theory – states that the chromatic number of the categorical product of two graphs is the minimum of their chromatic numbers. Hedetniemi’s conjecture has been verified in many cases, but the general case is still open. Tardif [27] and Zhu [31] provide extensive surveys of this topic. There exists also a categorical product for hypergraphs, defined by Dörfler and Waller [10] in 1980. Using this definition of the categorical product of hypergraphs, Zhu [30] conjectured in 1992 that a generalization of Hedetniemi’s conjecture holds for hypergraphs as well. A hypergraph H is a pair (V, E), where V is a finite set of vertices and E a collection of non-empty subsets of V . The elements of V are the vertices and the elements of E are the edges. Throughout this paper, we only consider hypergraphs without multiple edges and E is thus a usual set. As for graphs, we also denote the vertex set of H by V (H) and its edge set by E(H) when there is a risk of confusion. Given a subset X of V , the restriction of H to X is a hypergraph with X as vertex set and with {e ∈ E : e ⊆ X} as edge set. It is denoted H[X]. The rank of H is maxe∈E |e|. Let G = (V, E) and G  = (V  , E  ) be two hypergraphs. The projections π1 : V ×V  → V and π2 : V × V  → V  are defined by π1 : (u, u ) → u and π2 : (u, u ) → u , respectively. For a set A ⊆ V × V  and j ∈ {1, 2}, we define moreover πj (A) to be {πj (a) : a ∈ A}. The categorical product G × G  of G and G  , denoted G × G  , is the hypergraph defined by V (G × G  ) = V × V  E(G × G  ) = {e ⊆ V × V  : π1 (e) ∈ E, π2 (e) ∈ E  } . In words, a subset of V × V  is an edge of G × G  if its projection on the first component is an edge of G and its projection on the second component is an edge of G  . Note that this product can be made associative by a natural identification and thus defined for more than two hypergraphs. A proper coloring of a hypergraph is an assignment of colors to the vertices so that there are no monochromatic edges. The chromatic number of a hypergraph H, denoted χ(H), is the minimum number of colors a proper coloring of H may have. If the chromatic number is k or less, the hypergraph is k-colorable.

44

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

Conjecture 1 ([30]). Let G and G  be two hypergraphs. We have χ(G × G  ) = min{χ(G), χ(G  )}. The chromatic number of the product is at most the chromatic number of each of the hypergraphs, since a coloring of any of them provides a coloring of the product. The difficult part in this conjecture is thus the reverse inequality. When G and G  are graphs, their categorical product according to the definition for hypergraphs is not a graph anymore, since it will in general contain edges of cardinality four. However, edges of cardinality greater than two contain other edges as subset. It follows from the definition that deleting such edges does not change the chromatic number. Therefore, the chromatic number of the categorical product of two graphs does not depend on whether it is defined as the product of graphs or as the product of hypergraphs. Thus Conjecture 1 is a true generalization of Hedetniemi’s conjecture. 1.2. Kneser hypergraphs In 1976, Erdős [11] initiated the study of Kneser hypergraphs KGr (H) defined for a hypergraph H = (V (H), E(H)) and an integer r ≥ 2 by V (KGr (H)) = E(H) E(KGr (H)) = {{e1 , . . . , er } : e1 , . . . , er ∈ E(H), ei ∩ ej = ∅ for all i, j with i = j}. These hypergraphs enjoy several properties, which are interesting from both graph theoretical and set theoretical points of view, especially when r = 2, i.e., when we are dealing with Kneser graphs. Among many references dealing with Kneser hypergraphs, one can cite [6,17,32]. For Kneser graphs, there are much more references, see [12,18,23,24,26,28] among many of them.    There are also “usual” Kneser hypergraphs, which are obtained with H = [n], [n] . k r They are denoted KG (n, k). In the present paper, we prove that Conjecture 1 is true for the usual Kneser hypergraphs, which provides to the best of our knowledge the first non-trivial and explicit family of hypergraphs not being graphs for which Conjecture 1 is true. We actually prove a more general result involving the colorability defect of a hypergraph. The r-colorability defect of a hypergraph H, introduced by Dol’nikov [9] for r = 2 and by Kříž [15,16] for any r, is denoted cdr (H) and is the minimum number of vertices to be removed from H so that the restriction of H to the remaining vertices is r-colorable. We have thus cdr (H) = min{|Y | : Y ⊆ V (H) and χ(H[V (H) \ Y ]) ≤ r}. 1 Kříž [15,16] proved that χ(KGr (H)) ≥ r−1 cdr (H). The r-colorability defect has then been used by other authors as a tool for exploring further properties of coloring of graphs and hypergraphs [22,24,32].

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

45

1.3. Main results In this paper, we prove the following theorem. Theorem 1. Let H1 , . . . , Ht be hypergraphs and let r be a positive integer such that r ≥ 2. Then χ (KGr (H1 ) × · · · × KGr (Ht )) ≥

1 min cdr (H ). r − 1 =1,...,t

The case t = 1 is Kříž’s theorem. Note that the product in this theorem involves an arbitrary number of Kneser hypergraphs, while in Conjecture 1 only two hypergraphs are involved. The reason is that the categorical product of hypergraphs is associative and if the conjecture holds for two hypergraphs, it can be straightforwardly extended to the product of any number of hypergraphs. On the other hand, it is easy to see that Theorem 1 for only two Kneser hypergraphs does not imply its correctness for any number of Kneser hypergraphs. We will actually see that a stronger result involving the r-alternation number instead of the r-colorability defect holds. The r-alternation number of a hypergraph has been introduced by Alishahi and Hajiabolhassan [4] and it provides better lower bounds for Kneser hypergraphs. This result and the precise definition of the r-alternation number are given in Section 3.1. The fact that Conjecture 1 is true for the usual Kneser hypergraphs is obtained via the easy equality  cdr



[n] [n], k

 = n − r(k − 1)

and a theorem by Alon, Frankl, and Lovász [7] stating that n − r(k − 1) . χ(KG (n, k)) = r−1 

r

Corollary 1. Let r ≥ 2 be an integer and let n1 . . . , nt and k1 , . . . , kt be positive integers such that n ≥ rk for  = 1, . . . , t. We have χ (KGr (n1 , k1 ) × · · · × KGr (nt , kt )) = min χ (KGr (n , k )) . =1,...,t

When r = 2, Corollary 1 implies the already known fact that Hedetniemi’s conjecture is true for the usual Kneser graphs [8,14,29].

46

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

2. Proof of the main result 2.1. Main steps of the proof The proof consists in proving the following two lemmas. Their combination provides a proof of Theorem 1. They are respectively proved in Section 2.2 and in Section 2.3. Lemma 1. Let r and r be two positive integers. If Theorem 1 holds for both r and r , then it holds also for r = r r . Lemma 2. Let H1 , . . . , Ht be hypergraphs and let p be a prime number. Then χ (KGp (H1 ) × · · · × KGp (Ht )) ≥

1 min cdp (H ). p − 1 =1,...,t

2.2. Reduction to the case when r is a prime number The proof of Lemma 1 is based on the following lemma. Given a hypergraph H and two positive integers s and C, we define a new hypergraph TH,C,s by V (TH,C,s ) = V (H) E(TH,C,s ) = {A ⊆ V (H) : cds (H[A]) > (s − 1)C}. Lemma 3. The following inequality holds for any positive integer r cdrs (H) ≤ r(s − 1)C + cdr (TH,C,s ). Proof. Let A ⊆ V (H) be such that |A| = |V (H)| − cdr (TH,C,s ) and such that TH,C,s [A] is r-colorable. The existence of such an A is ensured by the definition of cdr (TH,C,s ). Consider any proper coloring of TH,C,s [A] with r colors and denote by Xj ⊆ A the set of vertices of color j. Since the coloring is proper, Xj is never an edge of TH,C,s . It implies that we have cds (H[Xj ]) ≤ (s − 1)C for all j ∈ [r]. We can thus remove at most (s − 1)C vertices from each Xj and get Yj ⊆ Xj with χ(H[Yj ]) ≤ s. There is thus a

r

r proper coloring of H[ j=1 Yj ] with at most rs colors and the restriction H[ j=1 Yj ] is obtained by the removal of at most r(s − 1)C + cdr (TH,C,s ) vertices of H. 2 Proof (of Lemma 1). Suppose for a contradiction that Theorem 1 holds for r and r , but does not hold for r r . There are hypergraphs H1 , . . . , Ht such that C<

1 min cdr r (H ), − 1 =1,...,t

r r

 

 

where C is the chromatic number of KGr r (H1 ) × · · · × KGr r (Ht ). Let c be a proper     coloring of KGr r (H1 ) × · · · × KGr r (Ht ) with C colors. By Lemma 3,

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

47

cdr (TH ,C,r ) ≥ cdr r (H ) − r (r − 1)C > (r r − 1)C − r (r − 1)C = (r − 1)C > 0. Hence, each TH ,C,r has at least one edge. Let e be an edge of TH ,C,r for each . As  cdr (H [e ]) > (r − 1)C and Theorem 1 holds for r , we conclude that χ(KGr (H1 [e1 ]) ×   · · · × KGr (Ht [et ])) > C. Thus there is a monochromatic edge in KGr (H1 [e1 ]) × · · · ×  KGr (Ht [et ]) for the coloring c. Note that if e is an edge of TH ,C,r for each , then (e1 , . . . , et ) is a vertex of    KGr (TH1 ,C,r ) × · · · × KGr (THt ,C,r ). For each (e1 , . . . , et ) ∈ V (KGr (TH1 ,C,r ) ×  · · · × KGr (THt ,C,r )), denote by h(e1 , . . . , et ) the color of a monochromatic edge in   KGr (H1 [e1 ]) × · · · × KGr (Ht [et ]) for the coloring c.   Now let us check that h is a proper coloring of KGr (TH1 ,C,r ) × · · · × KGr (THt ,C,r ).   On the contrary, suppose that there is an edge of KGr (TH1 ,C,r ) × · · · × KGr (THt ,C,r ) such that h assigns the same color α to all of its vertices. This edge has the form {(e11 , . . . , e1t ), . . . , (eρ1 , . . . , eρt )} 

for some ρ ≥ r . By definition of h, there is for each k ∈ [ρ] an edge in KGr (H1 [ek1 ]) ×  · · · × KGr (Ht [ekt ]) whose vertices get all the color α by c. This edge is of the form k k k k {(f1,1 , . . . , ft,1 ), . . . , (f1,γ , . . . , ft,γ )} k k

for some γk ≥ r . For each , there are r pairwise disjoint elements in {ek : k ∈ [ρ]}, k and each ek contains r pairwise disjoint elements of {f,j : j ∈ [γk ]}. Hence, the set ρ

k k k k {(f1,1 , . . . , ft,1 ), . . . , (f1,γ , . . . , ft,γ )} k k

k=1  

 

is an edge of KGr r (H1 ) × · · · × KGr r (Ht ), whose vertices get all the same color α by c, which is in contradiction with the assumption on c. The map h is therefore a proper   coloring of KGr (TH1 ,C,r ) × · · · × KGr (THt ,C,r ) with C colors. Since Theorem 1 holds for r , we have C≥

r

1 min cdr (TH ,C,r ). − 1 =1,...,t

Lemma 3 implies via a direct calculation that (r r − 1)C ≥ min∈[t] cdr r (H ), which is in contradiction with the starting assumption. 2 2.3. Proof of the main result when r is a prime number The proof of Lemma 2 makes use of a “Zp -Tucker lemma” proposed in [21] as a slight generalization of a “Zp -Tucker lemma” used by Ziegler [32] in a combinatorial proof of

48

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

Kříž’s theorem (proof inspired by Matoušek’s proof of the special case of usual Kneser graphs [19]). Before stating it, we introduce some notations and some notions. We denote by Zr the cyclic and multiplicative group of the rth roots of unity. We denote by ω one of its generators. Hereafter, we use Zr as shorthand of Zr ∪ {0} and (Zr )n∗ instead of (Zr ∪ {0})n \ {(0, . . . , 0)}. Let x = (x1 , . . . , xn ) and x = (x1 , . . . , xn ) be two vectors of Zrn = (Zr ∪ {0})n . By the notation “x ⊆ x ”, we mean that the following implication holds for all i ∈ [n] xi = 0

=⇒

xi = xi .

The number of nonzero components of a vector x is denoted |x|. We introduce also the notation suppj (x) for the set of indices i such that xi = ω j . Note that we have r |x| = j=1 | suppj (x)|. The action of a finite group H on a set X is free if the subgroup Hx := {h ∈ H : h · x = x} – the stabilizer of x – is trivial for every x ∈ X. If H is finite and freely acts on X, every orbit has its cardinality equal to the order of H. For x ∈ Zrn , define ω · x = (ωx1 , . . . , ωxn ), where ω0 = 0. It defines a free action of Zr on (Zr )n∗ . For (ω j , k) ∈ Zr × [m], where m is a positive integer, we define ω · (ω j , k) to be (ω j+1 , k). It defines a free action of Zr on Zr × [m]. A map between two sets on which Zr acts is Zr -equivariant if it commutes with the action of Zr . Lemma 4 (Zp -Tucker lemma [21]). For a prime number p and positive integers α, m, n, with α ≤ m let λ : (Zp )n∗ −→ x

Zp × [m]

−→ (s(x), v(x))

be a Zp -equivariant map such that: • if x(1) , x(2) ∈ (Zp )n∗ satisfy v(x(1) ) = v(x(2) ) ≤ α and x(1) ⊆ x(2) , then s(x(1) ) = s(x(2) ); • if x(1) , x(2) , . . . , x(p) ∈ (Zp )n∗ satisfy v(x(1) ) = v(x(2) ) = · · · = v(x(p) ) ≥ α + 1 and x(1) ⊆ x(2) ⊆ · · · ⊆ x(p) , then s(x(i) ) = s(x(j) ) for some 1 ≤ i < j ≤ p. Then α + (m − α)(p − 1) ≥ n. The proof of Lemma 2 also uses a Zp -equivariant map ε : (2Zp × · · · × 2Zp ) \ ({∅, Zp } × · · · × {∅, Zp }) −→ Zp , which we now define for every prime p. The Zp -action considered on (2Zp × · · · × 2Zp ) \ ({∅, Zp } × · · · × {∅, Zp })

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

49

is the action ω · (B1 , . . . , Bt ) := (ω · B1 , . . . , ω · Bt ), where for B ⊆ Zp we define ω · B :=

b∈B {ωb}. Let us prove that this action is free. By Lagrange’s theorem, the stabilizer of an element (B1 , . . . , Bt ) is of order 1 or p. If it were of order p, then ω would be in the stabilizer and each Bi would be in {∅, Zp } because ω · B = B implies B ∈ {∅, Zp }. It is excluded by definition and thus the stabilizer of each element (B1 , . . . , Bt ) is trivial, which proves that the action is free. Now choose a representative rO for each orbit O. For each (B1 , . . . , Bt ) in orbit O, set ε(B1 , . . . , Bt ) = ω  , where ω  is the unique element of Zp such that ω  · rO = (B1 , . . . , Bt ). Since the action is free, ε is well-defined and Zp -equivariant. Proof (of Lemma 2). Without loss of generality, we assume that cdp (H1 ) = min cdp (H ). =1,...,t

Denote by V and by E respectively the vertex set and the edge set of H . The cardinality of V is denoted by n and we arbitrarily identify V and [n ]. Let c : E1 × · · · × Et → [C] be a proper coloring of KGp (H1 ) × · · · × KGp (Ht ) with C colors. We endow E1 × · · · × Et with an arbitrary total order such that (S1 , . . . , St ) (T1 , . . . , Tt ) if c(S1 , . . . , St ) < c(T1 , . . . , Tt ). We now aim to apply the Zp -Tucker lemma (Lemma 4) with n=

t

n ,

α = n − cdp (H1 ) + p − 1,

and m := α + C − 1

=1

to obtain α + (m − α)(p − 1) ≥ n which implies the required lower bound on C. We define the relevant Zp -equivariant map λ : (Zp )n∗ → Zp × [m]. First, we write x ∈ (Zp )n∗ as x = (y 1 , . . . , y t ) with y  ∈ (Zp )n∗  for  ∈ [t] and associate set A = A (x) to x that consists of all ω j ∈ Zp such that suppj (y  ) contains at least one edge of E . Second, to define λ(x) = (s(x), v(x)) we distinguish two cases. First case: A = Zp for at least one  ∈ [t]. We define

v(x) :=

: A ∈{∅,Zp }

+

|y  | 

    ⊆ y  and E(H [suppj ( |A | + max | y| : y y  )]) = ∅ for all j) .

: A ∈{∅,Z / p}

(1) Notice we always have in this case 1 ≤ v(x) ≤ α. If A ∈ {∅, Zp } for all  ∈ [t], we define s(x) to be the first nonzero entry of x. Otherwise, we define s(x) to be ε(A1 , . . . , At ). Second case: A = Zp for all  ∈ [t]. We set Σx = ∪j∈[p] Σjx where Σjx is defined as  Σjx := (S1 , . . . , St ) : S ∈ E

 and S ⊆ suppj (y  ) for all  ∈ [t] .

50

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

Clearly, each Σjx consists only of vertices of KGp (H1 ) × · · · × KGp (Ht ) and, as A = Zp for all  ∈ [t], we conclude that all Σjx are nonempty. Let S j and S min be the -minimal elements of Σjx and Σx , respectively. As there is a unique jmin such that S min ∈ Σjxmin , we define s(x) := ω jmin

and v(x) := α + c(S min ).

Thus α + 1 ≤ v(x) and we claim v(x) ≤ α + C − 1. Since {S 1 , . . . , S p } is an edge of KGp (H1 ) × · · · × KGp (Ht ) and c is a proper coloring of KGp (H1 ) × · · · × KGp (Ht ), we have min{c(S j ) : j ∈ [p]} < C. Now the -minimality of S min implies c(S min ) < C. Therefore, α + 1 ≤ v(x) ≤ α + C − 1, as required. In the first case, if A (x) ∈ {∅, Zp } for all  ∈ [t], then the first nonzero entry of ω · x is equal to ω times the first nonzero entry of x, and if not, then we have     ε A1 (ω · x), . . . , At (ω · x) = ε ω · (A1 (x), . . . , At (x)) = ω · ε(A1 (x), . . . , At (x)). The first equality results from the definition of A (x) and the second is because ε is Zp -equivariant. Thus, in the first case, s(ω · x) = ωs(x). In the second case, we have j Σj+1 ω·x = Σx and thus again s(ω · x) = ωs(x). It is straightforward to check that in both cases v(ω · x) = v(x). The map λ is thus Zp -equivariant. It remains to check that this map satisfies the two required properties for the application of Zp -Tucker lemma. Let x(1) , x(2) ∈ (Zp )n∗ be such that v(x(1) ) = v(x(2) ) ≤ α. We are necessarily in the first case. Assume x(1) ⊆ x(2) . We shall show that s(x(1) ) = s(x(2) ). Since x(1) ⊆ x(2) , we have A (x(1) ) ⊆ A (x(2) ) for all . It follows from the definition of v that if there is an index  for which |A (x(1) )| < |A (x(2) )|, then v(x(1) ) < v(x(2) ), contrary to our assumption. Therefore, A (x(1) ) = A (x(2) ) for all . If A (x(1) ) ∈ {∅, Zp } for all , then the definition of v implies that x(1) = x(2) . Otherwise, as s(x) = ε(A1 (x), . . . , At (x)), we have s(x(1) ) = s(x(2) ). Let x(1) ⊆ x(2) ⊆ · · · ⊆ x(p) ∈ (Zp )n∗ be such that v(x(1) ) = v(x(2) ) = · · · = v(x(p) ) ≥ (i) α + 1. We are necessarily in the second case. Define S min to be the -minimal element of Σx(i) .  Suppose for a contradiction that the s(x(i) )’s are pairwise distinct for i = 1, . . . , p.  (1) (p) Then S min , . . . , S min is an edge of KGp (H1 ) × · · · × KGp (Ht ) that is monochromatic since v(x(1) ) = v(x(2) ) = · · · = v(x(p) ). It contradicts the fact that c is a proper coloring. Hence, the s(x(i) )’s are not pairwise distinct for i = 1, . . . , p. 2

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

51

3. Improvements via alternation number 3.1. Main theorem involving the alternation number An alternating sequence is a sequence x1 , x2 , . . . , xm ∈ Zr such that any two consecutive terms are different. For any x = (x1 , x2 , . . . , xn ) ∈ Zrn and any permutation σ ∈ Sn , we denote by altσ (x) the maximum length of an alternating subsequence of the sequence xσ(1) , . . . , xσ(n) . Note that by definition this subsequence uses only elements of Zr . In particular, if x = (0, . . . , 0), then altσ (x) = 0 for any permutation σ. Let H = (V, E) be a hypergraph with n vertices. We identify V and [n]. The r-alternation number altr (H) of H is defined as altr (H) = min max{altσ (x) : x ∈ Zrn with E(H[suppj (x)]) = ∅ for j = 1, . . . , r}. σ∈Sn

In other words, for each permutation σ of [n], we choose x such that altσ (x) is maximal while none of the suppj (x)’s contain an edge of H; then, we take a permutation for which this quantity is minimal. This number does not depend on the way V and [n] have been identified. Theorem 1 can now be improved with the help of the alternation number. Theorem 2. Let H1 , . . . , Ht be hypergraphs and let r be a positive integer such that r ≥ 2. Then χ (KGr (H1 ) × · · · × KGr (Ht )) ≥

1 min {|V (H )| − altr (H )}. r − 1 =1,...,t

Note that |V | − altr (H) ≥ cdr (H). Indeed, let σ be a permutation and let x be an element of Zrn such that altr (H) = altσ (x). We give the color j to every vertex in suppj (x). It provides a proper coloring of H[V \ X] with r colors, where X is the com

plement of j suppj (x). By definition of the colorability defect, we have |X| ≥ cdr (H). 

   Moreover,  j suppj (x) ≥ altσ (x). Thus the claimed inequality holds, and Theorem 2 implies Theorem 1. The 2-stable Kneser hypergraph KGr (n, k)2-stab is a Kneser hypergraph whose vertices are the k-subsets A of [n] no elements of which are cyclically adjacent (if i = i are both in A, then 2 ≤ |i −i | ≤ n −2) and whose edge set consists of all r-tuples of pairwise disjoint   vertices. It is straightforward to check that the equality altr ( [n] k 2-stab ) = r(k − 1) + 1 [n] holds, while Ziegler [32] proved the equality cdr ( k 2-stab ) = max{n − 2r(k − 1), 0}. Therefore, Theorem 2 provides in general a strictly better lower bound than Theorem 1. In fact, Theorem 2 implies  that hypergraphs H of same rank r and having their chro1 matic number equal to r−1 (|V (H)| − altr (H)) satisfy Conjecture 1, while this cannot be achieved via Theorem 1. Examples of such hypergraphs H are the 2-stable Kneser hypergraphs provided that r −1 do not divide n −k [4], the almost 2-stable Kneser hypergraphs [21], or some multiple Kneser hypergraphs [4]. Similarly as the proof of Theorem 1 given in Section 2, Theorem 2 is a consequence of two lemmas.

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

52

Lemma 5. Let r and r be two positive integers. If Theorem 2 holds for both r and r , then it holds also for r = r r . Lemma 6. Let H1 , . . . , Ht be hypergraphs and let p be a prime number. Then χ (KGp (H1 ) × · · · × KGp (Ht )) ≥

1 min {|V (H )| − altp (H )}. p − 1 =1,...,t

Lemma 5 can be proved via a technical lemma similar to Lemma 3. We define TH,C,s by V (TH,C,s ) = V (H) E(TH,C,s ) = {A ⊆ V (H) : |A| − alts (H[A]) > (s − 1)C}. Lemma 7. The following inequality holds for any positive integer r altr (TH,C,s ) ≤ r(s − 1)C + altrs (H). We omit the proofs of Lemmas 5, 6, and 7. They follow the same lines as the proofs of Section 2.2 with the following adjustments: replace cdr (H) by |V (H)| − altr (H) everywhere; for Lemma 6, identify V with n so that altr (H ) is achieved by the identity permutation id ∈ Sn for all  ∈ [t], and, in the first case of the definition of λ, replace Equation (1) by v(x) :=

altid (y  ) +

: A =∅

+



|y  |

: A =Zp



    ⊆ y  and E(H [suppj ( y ) : y y  )]) = ∅ for all j . |A | + max altid (

: A ∈{∅Z / p}

3.2. New graphs supporting Hedetniemi’s conjecture Two graphs G and G are homomorphically equivalent when there exists a homomorphism from G to G and a homomorphism from G to G. Alishahi and Hajiabolhassan [2] have defined the altermatic number of a graph G as the quantity ζ(G) = max(|V (H)| − alt2 (H)) H

where the maximum is taken over all hypergraphs H such that KG(H) and G are homomorphically equivalent. This definition makes sense since there always exists at least one such a hypergraph, for which actually an isomorphism holds. This hypergraph is a Kneser representation of G (see for instance [17] for a discussion on Kneser representations). In combination with Theorem 2 we conclude

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

χ(G1 × G2 ) ≥ min{ζ(G1 ), ζ(G2 )}

53

(2)

for graphs G1 and G2 . In particular, Hedetniemi’s original conjecture holds if χ(Gi ) = ζ(Gi ) for i ∈ {1, 2}. It can be shown that χ(KG2 (n, k)) = ζ(KG2 (n, k)) but other families satisfy this equation too. To that end, let KG(G, H) be the Kneser graph whose vertices are subgraphs of G isomorphic to H and whose edges are formed by two edge-disjoint subgraphs. The following families provide examples for χ(G) = ζ(G) and yield new examples satisfying Hedetniemi’s conjecture: 1. the graphs KG(G, H) where G is a multigraph such that the multiplicity of each edge is at least 2 and where H is a simple graph, see [1]. 2. the graphs KG(G, rK2 ), where rK2 is a matching of size r, when G is a sufficiently large dense graph, see [5] for more details. 3. the graphs KG2 (B), where B is the basis set of the truncation of any partition matroid, see [4] where this graph is called a multiple Kneser graph (it is a special case of the multiple Kneser hypergraphs mentioned right after Theorem 2). 4. the graphs KG(G, Tn ) (this is a new notation), when G is a sufficiently large dense graph: The vertices of KG(G, Tn ) are the spanning trees of G and two vertices are adjacent if the corresponding spanning trees are edge-disjoint. For more details, see [3]. Moreover, any pair of graphs obtained by iterating the Mycielski construction on a pair of graphs with the chromatic number equaling the altermatic number satisfies Hedetniemi’s conjecture. Indeed, Alishahi and Hajiabolhassan [2] proved that if χ(G) = ζ(G), then this equality holds for the graph obtained via the Mycielski construction applied on G. Remark 1. For some graphs of the families 1. and 2. above, Hedetniemi’s conjecture was already proved to be true by Alishahi and Hajiabolhassan [2], with the help of the “strong altermatic number”, whose definition resembles the definition of the altermatic number. 3.3. A question on the coindex of B0 (G × G ) For this paragraph, we assume basic knowledge in the topological machinery used for bounding the chromatic number. A presentation and a discussion of this machinery can be found for instance in the paper by Matoušek and Ziegler [20]. We wonder whether the inequality coind(B0 (G × G )) ≥ min{coind(B0 (G)), coind(B0 (G ))} holds. If it were the case, it would provide another proof of the inequality (2) because coind(B0 (G)) + 1 ≥ ζ(G) holds [2]. This question is suggested by the fact that we have coind(B(G × G )) = min{coind(B(G)), coind(B(G ))} [25] and this equality can be used for proving

54

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

an inequality similar to the inequality (2) for the strong altermatic number (which we did not define but only mentioned in Remark 1), see [2] for details. Acknowledgments The authors wish to thank the anonymous referees for their useful comments. The research of Hossein Hajiabolhassan is supported by ERC advanced grant GRACOL. Part of this work was done during a visit of Hossein Hajiabolhassan to the Université Paris Est. He would like to acknowledge Professor Frédéric Meunier for his support and hospitality. References [1] M. Alishahi, H. Hajiabolhassan, Chromatic number via Turán number, arXiv e-prints, arXiv: 1401.0138v4, December 2013. [2] M. Alishahi, H. Hajiabolhassan, Hedetniemi’s conjecture via altermatic number, arXiv e-prints, arXiv:1403.4404v4, March 2014. [3] M. Alishahi, H. Hajiabolhassan, On chromatic number and minimum cut, arXiv e-prints, arXiv: 1407.8035v2, July 2014. [4] M. Alishahi, H. Hajiabolhassan, On the chromatic number of Kneser hypergraphs, J. Combin. Theory Ser. B 115 (2015) 186–209. [5] M. Alishahi, H. Hajiabolhassan, On the chromatic number of matching graphs, arXiv e-prints, arXiv: 1507.08456v1, July 2015. [6] N. Alon, L. Drewnowski, T. Łuczak, Stable Kneser hypergraphs and ideals in N with the Nikodým property, Proc. Amer. Math. Soc. 137 (2009) 467–471. [7] N. Alon, P. Frankl, L. Lovász, The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc. 298 (1986) 359–370. [8] A. Dochtermann, Hom complexes and homotopy theory in the category of graphs, European J. Combin. 30 (2009) 490–509. [9] V.L. Dol’nikov, A certain combinatorial inequality, Sib. Math. J. 29 (1988) 375–397. [10] W. Dörfler, D.A. Waller, A category-theoretical approach to hypergraphs, Arch. Math. 34 (1980) 185–192. [11] P. Erdős, Problems and results in combinatorial analysis, in: Colloquio Internazionale sulle Teorie Combinatorie, Rome, 1973, in: Atti dei Convegni Lincei, vol. II, no. 17, 1976, pp. 3–17. [12] H. Hajiabolhassan, On the b-chromatic number of Kneser graphs, Discrete Appl. Math. 158 (2010) 232–234. [13] S.T. Hedetniemi, Homomorphims of Graphs and Automata, ProQuest LLC, Ann Arbor, MI, 1966, Thesis (Ph.D.)–University of Michigan. [14] P. Hell, An introduction to the category of graphs, in: Topics in Graph Theory, New York, 1977, in: Ann. New York Acad. Sci., vol. 328, 1979, pp. 120–136. [15] I. Kříž, Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc. 33 (1992) 567–577. [16] I. Kříž, A correction to “Equivariant cohomology and lower bounds for chromatic numbers”, Trans. Amer. Math. Soc. 352 (2000) 1951–1952. [17] C. Lange, G.M. Ziegler, On generalized Kneser hypergraph coloring, J. Combin. Theory Ser. A 114 (2007) 159–166. [18] L. Lovász, Kneser’s conjecture, chromatic number and homotopy, J. Combin. Theory Ser. A 25 (1978) 319–324. [19] J. Matoušek, A combinatorial proof of Kneser’s conjecture, Combinatorica 24 (2004) 163–170. [20] J. Matoušek, G.M. Ziegler, Topological lower bounds for the chromatic number: a hierarchy, Jahresber. Dtsch. Math.-Ver. 106 (2004) 71–90. [21] F. Meunier, The chromatic number of almost-stable Kneser hypergraphs, J. Combin. Theory Ser. A 118 (2011) 1820–1828. [22] F. Meunier, Colorful subhypergraphs in Kneser hypergraphs, Electron. J. Combin. 21 (2014) #P1.8.

H. Hajiabolhassan, F. Meunier / J. Combin. Theory Ser. A 143 (2016) 42–55

55

[23] G. Simonyi, G. Tardos, Local chromatic number, Ky Fan’s theorem, and circular colorings, Combinatorica 26 (2006) 587–626. [24] G. Simonyi, G. Tardos, Colorful subgraphs of Kneser-like graphs, European J. Combin. 28 (2007) 2188–2200. [25] G. Simonyi, A. Zsbán, On topological relaxations of chromatic conjectures, European J. Combin. 31 (2010) 2110–2119. [26] S. Stahl, n-tuple colorings and associated graphs, J. Combin. Theory Ser. B 20 (1976) 185–203. [27] C. Tardif, Hedetniemi’s conjecture, 40 years later, Graph Theory Notes N. Y. 54 (2008) 46–57. [28] M. Valencia-Pabon, J.-C. Vera, On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383–385. [29] M. Valencia-Pabon, J.-C. Vera, Independence and coloring properties of direct products of some vertex-transitive graphs, Discrete Math. 306 (2006) 2275–2281. [30] X. Zhu, On the chromatic number of the products of hypergraphs, Ars Combin. 34 (1992) 25–31. [31] X. Zhu, A survey on Hedetniemi’s conjecture, Taiwanese J. Math. 2 (1998) 1–24. [32] G.M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002) 671–691.