Regarding equitable colorability defect of hypergraphs

Authors : Saeed Shaebani

Pages : 184-190

Doi:10.15672/hujms.1254664

View : 137 | Download : 212

Publication Date : 2024-02-29

Article Type : Research Paper

Abstract :After Lovász’s break-through in determining the chromatic number of Kneser graphs (1978), and after extending this result to the chromatic number of $r$-uniform Kneser hypergraphs by Alon, Frankl, and Lovász’s (1986), some important parameters such as colorability defect and equitable colorability defect were introduced in order to provide sharp lower bounds for the chromatic number of general $r$-uniform Kneser hypergraphs. As a generalization of many earlier results in this area, Azarpendar and Jafari (2023) introduced the $s$-th equitable $r$-colorability defect ${\\rm ecd}^r (\\mathcal{F} , s)$; a parameter which provides a lower bound for the chromatic number of generalized Kneser hypergraphs ${\\rm KG} ^r (\\mathcal{F} , s)$. They proved the following nice inequality $$\\chi \\left( {\\rm KG} ^r (\\mathcal{F} , s) \\right) \\geq \\left\\lceil \\frac{ {\\rm ecd}^r \\left( \\mathcal{F} , \\left\\lfloor \\frac{s}{2} \\right\\rfloor \\right) }{r-1} \\right\\rceil ,$$ and noted that it is plausible that the above inequality remains true if one replaces $\\left\\lfloor \\frac{s}{2} \\right\\rfloor$ with $s$. In this paper, considering the relation ${\\rm ecd}^r \\left( \\mathcal{F} , x \\right) \\geq {\\rm cd}^r \\left( \\mathcal{F} , x \\right)$ which always holds, we show that even in the weaker inequality $$\\chi \\left( {\\rm KG} ^r (\\mathcal{F} , s) \\right) \\geq \\left\\lceil \\frac{ {\\rm cd}^r \\left( \\mathcal{F} , \\left\\lfloor \\frac{s}{2} \\right\\rfloor \\right) }{r-1} \\right\\rceil ,$$ no number $x$ greater than $\\left\\lfloor \\frac{s}{2} \\right\\rfloor$ could be replaced by $\\left\\lfloor \\frac{s}{2} \\right\\rfloor$.
Keywords : Hypergraph, Generalized Kneser Hypergraph, Chromatic Number, Colorability Defect, Equitable Colorability Defect, Hypergraph, Generalized Kneser Hypergraph, Chromatic Number, Colorability Defect, Equitable Colorability Defect