Пересечения, паросочетания и раскраски в экстремальной теории множеств тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Киселев Сергей Григорьевич

• Киселев Сергей Григорьевич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Киселев Сергей Григорьевич

Contents

Introduction

1 Matchings and intersections

1.1 Introduction and statement of the results

1.1.1 Matchings

1.1.2 Setwise intersections and differences

1.2 Preliminaries

1.2.1 Concentration for intersections with a random matching . . 18 The concentration

1.2.2 Concentration for complement to a random set

1.3 Matchings

1.3.1 Proof of Theorem

1.3.2 Discussion

1.4 Distinct differences

1.4.1 Families with small diversity

1.4.2 Proof of Lemma

1.4.3 Counterexamples

Family Ak(n, k)

Family A3(n,k)

1.4.4 Discussion

1.5 Distinct intersections

1.5.1 Preliminaries and the main lemma

1.5.2 The proof of Theorem

1.5.3 Discussion

2 Kneser-type graphs

2.1 Introduction and statement of the results

2.1.1 Non-trivial colors

2.1.2 Random Kneser graphs

2.1.3 Random generalized Kneser graphs

2.2 Other coloring problems and algebraic topology

2.2.1 Number of monochromatic edges

2.2.2 Number of missing vertices

2.3 Trivial colors in colorings of Kneser graphs

2.3.1 Lower bound construction

2.3.2 A weaker upper bound

2.3.3 Proof of Theorem

Proof of Theorem

2.4 Chromatic numbers of random Kneser graphs

2.4.1 Proofs of lower bounds from Theorems 2.7 and

Proof of Lemma

Proof of Lemma

Proof of Lemma

2.4.2 Proof of Theorem

Proof of the upper bound from Theorem 2.7 for k =

2.4.3 Discussion

2.5 Independence numbers of random generalized Kneser graphs

2.5.1 Proof of Theorem

Preliminaries

Proof of the Theorem

2.5.2 Proofs of the Lemmas

Proof of Lemma

Proof of Lemma

Proof of Lemma

Bibliography

Введение диссертации (часть автореферата) на тему «Пересечения, паросочетания и раскраски в экстремальной теории множеств»

Introduction

We will use the following notation. Put [n] := {1,... , n}. For a set X let 2X denote the power set of X and denote the collection of all k-element subsets of X. Any F C 2X we call a family. A family is called intersecting if any its two sets intersect. A family is called down-closed if with any set A it contains all subsets of A.

Extremal combinatorics is a field of combinatorics, which asks, how large or how small a discrete structure with some fixed properties can be. One of the first extremal combinatorics results is Mantel's theorem from 1907 which states that any n-vertex graph without triangles has at most |_n2/4J edges, where the maximum is attained on a complete bipartite graph with (almost) equal parts. In 1941 Turan generalized this result and upper bounded the number of edges in a graph without copies of Kr. Later more generalizations were obtained.

In turn, extremal set theory studies extremal properties of families. E.g., one can see that any intersecting family F C 2[n] has size at most |F| ^ 2n-1. Indeed, for any set X C [n] only one set of the pair (X, X) belongs to F. One can see that the equality is attained on the family of all sets containing a fixed element x E [n]. The case of the k-uniform intersecting families F C is less trivial and was resolved by Erdos, Ko and Rado in [25], which is one of the first and most influential results in extremal set theory.

Theorem (Erdos, Ko, Rado [25]). Let n,k, n ^ 2k, be integers. Suppose that F C is intersecting. Then

F< Ck -1)'

It is easy to see that again the equality is attained on the family all k-sets containing a fixed element x E [n]. We will call such families full stars and denote them by Sx. Subfamilies of Sx are called stars or trivial families.

Another important result, due to Hilton and Milner [45], implies that for n > 2k the equality in the Erdos-Ko-Rado theorem can not be attained for a nontrivial family.

Theorem (Hilton, Milner [45]). Let n,k, n > 2k, be integers. Suppose that F C is an intersecting non-trivial family. Then

