TY - JOUR
T1 - Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
AU - Balogh, József
AU - Cherkashin, Danila
AU - Kiselev, Sergei
N1 - The work was supported by the Russian government grant NSh-6760.2018.1, and by the grant of the Government of the Russian Federation for the state support of scientific research carried out under the supervision of leading scientists, agreement 14.W03.31.0030 dated 15.02.2018. Research of the first author is partially supported by NSF Grant DMS-1500121 and by the Langan Scholar Fund (UIUC). The authors are grateful to A. Raigorodskii for the statement of the problem and to H.R. Daneshpajouh for drawing their attention to the generalized Kneser hypergraph. The authors thank the referees for their careful reading of the manuscript and for their useful comments.
The work was supported by the Russian government grant NSh-6760.2018.1 , and by the grant of the Government of the Russian Federation for the state support of scientific research carried out under the supervision of leading scientists, agreement 14.W03.31.0030 dated 15.02.2018. Research of the first author is partially supported by NSF Grant DMS-1500121 and by the Langan Scholar Fund (UIUC).
PY - 2019/6
Y1 - 2019/6
N2 - We suggest a new method for coloring generalized Kneser graphs based on hypergraphs with high discrepancy and a small number of edges. The main result provides a proper coloring of K(n,n∕2−t,s) in (4+o(1))(s+t) 2 colors, which is produced by Hadamard matrices. Also, we show that for colorings by independent set of a natural type, this result is the best possible up to a multiplicative constant. Our method extends to Kneser hypergraphs as well.
AB - We suggest a new method for coloring generalized Kneser graphs based on hypergraphs with high discrepancy and a small number of edges. The main result provides a proper coloring of K(n,n∕2−t,s) in (4+o(1))(s+t) 2 colors, which is produced by Hadamard matrices. Also, we show that for colorings by independent set of a natural type, this result is the best possible up to a multiplicative constant. Our method extends to Kneser hypergraphs as well.
UR - https://www.scopus.com/pages/publications/85064090237
UR - https://www.scopus.com/pages/publications/85064090237#tab=citedBy
U2 - 10.1016/j.ejc.2019.03.004
DO - 10.1016/j.ejc.2019.03.004
M3 - Article
AN - SCOPUS:85064090237
SN - 0195-6698
VL - 79
SP - 228
EP - 236
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -