Back to Search Start Over

Lower bounds for the chromatic number of certain Kneser-type hypergraphs.

Lower bounds for the chromatic number of certain Kneser-type hypergraphs.

Authors :
Azarpendar, Soheil
Jafari, Amir
Source :
European Journal of Combinatorics. May2023, Vol. 110, pN.PAG-N.PAG. 1p.
Publication Year :
2023

Abstract

Let n ≥ 1 , r ≥ 2 , and s ≥ 0 be integers and P = { P 1 , ... , P l } be a partition of [ n ] = { 1 , ... , n } with | P i | ≤ r for i = 1 , ... , l. Also, let F be a family of non-empty subsets of [ n ]. The r -uniform Kneser-type hypergraph KG r (F , P , s) is the hypergraph with the vertex set consisting of all P -admissible elements F ∈ F , that is | F ∩ P i | ≤ 1 for i = 1 , ... , l and the edge set consisting of all r -subsets { F 1 , ... , F r } of the vertex set that | F i ∩ F j | ≤ s for all 1 ≤ i < j ≤ r. In this article, we extend the equitable r -colorability defect ecd r (F) of Abyazi Sani and Alishahi to the case when one allows intersections among the vertices of an edge. It will be denoted by ecd r (F , s). We then prove that the chromatic number of KG r (F , P , s) is bounded from below by ecd r (F , ⌊ s / 2 ⌋) r − 1 , under the technical assumption that the pair (F , P) is ⌊ s / 2 ⌋ -good. This condition holds in the cases when s = 0 , or P consists of singletons, that is P -admissibility is automatically satisfied for all sets or the family F is the family of all k -sets in [ n ] for some integer s < k < n. This work generalizes many existing results in the literature on the Kneser hypergraphs. It generalizes the previous results of the current authors from the special family of all k -subsets of [ n ] to a general family F of subsets. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*HYPERGRAPHS
*INTEGERS
*FAMILIES

Details

Language :
English
ISSN :
01956698
Volume :
110
Database :
Academic Search Index
Journal :
European Journal of Combinatorics
Publication Type :
Academic Journal
Accession number :
162921102
Full Text :
https://doi.org/10.1016/j.ejc.2022.103664