fn - 1\ fn - k - 1\ ,

The question behind the Erdos-Ko-Rado theorem can be generalized in the following way: what is the largest family F C without s pairwise disjoint sets? (We will call such s sets an s-matching.) The case s = 2 is equivalent to the Erdos-Ko-Rado theorem. For s ^ 3 and n ^ sk there are two natural constructions of such families of sizes (k) — (n"|+1) and (skk~^, respectively, and famous Erdos Matching Conjecture (EMC) states, that the maximum is always attained on one of them. The conjecture is proven in some ranges of parameters, but still not resolved completely. For somewhat large n, the best results on the conjecture is due to Frankl [32], who showed the validity of the conjecture for roughly n > 2sk and Frankl and Kupavskii [40], who showed the conjecture is valid for n > 3sk and s > so. For n close to sk, the first non-trivial result is due to Frankl [33], who showed the validity of the conjecture for n < s(k + e), where £ = e(k) is roughly k-k. Recently Kolupaev and Kupavskii [61] improved it to

e(k) = uk for s > 101k3.

Many problems in extremal combinatorics have multi-color or rainbow analogues. For EMC such an analogue was proposed by Hyang, Loh and Sudakov [47] and by Aharoni and Howard [1]. The rainbow version of the EMC states that if there are s families Fi,..., Fs C (M) with |F*| > min ((J) - (n"|+1), (skk-1)), then one can take one set from each family such that these sets are pairwise disjoint (a rainbow matching).

Another modification of the EMC was proposed by Aharoni and Howard [1]. Let [n]k be the collection of all k-tuples with elements in [n]. Note that [n]k can be interpreted as the complete k-partite k-uniform hypergraph with parts of size n or as a subfamily of ([kkn]). Aharoni and Howard conjectured, that if families Fu,..., Fs C [n]k are such that |Fi| > (s - 1)nk-1, then there exists a rainbow matching. In their paper, they proved this conjecture for k = 2, 3. Later, Lu and Yu [71] proved it for n > 3(s - 1)(k - 1). In a recent work with Kupavskii [56], we resolved this conjecture for s ^ s0.

Correlation inequalities

Correlation inequalities play an important role in probabilistic combinatorics. One of the first result of that type was proved by Kleitman in [59].

Theorem (Kleitman [59]). Let A, B C 2[n] be two down-closed families. Then the following holds

|A n B| • 2n ^ |A| • |B|.

This result was extended in many different ways. Later Ahlswede and Daykin [2] proved a general results which implies most of these extensions. For families A, B C 2[n] put AAB := {A n B: A E A, B E B} and A V B := {A U B: A E A, B E B}. For a function ^: 2[n] ^ r put ^(A) := EAeA p(A).

Theorem (Ahlswede, Daykin [2]). Let a, P,Y, 6: 2[n] ^ r+ be functions such that for any A, B C [n] holds

a(A) • p(B) < y(A n B) • 6(A U B).

Then for any two families A, B C 2[n] holds

a (A) • P (B) < y (A A B) • 6(A V B).

Note that for down-closed families A, B we have A A B = A n B and for up-closed families A, B we have A V B = A U B. This often comes in handy when working with intersecting families, since the up-closure of an intersecting family is also interesting.

For a family F C 2[n], let D(F) be the family of setwise differences D(F) = {F \ F': F, F' E F}. Note that D(F) can be written as D(F) = F A Fc, where Fc := {[n] \ F: F E F}. In [72] Marica and Schonheim introduced a combinatorial analogue of Graham's conjectures and proved that for a family F C 2[n] it holds that |D(F)| ^ |F|. In [35] Frankl studied this problem for intersecting families and showed that |D(F)| ^ 2n-1. He also proved that for n ^ k(k + 3) and a k-uniform intersecting family F the value of |D(F)| is maximized on the full stars Sx. In [37] with Frankl and Kupavskii we replaced the restriction n ^ k(k + 3) by n ^ 50k ln k and in [38] we studied the behavior of |F A F| for k-uniform intersecting families F.

Kneser graphs

One of the points of view on intersecting families comes from the so-called Kneser graphs. For positive integers n, k, where n ^ 2k, the Kneser graph KGn,k =

(V, E) is a graph whose vertex set V is ([k]), and E is the collection of the pairs of disjoint sets from V. Most of the problems from the previous subsection can be reformulated in terms of Kneser graphs. E.g., the Erdos-Ko-Rado theorem states that the independence number a (KGn,k) = (k-1) and the Erdos Matching Conjecture asks for the maximum size of a vertex set without s-cliques. The notion of Kneser graphs was introduced by Kneser [60], who showed that x(KGn,k) ^ n - 2k + 2. He conjectured that, in fact, equality holds in this inequality. This was proved by Lovasz [69], who introduced the use of topological methods in combinatorics in that paper.

An example of a coloring in n - 2k + 2 colors is very simple: we take n - 2k + 1 star ...,Cn-2k+1, where C := {A e : A C [i,n],i £ A}, and the family ^[n-2k+2,n]). On the other hand, the proofs of the lower bound are non-trivial and use results from combinatorial topology in one way or another. We also note that a weaker lower bound can be proved using correlation inequalities from the previous section.

Kneser graphs can be generalized in the following way. For integers n > r > s ^ 0 the generalized Kneser graph Gn,r,s is a graph on the vertex set , where edges connect pairs of sets intersecting in exactly s elements. Note that the graph Gn,r,0 coincides with KGn,r.

Generalized Kneser graphs were introduced by Larman and Rogers [68], who used them to give the first superlinear lower bounds on the chromatic number of the space x(rn). Later graphs were used by Frankl and Wilson [44] to give the first exponential lower bound x(rn) ^ (1.207... + o(1))n. The best known lower bound x(rn) ^ (1.239 ... + o(1))n due Raigorodskii [82] is also based on a similar of Kneser graphs.

Stability results

It is a natural question to ask, whether the aforementioned results are "stable" with some notion of "stability". That is, we are interested, if the results will still hold if we slightly change the conditions. The Hilton-Milner theorem is one of the results in that direction.

Another approach to study stability is to consider, for a real p, 0 < p < 1, a random family Fp C which includes each k-set independently with probability p and ask, what is the maximal size of intersecting subfamily in Fp. Such approach was taken by Balogh, Bohman and Mubay in [8], who showed that for a wide range of parameters the maximum is sill attained on a star.

Related studies were made by Bogolyubskiy, Gusev, Pyaderkin and Raigorod-skii in [13]. For 0 < p < 1, define the random Kneser graph KGn,k(p) as a subgraph of KGn,k, where each edge is included independently with probability p. In the same way, one can define random generalized Kneser graphs. This notion was introduced in [13], where the authors proved several results concerning the chromatic and independence numbers of the random generalized Kneser graphs. In particular, they showed that asymptotically almost surely (a.a.s.) holds that a(KGn,k(1/2)) = (1 + o(1))(n-1). Later, this result was improved in a series of results [14, 9, 17, 19] which for a wide range of parameters show that a.a.s. the independence number of KGn,k (p) is exactly (k—J).

In view of the importance of the Lovasz' [69] result, it is interesting to consider the chromatic number of KGn,k(p). This question was studied in [64] by Kupavskii. In particular, for constant p and k ^ 2 it was showed, that chromatic number of KGn,k(1/2) is not equal to x(KGn,k) = n — 2k + 2, but the difference x(KGn,k) — x(KGn,k(1/2)) can be upper bounded by C(nlogn)1/k. This is somewhat surprising result, since the independence number of KGn,k(1/2) does not change. In [54] with Kupavskii we obtained sharp bounds on the difference x(KGn,k) — x(KGn,k (1/2)).

Aim of the work

The aim of the dissertation is to study the behavior of intersecting families and related discrete structures. In particular, we study

• families of k-tuples without a rainbow s-matching,

• number of distinct intersections and differences in an intersecting family,

• colorings of KGn,k without trivial colors,

• the chromatic number of KGn,k(p),

• the independence number of Gn,2;1(p).

Scientific novelty

All the presented results are new.

Scientific and practical importance

The dissertation is theoretical. The presented results may find their application

in the extremal combinatorics and extremal set theory research.

Statements to be defended

• resolved Aharoni-Howard conjecture for s ^ s0,

• found an extremal intersecting construction which maximizes the number of distinct intersections for n ^ 50k2,

• found an extremal intersecting construction which maximizes the number of distinct differences for n ^ 50k ln k,

• showed that for n > (2 + e)k2 any coloring of KGn,k in n - 2k + 2 colors has a trivial color,

• obtained sharp upper and lower bounds on x(KGn,k) - x(KGn,k(1/2)) for constant k,

• obtained a sharp bound on k for which x(KGn,k) - x(KGn,k(1/2)) ^ 8,

• obtained an asymptotically tight bound on a(Gk;2;1(1/2)).

Presentations and validation of research results

The results of the thesis were presented at the following conferences:

• Probabilistic Combinatorics Online 2020, Moscow, Russia, 2020.

• European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2019), Bratislava, Slovakia, 2019.

• 2nd Russian-Hungarian Combinatorial Workshop, Budapest, Hungary, 2018.

• The 18th International Conference on Random Structures And Algorithms (RS&A 2017), Gniezno, Poland, 2017.

Publications

The results in the thesis are represented in five published papers [18, 38, 54, 56, 58], one accepted for publication paper [37] and one preprint [55]. Some related results are represented in published papers and preprints [10, 15, 28, 57, 89].

The structure of the thesis

The dissertation consists of an introduction, 2 chapters, and list of the references. The full volume of the dissertation is 100 pages.

Список литературы диссертационного исследования кандидат наук Киселев Сергей Григорьевич, 2022 год

Bibliography

[1] R. Aharoni and D. Howard, A Rainbow r-Partite Version of the Erdos-Ko-Rado Theorem, Combinatorics, Probability and Computing, 26(3) (2017), 321-337.

[2] R. Ahlswede and D.E. Daykin, An inequality for the weights of two families of sets, their unions and intersections, Zeitschrift fiir Wahrscheinlichkeitstheorie und verwandte Gebiete, 43(3) (1978) 183-185.

[3] M. Alishahi and H. Hajiabolhassan, Chromatic Number of Random Kneser Hypergraphs, Journal of Combinatorial Theory, Series A, 154 (2018), 1-20.

[4] N. Alon and F.R.K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, 72 (1988), 15-19.

[5] N. Alon, P. Frankl and L. Lovasz, The chromatic number of Kneser hypergraphs, Transactions of the American Mathematical Society, 298(1) (1986), 359-370.

[6] N. Alon and J. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization, Second Edition, 2000.

[7] K. Azuma, Weighted sums of certain dependent random variables, Tohoku Mathematical Journal, 19(3) (1967), 357-367.

[8] J. Balogh, T. Bohman and D. Mubayi, Erdos-Ko-Rado in random hypergraphs, Combinatorics, Probability and Computing, 18(5) (2009), 629-646.

[9] J. Balogh, B. Bollobas and B.P. Narayanan, Transference for the Erdos-Ko-Rado theorem, Forum of Mathematics, Sigma (Vol. 3) (2015), Cambridge University Press.

[10] J. Balogh, D. Cherkashin and S. Kiselev, Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs, European Journal of Combinatorics, 79 (2019), 228-236.

12

13

14

15

16

17

18

19

20

21

A. Bobu, A. Kupriyanov and A. Raigorodskii, On chromatic numbers of nearly Kneser distance graphs, Doklady Mathematics, 93(3) (2016), 267-269.

L.I. Bogolyubskiy, A.S. Gusev, M.M. Pyaderkin and A.M. Raigorodskii, Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs, Doklady of the Russian Acad. Sci. 457(4) (2014), 383387; English transl. in Doklady Mathematics, 90(1) (2014), 462-465.

L.I. Bogolyubskiy, A.S. Gusev, M.M. Pyaderkin and A.M. Raigorodskii, The independence numbers and the chromatic numbers of random subgraphs of some distance graphs, Mat. Sbornik 206(10) (2015), 3-36; English transl. in Sbornik Mathematics, 206(10) (2015), 1340-1374.

B. Bollobas, B.P. Narayanan and A.M. Raigorodskii, On the stability of the Erdos-Ko-Rado theorem, Journal of Combinatorial Theory, Series A, 137

(2016), 64-78.

D. Cherkashin and S. Kiselev, Independence numbers of Johnson-type graphs, arXiv preprint arXiv:1907.06752 (2019).

F. Chung and L. Linyuan, Concentration inequalities and martingale inequalities: a survey, Internet Mathematics, 3(1) (2006), 79-127.

S. Das and T. Tran, Removal and Stability for Erdos-Ko-Rado, SIAM Journal on Discrete Mathematics, 30(2) (2016), 1102-1114.

N.M. Derevyanko and S.G. Kiselev, Independence numbers of random subgraphs of some distance graph, Problems of Information Transmission, 53(4)

(2017), 307-318.

P. Devlin and J. Kahn, On "stability" in the Erdos-Ko-Rado Theorem, SIAM Journal on Discrete Mathematics, 30(2) (2016), 1283-1289.

I. Dinur and E. Friedgut, Intersecting families are essentially contained in juntas, Combinatorics, Probability and Computing, 18 (2009), 107-122.

D. Ellis, N. Keller and N. Lifshitz, Stability versions of Erdos-Ko-Rado type theorems via isoperimetry, Journal of the European Mathematical Society, 21(12) (2019), 3857-3902.

D. Ellis and N. Lifshitz, On the union of intersecting families, Combinatorics, Probability and Computing, 28(6) (2019), 826-839.

[23] P. Erdos, A problem on independent r-tuples, Ann. Univ. Sci. Budapest. 8 (1965), 93-95.

[24] P. Erdos, Problems and results in combinatorial analysis, Colloq. Internat. Theor. Combin. Rome (1973), Acad. Naz. Lincei, Rome (1976), 3-17.

[25] P. Erdos, C. Ko and R. Rado, Intersection theorems for systems of finite sets, The Quarterly Journal of Mathematics 12 (1961), N1, 313-320.

[26] P. Erdos and L. Lovasz, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and Finite Sets (Proceedings Colloquia Mathematica Societatis Janos Bolyai 10), (1975), 609-627.

[27] P. Erdos and R. Rado, Intersection theorems for systems of sets, Journal of the London Mathematical Society, 1(1) (1960), 85-90.

[28] N. Frankl, S. Kiselev, A. Kupavskii and B. Patkos, VC-saturated set systems, European Journal of Combinatorics, 104 (2022), 103528.

[29] P. Frankl, On intersecting families of finite sets, Journal of Combinatorial Theory, Series A, 24(2) (1978), 146-161.

[30] P. Frankl, A new short proof for the Kruskal-Katona theorem, Discrete Mathematics, 48(2-3) (1984), 327-329.

[31] P. Frankl, Erdos-Ko-Rado theorem with conditions on the maximal degree, Journal of Combinatorial Theory, Series A, 46(2) (1987), 252-263.

[32] P. Frankl, Improved bounds for Erdos' Matching Conjecture, Journal of Combinatorial Theory, Series A, 120 (2013), 1068-1072.

[33] P. Frankl, Proof of the Erdos matching conjecture in a new range, Israel Journal of Mathematics, 222(1) (2017), 421-430.

[34] P. Frankl, Antichains of fixed diameter, Moscow Journal of Combinatorics and Number Theory, 7(3) (2017), 189-219.

[35] P. Frankl, On the number of distinct differences in an intersecting family, Discrete Mathematics, 344(2) (2021), 112210.

[36] P. Frankl and Z. Fiiredi, Extremal Problems concerning Kneser Graphs, Journal of Combinatorial Theory, Series B, 40(3) (1986), 270-285.

[37] P. Frankl, S. Kiselev and A. Kupavskii, Best possible bounds on the number of distinct differences in intersecting families, accepted at European Journal of Combinatorics, arXiv preprint arXiv:2106.05355 (2021).

[38] P. Frankl, S. Kiselev and A. Kupavskii, On the maximum number of distinct intersections in an intersecting family, Discrete Mathematics, 345(4) (2022), 112757.

[39] P. Frankl and A. Kupavskii, Families with no s pairwise disjoint sets, Journal of the London Mathematical Society, 95(3) (2017), 875-894.

[40] P. Frankl and A. Kupavskii, The Erdos Matching Conjecture and Concentration Inequalities, arXiv preprint arXiv:1806.08855 (2018).

[41] P. Frankl and A. Kupavskii, Two problems on matchings in set families — in the footsteps of Erdos and Kleitman, Journal of Combinatorial Theory Series B, 138 (2019), 286-313.

[42] P. Frankl and A. Kupavskii, Simple juntas for shifted families, to appear in Discrete Analysis, arXiv preprint arXiv:1901.03816 (2019).

[43] P. Frankl and A. Kupavskii, Beyond the Erdos Matching Conjecture, arXiv preprint arXiv:1901.09278 (2019).

[44] P. Frankl and R.M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1(4) (1981), 357-368.

[45] A.J.W. Hilton and E.C. Milner, Some intersection theorems for systems of finite sets, The Quarterly Journal of Mathematics, 18(1) (1967), 369-384.

[46] W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, 58(301) (1963), 13-30.

[47] H. Huang, P. Loh and B. Sudakov, The size of a hypergraph and its matching number, Combinatorics, Probability and Computing, 21(3) (2012), 442-450.

[48] T. Kaiser and M. Stehlik, Edge-critical subgraphs of Schrijver graphs II: The general case, Journal of Combinatorial Theory, Series B, 152 (2022), 453-482.

[49] G. O. H. Katona, Intersection theorems for systems of finite sets, Acta Math-ematica Academiae Scientiarum Hungaricae, 15 (1964), 329-337.

[50] G. O. H. Katona, A theorem of finite sets, Theory of Graphs, Proc. Colloq. Tihany, (1966), 187-207, Akad. Kiado, Budapest, 1968.

[51] P. Keevash, N. Lifshitz, E. Long and D. Minzer, Global hypercontractivity and its applications, arXiv preprint arXiv:2103.04604 (2021).

[52] N. Keller and N. Lifshitz, The Junta Method for Hypergraphs and Chvatal's Simplex Conjecture, arXiv preprint arXiv:1707.02643 (2017).

[53] N. KhadZiivanov, V. Nikiforov, The Nordhaus-Stewart-Moon-Moser inequality, Serdica, 4 (1978) 344-350.

[54] S. Kiselev and A. Kupavskii, Sharp bounds for the chromatic number of random Kneser graphs, Journal of Combinatorial Theory, Series B, 157 (2022), 96-122.

[55] S. Kiselev and A. Kupavskii, Trivial colors in colorings of Kneser graphs, arXiv:2012.14528 (2020).

[56] S. Kiselev and A. Kupavskii, Rainbow matchings in k-partite hypergraphs, Bulletin of the London Mathematical Society, 53(2) (2021), 360-369.

[57] S. Kiselev, A. Kupavskii, O. Verbitsky and M. Zhukovskii, On anti-stochastic properties of unlabeled graphs, accepted at 48th International Workshop on Graph-Theoretic Concepts in Computer Science, arXiv preprint arXiv:2112.04395 (2021).

[58] S.G. Kiselev and A.M. Raigorodskii, On the chromatic number of a random subgraph of the Kneser graph, Doklady Mathematics, 96(2) (2017), 475-476.

[59] D.J. Kleitman, Families of non-disjoint subsets, Journal of Combinatorial Theory, 1 (1966), 153-155.

[60] M. Kneser, Aufgabe 360, Jahresbericht der Deutschen MathematikerVereinigung, 2 (1955), 27.

[61] D. Kolupaev and A. Kupavskii, Erdos Matching Conjecture for almost perfect matchings, arXiv preprint arXiv:2206.01526 (2022).

[62] J. B. Kruskal, The number of simplices in a complex, Mathematical optimization techniques, 10 (1963), 251-278.

[63] A. Kupavskii, On random subgraphs of Kneser and Schrijver graphs, Journal of Combinatorial Theory, Series A, 141 (2016), 8-15.

[64] A. Kupavskii, Random Kneser graphs and hypergraphs, The Electronic Journal of Combinatorics (2018), P4-52.

[65] A. Kupavskii, Diversity of uniform intersecting families, European Journal of Combinatorics, 74 (2018), 39-47.

[66] A. Kupavskii, Rainbow version of the Erdos Matching Conjecture via Concentration, arXiv preprint arXiv:2104.08083 (2021).

[67] A. Kupavskii and D. Zakharov. Regular bipartite graphs and intersecting families, Journal of Combinatorial Theory, Series A, 155 (2018), 180-189.

[68] D.G. Larman and C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1-24.

[69] L. Lovasz, Kneser's conjecture, chromatic number, and homotopy, Journal of Combinatorial Theory, Series A, 25(3) (1978), 319-324.

[70] L. Lovasz, Combinatorial Problems and Exercises, 13.31, Akad. Kiado, Budapest; North-Holland, Amsterdam, 1979.

[71] H. Lu and X. Yu, On rainbow matchings for hypergraphs, SIAM J. Disrete Math. 32(1) (2018), 382-393.

[72] J. Marica and J. Schonheim, Differences of sets and a problem of Graham, Canadian Mathematical Bulletin, 12(5) (1969), 635-637.

[73] J. Matousek, Using the Borsuk-Ulam theorem, Springer, 2003.

[74] J. Matousek, A combinatorial proof of Kneser's conjecture, Combinatorica, 24 (2004), 163-170.

[75] B.D McKay, Asymptotics for symmetric 0-1 matrices with prescribed row sums, Ars Combin., 19 (1985), 15-25.

[76] B.D. McKay and N.C. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2), Combinatorica, 11(4) (1991), 369-382.

