Abstract:
We study distance graphs with exponentially large chromatic numbers and
without $k$-cliques, that is, complete subgraphs of size $k$. Explicit
constructions of such graphs use vectors in the integer lattice. For
a large class of graphs we find a sharp threshold for containing
a $k$-clique. This enables us to improve the lower bounds for the maximum
of the chromatic numbers of such graphs. We give a new probabilistic approach
to the construction of distance graphs without $k$-cliques, and this yields
better lower bounds for the maximum of the chromatic numbers for large $k$.
Keywords:
distance graph, chromatic number, clique number, Nelson problem.
Citation:
A. B. Kupavskii, “Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers”, Izv. Math., 78:1 (2014), 59–89
\Bibitem{Kup14}
\by A.~B.~Kupavskii
\paper Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers
\jour Izv. Math.
\yr 2014
\vol 78
\issue 1
\pages 59--89
\mathnet{http://mi.mathnet.ru/eng/im7962}
\crossref{https://doi.org/10.1070/IM2014v078n01ABEH002680}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3204659}
\zmath{https://zbmath.org/?q=an:1287.05029}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2014IzMat..78...59K}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000332236500004}
\elib{https://elibrary.ru/item.asp?id=21276260}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84894711516}
Linking options:
https://www.mathnet.ru/eng/im7962
https://doi.org/10.1070/IM2014v078n01ABEH002680
https://www.mathnet.ru/eng/im/v78/i1/p65
This publication is cited in the following 12 articles:
Yu. A. Demidovich, M. E. Zhukovskii, “Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces”, Math. Notes, 109:5 (2021), 727–734
R. I. Prosanov, “Counterexamples to Borsuk's Conjecture with Large Girth”, Math. Notes, 105:6 (2019), 874–880
Yu. A. Demidovich, “Distance Graphs with Large Chromatic Number and without Cliques of Given Size in the Rational Space”, Math. Notes, 106:1 (2019), 38–51
P. Frankl, A. Kupavskii, “Two problems on matchings in set families - in the footsteps of Erdos and Kleitman”, J. Comb. Theory Ser. B, 138 (2019), 286–313
A. Sokolov, “On the Chromatic Numbers of Rational Spaces”, Math. Notes, 103:1-2 (2018), 111–117
P. Frankl, A. Kupayskii, “Erdös-Ko-Rado theorem for $\{0,\pm 1\}$-vectors”, J. Comb. Theory Ser. A, 155 (2018), 157–179
P. Frankl, “An exact result for $(0,\pm 1)$-vectors”, Optim. Lett., 12:5 (2018), 1011–1017
P. Frankl, A. Kupavskii, “Families of vectors without antipodal pairs”, Stud. Sci. Math. Hung., 55:2 (2018), 231–237
A. V. Berdnikov, “Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size”, Problems Inform. Transmission, 54:1 (2018), 70–83
A. Sagdeev, “Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth”, Math. Notes, 101:3 (2017), 515–528
A. Sagdeev, “The Chromatic Number of Space with Forbidden Regular Simplex”, Math. Notes, 102:4 (2017), 541–546
A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete Geometry and Algebraic Combinatorics, Contemporary Mathematics, 625, 2014, 93–109
Citation in format AMSBIB
Contact us: