RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2018 Volume 54, Issue 2, Pages 45–72 (Mi ppi2266)

This article is cited in 15 papers

Large Systems

Improved Frankl–Rödl theorem and some of its geometric consequences

A. A. Sagdeev

Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology (State University), Moscow, Russia

Abstract: We substantially improve a presently known explicit exponentially growing lower bound on the chromatic number of a Euclidean space with forbidden equilateral triangle. Furthermore, we improve an exponentially growing lower bound on the chromatic number of distance graphs with large girth. These refinements are obtained by improving known upper bounds on the product of cardinalities of two families of homogeneous subsets with one forbidden cross-intersection.

UDC: 621.391.1+519.1

Received: 18.07.2017
Revised: 27.12.2017


 English version:
Problems of Information Transmission, 2018, 54:2, 139–164

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024