Regarding equitable colorability defect of hypergraphs

Year 2024, Volume: 53 Issue: 1, 184 - 190, 29.02.2024

Saeed Shaebani

https://doi.org/10.15672/hujms.1254664

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

References

• [1] R. A. Sani and M. Alishahi, A new lower bound for the chromatic number of general Kneser hypergraphs, Eur. J. Comb. 71, 229–245, 2018.
• [2] N. Alon, P. Frankl, and L. Lovász. The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc. 298 (1), 359–370, 1986.
• [3] S. Azarpendar and A. Jafari, On some topological and combinatorial lower bounds on the chromatic number of Kneser type hypergraphs, J. Comb. Theory Ser. B, 146, 372–381, 2021.
• [4] S. Azarpendar and A. Jafari, Lower bounds for the chromatic number of certain Kneser-type hypergraphs, Eur. J. Comb. 110, 103664, 2023.
• [5] V. L. Dol'nikov, A combinatorial inequality, Sibirsk. Mat. Zh. 29 (3), 53–58, 219, 1988.
• [6] P. Erdos, Problems and results in combinatorial analysis, In Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Atti dei Convegni Lincei, 17, Accad. Naz. Lincei, Rome, 1976.
• [7] M. Kneser, Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen, Math. Z. 61, 429–434, 1955.
• [8] I. Kríž, Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc. 333 (2), 567–577, 1992.
• [9] I. Kríž, A correction to equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc. 352 (4), 1951–1952, 2000.
• [10] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25 (3), 319–324, 1978.