Search

The probabilistic version of a classical problem of extremal combinatorics is considered. The stability theorem which says that the independence number of a random subgraph of the graph remains asymptotically constant when edges are randomly removed is generalized to the case of nonconstant parameters. [ABSTRACT FROM AUTHOR]

This paper considers the so-called distance graph G(n, r, s);its vertices can be identified with the r-element subsets of the set {1, 2,...,n}, and two vertices are joined by an edge if the size of the intersection of the corresponding subsets equals s. Note that, in the case s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erdős-Ko-Rado problem; they also play an important role in combinatorial geometry and coding theory. We study properties of random subgraphs of the graph G(n, r, s) in the Erdős-Rényi model, in which each edge is included in the subgraph with a certain fixed probability p independently of the other edges. It is known that if r > 2s + 1, then, for p = 1/2, the size of an independent set is asymptotically stable in the sense that the independence number of a random subgraph is asymptotically equal to that of the initial graph G(n, r, s). This gives rise to the question of how small p must be for asymptotic stability to cease. The main result of this paper is the answer to this question. [ABSTRACT FROM AUTHOR]

A particular class of estimates related to the Nelson–Erdős–Hadwiger problem is studied. For two types of spaces, Euclidean and spaces with metric ℓ1, certain series of distance graphs of small dimensions are considered. Independence numbers of such graphs are estimated by using the linear-algebraic method and combinatorial observations. This makes it possible to obtain certain lower bounds for the chromatic numbers of the spaces mentioned above and, for each case, specify a series of graphs leading to the strongest results. [ABSTRACT FROM AUTHOR]

The article discusses the problem of finding the chromatic number of the plane with a single forbidden distance. The dimension of the space and the number of forbidden distances in the theorems is tackled. The use of the linear-algebraic method to estimate the quantity for an arbitrary vector is also explored.

We consider the distance graph G( n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erdős-Ko-Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G( n, r, s) in the Erdős-Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G( n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log n) times as large as that of the graph G( n, r, s) itself for r ≤ 2 s + 1, while for r > 2 s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide. [ABSTRACT FROM AUTHOR]

We consider the so-called distance graph G( n, 3, 1), whose vertices can be identified with three-element subsets of the set {1, 2,..., n}, two vertices being joined by an edge if and only if the corresponding subsets have exactly one common element. We study some properties of random subgraphs of G( n, 3, 1) in the Erdős-Rényi model, in which each edge is included in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G( n, 3, 1). [ABSTRACT FROM AUTHOR]

The present paper is motivated by Borsuk's classical problem of the partition of sets in spaces into parts of smaller diameter. We obtain sharp estimates for the maximal number of vertices of the induced subgraph of a random graph that, with high probability, is isomorphic to the diameter graph with given chromatic number in a space of any fixed dimension. [ABSTRACT FROM AUTHOR]

The article describes a method of determining the chromatic number of Euclidean space with two forbidden distances. The method determines new asymptotic lower bounds for the chromatic number of Euclidean space. A method for obtaining new estimates and the use of distance graphs to estimate the chromatic number of space, as well as the property of chromatic numbers of finite distance graphs are illustrated.

Upper bounds for the independence numbers in the graphs with vertices at {−1, 0, 1} are improved. Their applications to problems of the chromatic numbers of distance graphs are studied. [ABSTRACT FROM AUTHOR]

The article discusses the study on the independence number of distance graphs with vertices in {−1, 0, 1} n wherein only one linear-algebraic method was known to be effective in obtaining the upper bounds of vertices. It notes that the authors have developed a technique which significantly improved the vertical eigengvalues to a higher dimension and strengthened the asymptotic inequality.

The article cites a study which investigates the lower bounds for the independence numbers of distance graphs along with vertices. The study examines the so-called multiparameter construction, which is probably optimal for searching the correct choice of the parameters. It also highlights the Borsuk problem which is designed to find the minimal number.