[77] M.M. Pyaderkin, Independence numbers of random subgraphs of a distance graph, Mathematical Notes, 99(1) (2016), 312-319.

[78] M.M. Pyaderkin, Independence numbers of random subgraphs of a distance graph, Mathematical Notes, 99(3) (2016), 556-563.

[79] M.M. Pyaderkin, On the stability of some Erdos-Ko-Rado type results, Discrete Mathematics, 340(4) (2017), 822-831.

[80] M. Pyaderkin and A. Raigorodskii, On random subgraphs of Kneser graphs and their generalizations, Doklady Mathematics, 94(2) (2016), 547-549.

[81] A.M. Raigorodskii, Combinatorial geometry and coding theory, Fundamenta Informaticae, 145(3) (2016), 359-369.

[82] A.M. Raigorodskii, The Borsuk problem and the chromatic numbers of some metric spaces, Russian Math. Surveys, 56(1) (2001), 103-139.

[83] C. Reiher, The clique density theorem, Annals of Mathematics (2016), 683707.

[84] V. Rodl, On a Packing and Covering Problem, European Journal of Combinatorics, 6(1) (1985), 69-78.

[85] A.J. Sanders, Covering by intersecting families, Journal of Combinatorial Theory, Series A, 108(1) (2004), 51-61.

[86] A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wiskd., III. Ser., 26 (1978), 454-461.

[87] E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z.27 (1928), 544-548.

[88] J. Spencer, Turan's theorem for k-graphs, Discrete Mathematics, 2 (1972), 183-186.

[89] S.V. Vahrushev, M.E. Zhukovskii, S.G. Kiselev and A.Y. Skorkin Minimum Clique-Free Subgraphs of Kneser Graphs, Doklady Mathematics 102(3), (2020) 472-473.