Семейства множеств с запрещенными конфигурациями и приложения к дискретной геометрии независимости / Families of Sets With Forbidden Configurations and Applications to Discrete Geometry тема диссертации и автореферата по ВАК РФ 05.13.17, доктор наук Купавский Андрей Борисович

• Купавский Андрей Борисович
• доктор наук
• 2019

Оглавление диссертации доктор наук Купавский Андрей Борисович

Contents

Notations

Introduction

1. Intersecting families of sets

1.1. Introduction and statement of results

1.1.1. Stability for the Erdds Ko Rado theorem

1.1.2. Diversity

1.1.3. Counting intersecting families

1.1.4. Product-type inequalities

1.1.5. Cross s

1.1.6. ¿-intersecting, cross s

1.2. Preliminaries

1.2.1. Shifting

1.2.2. Lex order and the Kruskal Katona theorem

1.3. Switchings via regular bipartite graphs and theorems on intersecting families

1.3.1. Cross-intersecting families

1.3.2. Proof of Theorem

1.4. Proof of Theorem

1.5. Diversity for 2k < n < 3k

1.5.1. Intersecting families with the largest diversity are not

shifted

1.6. Counting intersecting families

1.6.1. Cross-intersecting families

1.6.2. Intersecting families

1.7. Product inequalities

1.7.1. Preliminaries

1.7.2. ShortproofofTheoreml.il

1.7.3. Proof of Theorem 1.12 modulo Theorem

1.7.4. Proof of Theorem

1.8. Proof of Theorem

1.8.1. Preliminaries

1.8.2. Proof of Theorem

1.9. ¿-intersecting, cross s

1.9.1. Proof of Theorem

2. Intersecting families of vectors

2.1. Introduction and statement of results

2.1.1. Vectors with a fixed number of +l's and —1

2.1.2. Vectors of fixed length

2.2. Proofs of Theorems 2.5 and

2.2.1. Summary

2.2.2. Comparing the constructions

2.2.3. Auxiliaries from extremal set theory

2.2.3.1. Shifting

2.2.3.2. Shadows

2.2.3.3. General form of Katona's circle method

2.2.3.4. An inequality for cross-intersecting families of

sets

2.2.3.5. Analysis of the Kruskal Katona's Theorem

2.2.3.6. A sharpening of Theorem

2.2.4. Proof of Theorem

2.2.5. Proof of Theorem 2.5 in the case 3k < n < k2

2.3. The proof of Theorem

2.4. Proof of Theorem

2.5. Vectors of fixed length

2.5.1. Simple properties of F(n, k,l)

2.5.2. The case k =

2.5.3. Preliminaries

2.5.4. Proof of Theorems 2.10 and

2.5.5. Proof of Theorem

3. Families with small matching number

3.1. Introduction and statement of results

3.2. Proof of Theorem 3.4 for s >

3.2.1. Averaging over partitions

3.2.2. Calculations

3.2.3. Hilton-Milner-type result for Erdds Matching Conjecturel23

s>5

3.2.5. Proof of Theorem 3.4 (ii), (iii)

3.3. Proof of Theorem 3.4 (i) for s = 3,4

3.3.1. Calculations

s=3

3.3.2.1. The casern < 2,s =

s=4

3.3.4. The casern < 2,s =

k

3.4.1. The proof of (3.55)

3.4.2. The proof of (3.56)

3.4.3. Applications

3.5. Discussion

4. Random Kneser graphs

4.1. Introduction and statement of results

4.1.1. The bounds

4.2. Proof of Theorem

4.2.1. Proof of Theorem

4.3. Proof of Theorem

4.3.1. Basic approach

4.3.1.1. Coloring random subgraphs of blow-ups of hypergraphs

4.3.1.2. Numerical Corollaries for Kneser hypergraphs

4.3.2. The approach refined

4.3.3. Simple lower bounds

5. Coverings and e

5.1. Introduction

5.2. Proof of Theorem 5.3 using Lemma

5.3. Proof of Lemma

5.4. Proof of Theorem

6. Applications to distance problems

6.1. Introduction and statement of results

6.1.1. Borsuk's problem

6.1.2. Distance graphs with high girth

6.2. Borsuk's problem

6.2.1. Proofs of Theorems 6.1 and

6.2.1.1. Construction

6.2.1.2. Transforming Q' into an Q C Srd—1

6.2.1.3. Lower bound for f (Q)

6.2.1.4. Proof of Lemma

6.2.2. Proof of Theorem

6.2.3. Proof of Theorem

6.2.4. Improving Construction from Section 6.2.1.1 is hard . 210 6.3. Distance graphs of high girth

6.3.1. Preliminaries

6.3.2. Proof of Theorem

Bibliography

Введение диссертации (часть автореферата) на тему «Семейства множеств с запрещенными конфигурациями и приложения к дискретной геометрии независимости / Families of Sets With Forbidden Configurations and Applications to Discrete Geometry»

Introduction

Introduction to Extremal Combinatorics.

Extremal combinatorics questions typically ask to maximize a certain function over a class of objects. This is one of possible approaches to analyze a given class of objects, and is different from, say, structural approach, when the goal is to find a compact characterization of the objects belonging to the class. Let us illustrate it on the following two famous results on planar graphs. Recall that a graph is a pair (V, E) where V is a set and E is a collection of pairs of elements from V. A graph is planar if, roughly speaking, one may draw it on the plane without crossing edges.

• One consequence of the famous Euler's formula states that any planar graph with n vertices has at most 3n — 6 edges. This is may be seen as an extremal graph theory result: we upper bound the number of edges in the graphs belonging to a certain class.

•

and only if it does not contain a subdivision of K5 or K3,3 as a subgraph. Without giving definition of a subdivision, this result gives a compact combinatorial characterisation of all planar graphs. Thus, this result belongs to structural graph theory.

These two results (and two ways of thinking about classes of combinatorial objects) complement each other.

Arguably the most famous topic in extremal graph theory is to maximize the number of edges in a graph that does not contain some other graph H as a subgraph. The two most known examples are when H = Kr or Ks,t.

n

bipartite graph with almost equal parts has the largest number of edges

n

Kr

Theorem (Turan). For any fixed r > 3, any n-vertex Kr-free graph has at most (1 — rzj) nr edges.

The number of edges in triangle-free (and Kr-free for any r > 3) graphs is quadratic in n. The situation with the Ks,rfree graphs is very different: if s < t are fixed, then the famous Kovari-Sos-Turan theorem states that any

¿-free graph has at most tn2 1/s edges, which is subquadratic.

Extremal questions are studied for many objects that include hypergraphs or families, words, subsets of integers, collections of vectors, arrangements of points and hyperplanes etc. As an example, the celebrated result of Green and Tao on existence of arbitrarily long arithmetic progressions in primes or, more generally, in dense subsets of integers, is an extremal combinatorics result.

The probabilistic method. In combinatorics, seemingly very different subjects share common methods, and it is sometimes very useful to think about methods, rather than subjects, in combinatorics. There are many methods used in extremal combinatorics: the probabilistic method, the algebraic and eigenvalue methods, the topological methods, the methods of discrete Fourier analysis and the analysis of Boolean functions, the quasirandom method etc. Some of these methods will be discussed later in the introduction.

One of the most important methods, pioneered by P. Erdos, is the probabilistic method. The main principle behind the method is to show that a certain object exists by developing a right probability space and proving that a random object in this space has the desired properties with positive probability, rather than to construct the object explicitly. Let me illustrate it. In coding theory, one is often confronted with the problems of the following type.

Question. How many unit vectors in Rd one may select so that the scalar product of any of them is at most 0.01 ?

It is not easy to provide a good explicit construction. However, one can easily show that there exist cd such vectors with c > 1 using the probabilistic method: it is sufficient to simply choose the vectors at random, bound the

0. 01

a union bound over all such pairs. (To bound the probability, we use the following principle: the surface area of a sphere in high dimension is concentrated around (any) diametral sphere.) One big advantage of probabilistic method is that it is very flexible.

Let us revisit the bound e(G) < 3v(G) — 6, valid for any planar graph. In an attempt to measure the representation complexity of different graphs,

it is a natural question to ask, how many crossing pairs of edges one may expect for the "best" drawing of an n-vertex graph G with e edges on the plane. There is such a bound, called the "crossing lemma", sharp up to a constant factor. In particular, it tells us that the number of crossing pairs of edges in any representation of Kn or Kn,n on the plane is at least Cn4 for some absolute C > 0:

Theorem (Crossing lemma). In any drawing of G with e edges and, v ver-

3

tices, e > 4v7 on the plane, there are at least pairs of crossing edges.

A very short and beautiful proof of this theorem uses probabilistic method.

e

number of crossings (deleting one edge, one deletes at least one crossing, until finally making the graph planar). Using probabilistic method, we can

G

formed by including each vertex of G independently with probability p!

The major inherent drawback of probabilistic method is that it supplies with existential proofs rather than explicit constructions. In some cases, one can deal with it using derandomization, but in most cases there is a big gap between the objects (or algorithms) constructed probabilistically and deterministic constructions. I will illustrate it with an example from a closely related field: Ramsey theory.

Ramsey theory. The underlying principle in Ramsey theory is that in any sufficiently large object one can find a highly structured part. For example, the famous van der Vaerden theorem from 1927 states that, no

2

monochromatic arithmetic progression of length l, for any integer l. However, the theory got its name from a 1930 result1 due to an English logician Ramsey, who proved the following.

Theorem (Ramsey). For any k there exists n, such that in any 2-coloring of the edges of the complete graph Kn one always finds k-vertices, such that

k

can find a monochromatic copy of Kk).

The same result was later rediscovered by Erdds and Szekeres. One may restate it in terms of arbitrary graphs, rather than colorings: for sufficiently large n = n(k), any n-vertex graph contains either a complete graph Kk or

k

1Probably. the first Rariiscy-typc result was proven by Schur in 1913.

plays an important role in computer science. In particular, it is used in the proof of hardness of approximating the chromatic number of graphs. (Recall that the chromatic number of a graph is the minimum number of colors needed to color the vertices so that no edge has monochromatic endpoints. Chromatic number plays important role in many areas of computer science, in particular, in scheduling.)

Naturally, one may ask for the behaviour of n = n(k) in the theorem above. The original proof yields the bound n(k) < 4k. The lower bound of roughly n > 2k was shown by Erdos, again using simple probabilistic method: color each edge of Kn with one of the two colors at random. Then

Kk

than 1 for appropriately chosen parameters. This implies that there exists a

Kk

2k

monochromatic Kk (we may state it as follows: the random graph G(2k, 1/2) does not contain neither a Kk nor an independent set of size k with high probability), it is extremely hard to come up with an explicit construction of such a graph. The best known such construction gives a graph on roughly 2^ vertices with on monochromatic Kk. It is due to Frankl and Wilson, and it is coming from extremal set theory, the field that is in the focus of my dissertation.

Introduction to Extremal Set Theory

Extremal set theory is a field started by Erdos, Kleitman, Sperner and others, which typically searches for the largest systems of sets (families) under certain restrictions. A family is simply a collection of sets.2 Many results and notions from extremal set theory have real-life applications: measuring the complexity of an arrangement of objects, the algorithms for efficient encoding and error-free decoding of information.

Below, I state several key results from the area that motivated my research. One of the first results in the field belongs to Sperner and is as follows.

Theorem (Sperner [ ]). The largest size of a family F C 2[n] such that no F1 G F is strictly contained in F2 £ F, is (^nj).

Any family F with this property is called an antichain, referring to an

2Recall that a pair (V, E), where V is a set of vertices and E is a collection of subsets of E. A hypergraph is k-umform if all sets in E have size k. Thus, a 2-uniform hypergraph is a graph. When the V

that V = [n] := {1,... ,n}.

antichain in the containment order on the poset on 2[n]. The bound is sharp and is attained on the family of all sets of size |_nJ (or n!)• This result has numerous applications, in particular, to the famous Hardy Littlewood problem on the maximum number of distinct sums of numbers ai,... , an > 1

1

Another cornerstone of extremal set theory is the following theorem of Erdds, Ko and Rado, proved in 1938, but published only 23 years later, in 1961. We say that a family is intersecting if any two of its sets intersect.

Theorem (Erdos, Ko, Rado [73]). Any intersecting family F of k-element subsets of [n] has size at most ('—providedn > 2k.

It is tight for a star: a family of all sets containing a fixed element. It has several very different proofs, and many classical extremal set theory methods, such as shifting, cycle method, the eigenvalues method etc. were introduced in these proofs. Its generalizations, such as the famous Frankl Wilson theorem and the Complete ¿-Intersection Theorem due to Ahlswede and Khachatrian, have several applications elsewhere in discrete mathematics and computer science, some of which we will mention in the dissertation.

The following result plays a central role in many applications of extremal set theory to different threshold phenomena in combinatorics and computer science. For a family F of k-element sets, let dF stand for the collection of all (k — 1)-element sets contained in at least one set from F. Recall that (') := 11).'<k|X—'k+1) for any real x > k. The Kruskal-Katona theorem, in the form found by Lovasz, states that

Theorem (Kruskal []; Katona [ ]). Given a family F of k-element sets with |F| = 0 for so me x > k, we ha ve |dF| > J.

In particular, it was used by Bollobas and Thomason [35] to show that monotone properties always have a threshold. It is also directly related to the famous Kahn Kalai Linial theorem [135] from the analysis of Boolean functions.

Let us conclude the introduction to extremal set theory with the Vapnik Chervonenkis Sauer Shelah lemma, which is important in the areas of statistical learning and computational geometry. For a family F C [n], its VC- dimension is the size of the largest subset X C [n], such that X is shattered, that is, {F fl X : F £ F} = 2X. (In plain words, X is shattered if any XX XF

or statistical applications, have bounded VC-dimension. If this is the case,

n

f f F C

[n] has VC-dimension at most d, then |F| < d=0 (n) = O(nd).

This lemma is crucial for proving the existence of small e-nets, which we discuss later in the introduction.

In what follows, I discuss the development of several topics within extremal set theory. These are the topics of this dissertation.

Families with forbidden intersection patterns

The Erdds Ko Rado theorem, stated above, is tight on a full star: the collection of all k-element subsets of [n] containing a given element. Any subfamily of a full star is a star. Erdds, Ko and Rado asked, what is the next largest maximal intersecting family. This question was answered by Hilton and Mil-ner (cf. Theorem 1.3), but more general questions lead to a development of

a whole field of research. One perspective on this field is as follows. The goal

ff

is the largest intersecting family F(d) C ([n]), that is at distance at least d from a star in that "metric". Or, seen from a different perspective, we fix a certain parameter of a family and ask for the largest intersecting family

with this parameter falling in a certain range. Below, I shall discuss several

ff

Frankl [ ] determined the size of the largest intersecting family F C ([n]) in terms of its maximum degree A(F): the maximum over the elements of

F

Zakharov [176], we got a stronger, "dual" version of Frankl's result in terms of diversity y(F), where 7(F) = |F| — A(F). More precisely, we found the largest size of an intersecting family given the lower bound on the Hamming distance from it to the closest star (see Theorem 1.5). Similar, but weaker, stability results were obtained by Keevash and Mubayi, Keevash, Das and Tran, Keevash and Long (see [54, 144, 145, 147]).

Another approach was proposed in the works of Friedgut [115] and Dinur and Friedgut [60] (see Theorem 1.30) and recently greatly developed in the works of Keller, Lifshitz and coauthors (see, e.g. [66, 148]). There, using the machinery of discrete Fourier transform, they proved the following type of results: any intersecting family, up to a small remainder, is contained in an

intersecting junta. Here, a j-junta J is a family such that whether F £ J or not depends on an intersection of F with a fixed set of size at most j. In

1

This type of results has proved to be very useful for different problems in extremal set theory. I will discuss some of them later. I will also mention that this type of results falls in the same framework as, say, the famous Szemeredi regularity lemma: a combinatorial object is decomposed into a highly structured part, a quasirandom part, and a small remainder (for more details, see the paper by Tao [230]). In a recent work with Frankl [106], we have obtained essentially best possible junta approximation results for shifted families (see Section 1.2.1). Without giving precise definitions, this is an extremely important class of families since in many of the extremal set theory problems is sufficient to deal with shifted families.

Another possible "distance" is the covering number t(F) of F, that is, the

F

in the following problem.

Problem. Find the largest intersecting family in with t(F) > t.

For t = 2, the answer is given by the same result of Hilton and Milner, for t = 3,4 and n > no(k) it was solved by Frankl [ ] and Frankl, Ota and Tokushige [109], respectively. In a recent paper [166], I have used a combination of the junta method and the bipartite exchange trick (which

t=3

n > Ck t = 4

However, the case t > 5 remains wide open even for large n.

t=k

classic paper of Erdds and Lovasz [74]. Since each set from an intersecting family F is a cover for the family, we have t (F) < k for any intersecting

family. Erdds and Lovasz showed that the largest size of such a family is at k'

set). Recently, this bound was improved by Frankl [87], but still has the form k(1+o(1))k. The lower bound, due to Frankl, Ota and Tokushige [ ], is roughly (k/2)'.

In the study of intersecting families, it is often very helpful to have some analogous results for several families. We say that families A, B are cross-intersecting, if for any A £ A, B £ B, A and B intersect. The study of cross-intersecting families goes back to the aforementioned work of Hilton and Milner. There are two types of questions that were studied quite extensively:

sum-type inequalities [38, 97, 113, 128, 176], in which the goal is to bound |A| + |B|, given some restrictions on one of the families, and product-type inequalities [ , , ] where the goal is to bound |A||B|. For the first type of inequalities, we refer to Theorem 1.14, and for the second type we refer to Theorem 1.11. We note that the latter theorem, in particular, implies the Erdds Ko Rado theorem.

Of course, one may ask stability-type questions for cross-intersecting families. However, this turns out to be much more difficult. In a recent work [105], we have obtained an analogue of the result of [176] for cross-intersecting families. This is directly related to the question of stability in the Kruskal Katona theorem, which is a much harder question, see [105, 144, 146].

A more general question, addressed by Erdds, Ko, and Rado, is to find tt two sets from the family intersect in at least t elements. If [ ], the authofs have shown that the size of a t-intersecting family in ([n]) is at most Q—1)> provided n > n0(k, t). For n > k > t > 1 and n > 2k — t define

Ai(n, k,t) := j A C : |A n [t + 2i] | > t + i}, 0 < i < k — t.

t

many cases by Frankl and Fiiredi [89], and nearly 20 years later proved in full s f t

family in ([n]) for any n > 2k — t (excluding n = 2k, t = 1) must be isomorphic to one of A(n,k,t). This theorem found an application to the problem of hardness of approximation of vertex cover [61]. Of course, it is natural to ask for the cross-intersecting analogues of this result (cf. [92, 107, 234]), as well as for stability results (cf. [67, 115]).

k

questions for non necessarily uniform families are in general much easier. In particular, it is an easy exercise to show that the largest intersecting family F C 2[n] has size 2n—1\ As for the t-intersecting families, Katona [137] (see

n, t

analogue of k-uniform setting is pbiased setting, in which a set of size £ gets weight — p)n—i and we aim to maximize the sum of weights of sets in a family (cf. [115]). We do not dwell on this since we are mostly concerned k

be, provided no two sets in F intersect in exactly t elements? Recently, a big progress on this question was made by Ellis, Keller and Lifshitz [67], who showed that for any fixed t and a very wide range of k = k(n), the answer to this question is the same as in the theorem of Ahlswede and Khachatrian. In this dissertation, however, I am particularly interested in the case when tn

and Wilson [114] (see Theorem 2.1), which shows that for a certain choice a i n

([n]). Interestingly, this theorem require certain numbers to be prime powers. Without that restriction, the bounds in the theorem are false. However, there is a qualitatively similar result of Frankl and Rodl [111] for a pair of families (cf. its "supersaturation" corollary Theorem 6.10) that, albeit gives worse quantitative bounds, is much more flexible and, in particular, does not have any algebraic restrictions. Recently, Keevash and Long [145] managed to deduce the result of Frankl and Rodl from the result of Frankl and Wilson using the modern probabilistic technique of dependent random, choice.

We have already mentioned one application of the results of Frankl and Wilson: explicit constructions for Ramsey numbers. We are particularly interested in its applications in combinatorial geometry to the problems of finding the chromatic number of Euclidean space and Borsuk's problem. The chromatic number of Rd is the minimum number of colors needed to color all points of Rd so that no two points at unit distance apart receive the same color. This quantity was studied quite extensively (see the surveys [209], [229]).

The result of Frankl and Wilson was a breakthrough for the chromatic number of the space, for the following reasons. One way of looking at families is to associate with each set R C [n] its characteristic vector v(F) := (x1,... , xn) with Xi = 1 for i £ F and xi = 0 for i £ F. Then each family

{0, 1}

section corresponds to one forbidden scalar product, which, given that all vectors have the same length, corresponds to one fixed forbidden distance. Scaling this aisiance to 1, we obtain a finite subset X of Rn (which cor-responas to ([n]))5 f°r which we neea exponential in n number of colors to properly color: the Frankl-Wilson theorem states that any subset X' C X 1t

nX

The situation is similar with Borsuk problem [41], which asks for the minimum number of parts neeaea to partition each boay in Rn of unit aiameter

into parts of strictly smaller diameter. There, using the result of Frankl and

n

bound on the number of parts.

Raigorodskii [209] succeeded in improving the bounds in the aforementioned geometric problems by enlarging the scope of vectors from {0,1}-vectors to {0, ±1}-vectors and proving Frankl-Wilson type theorems for such vectors (see also [48], [162], [195], [205], [209], [215]). Motivated by this, in a series of works [93, 97, 99] I and Frankl initiated systematic studies of intersecting theorems for families of {0, ±1}-vectors. We note here that intersecting theorems were studied for other objects, such as subspaces and permutations, but this is beyond the scope of this dissertation.

Let us return to the first question we have discussed in this section: stability of the Erdds Ko Rado theorem. Another way of looking at stability is by studying the so-called "transference" results in Kneser graphs. Let us first gife some definitions. A Kneser graph KGn,k is a graph witf vertex set ([n]) and edge set formed by all pairs of disjoint sets from ([n]). Note that the Erdds Ko Rado theorem determines the size of the largest independent set in KGn,k. Similarly to the classical random graph model G(n,p) (cf., e.g., [13, 31]), define the random, Kneser graph KGn,k(p) as follows: V(KGn,k(p)) = V(KGn,k) and the set of edges of KGn,k(p) is a subset

of the set of edges of KGn,k, obtained by including each edge from KGn,k

p

Returning to transference, in general, we speak of transference if a certain combinatorial result (with high probability) holds with no changes in the random setting. Studying this phenomenon in the context of the independence number and the chromatic number of generalized Kneser graphs was suggested by Bogolyubskiy et. al. in [28]. One example of such theorem is due to B. Bollobas, B. Narayanan and A. Raigorodskii [33]. They studied the size of maximal independent sets in KGn,k(p), and showed that for a wide range of parameters the if dependence numb er of KGn,k (p) is exactly the same as that of KGn,k: (n—^ • Later on, their result was further strengthened in [19, 54, 59]. Random subgraphs of generalized Kneser graphs were studied in [27, 29, 204, 205, 216].

Finally, let us mention the following surprising (in the words of Erdds) conjecture of Chvatal [ ]. Recall that a down-set is a family G, such that G C F and F G G imply G G G-

Conjecture (Chvatal [ ]). For any down-set G, one of the largest intersecting subfamily F C G is the family of all sets from G containing the element of the largest degree.

Thus, the simple result of Erdds, Ko and Rado stating that the largest intersecting family F C 2[n] has size 2n—1 actually proves the conjecture for G = 2[n]. Chvatal himself proved it for shifted families. Recently, an interesting connection with correlation inequalities was established in [116]. For some further results see [39, 40, 227].

Families with forbidden configurations

We say that a family F has matching number s if s is the maximum number

F1 and for the edge sets of graphs this definition corresponds to the standard notion of a matching. Erdds and Kleitman in the 60;s suggested the following two problems that generalize the Erdds Ko Rado theorem. The first one is as follows.

Problem (Erdds, Kleitman [151]). Determine the size of the largest family F C 2[n] with matching nu mber s.

Kleitman resolved the problem above for n = sm — 1, sm, where m is an integer. Queen [ ] resolved the only remaining case for s = 3: n = 3m +1. For a while, there was no progress. In a recent work with Frankl [94, 101] we managed to resolve this problem in many new cases.

The more famous question on matchings deals with uniform families.

Problem (Erdos Matching Conjecture [71]). The sizr ek(n,s) af the largest family F C with matching number s is max{ (') — (n—'s), (sk+k—^ } •

k=1

k=2

has stimulated a series of papers in graph theory, cf. e.g., the recent paper of Luo [ ]). It was settled in the case k = 3 and n > 4s in [ ], for k = 3, all n and s > s0 in [ ], and, finally, it was completely resolved for k = 3 in [ ]. The case s = 1 is the Erdos-Ko-Rado theorem.

In his original paper, Erdos proved the conjecture for n > n0(k,s). His result was sharpened by Bollobas, Daykin and Erdds [32], who verified it for n > 2k3s. Subsequently, Hao, Loh and Sudakov [ ] proved the EMC for n > 3k2s. Their proof relies in part on the "multipartite version" of the

following universal bound from [80]:

ek(n,s) < s(^ — ^ .

If n = k(s + 1) then the right hand side of the equation above is equal to |A0(s, k)|. For this case, the EMC was implicitly proved by Kleitman [ ] in

sf

Frankl [ ], who showed that ek(n, s) < fk(s+k1)—1) for all n < (s + 1)(k + e), ek

resolved the conjecture for n > (2s + 1)k — s. In a recent work with Frankl 104], we managed to get the current best bound for the EMC: we showed

that it is valid for any s > so and n > |sk — |s.

The Erdôs Matching Conjecture takes a central place in extremal combinatorics and attracted a lot of attention recently, in particular, due to connections with Dirac thresholds, theory on deviations of sums of random variables and some computer science problems. For details, see [8] and [104]. We will just briefly overview the questions on Dirac thresholds. This active area of research in extremal combinatorics stems from the famous Dirac's crin

n/2 contains a Hamilton cycle. The generic question is as follows: what is the condition on the minimum degree3 for a family in order for it to contain a certain spanning (that is, covering the ground set) structure. Probably the most basic structure is a perfect matching, and it turns out that the results for the EMC imply the results on Dirac thresholds for perfect matchings. For details on this connection, we refer to [8, 104], and for more on Dirac thresholds we refer to a recent survey [236].

One may think of intersecting families or families with matching number

s

configuration is 2 disjoint sets, and in the second case it is s + 1 pairwise disjoint sets. One may similarly interpret the other restrictions on intersections. Having this perspective, it is natural to ask, what could we say about other potential forbidden configurations.

The family F C 2[n] is called partition-free if the re are no A,B,C G F satisfying A n B = 0 and C = A U B. Half a century ago Kleitman [ ] proved the following beautiful result.

3We note here that it may be the degree of an element, or a collective degree of a d-tuple of elements, that is, the number of sets from the family containing that d-tuple

Theorem (Kleitman [ ]). Suppose that n = 3m + 1 for some positive m Let T C 2[n] he partition-free. Then

2m+1

|F|< E

t=m+1

He asked, what is the answer for n = 3m, 3m + 2. In a recent work with Frankl [95] we used the methods developed for the first problem from this section and completely resolved this problem. Frankl [87] generalized the

ss

Kleitman [153] considered the following related problem. What is the maximum size u(n) of a family F C 2[/] without three distinct members satisfying A U B = C. The difference with partition-free families is that ane does not require A and B to be disjoint. Kleitman proved u(n) < (|n/2|)(1 + n) for some absolute constant c.

An "abstract" version of this problem was solved by Katona and Tarjan [ ]. Let v(n) denote the maximum size of a family F without three distinct

A, B, C a i A C C B C C that v(2m + 1) = 2(2^.

This result was the starting point of a lot of research. The central problem might be stated as to determine the largest size of subsets of the boolean lattice without a certain subposet. We refer the reader to the survey [122]. One of the important recent advancements in the topic was the result of [192], where the authors showed that for any finite poset there exists a constant C, such that the largesi size of a family without an induced copy of this poset has size at most C (^j) • However, the value of C is unknown in most cases, including the diamond poset: four sets A, B, C, D, where A C B C D, A C C C D.

A structure of completely different spirit was suggested by Chvatal. A d-simplex is a family of d +1 sets that have empty intersection, such that the intersection of any d of them is aonempty. Chvatal conjectured that for d < k < dpin the largest family in not containing a d-simplex is a full star. Recently, great progress in this problem was obtained in [148]. We refer to that paper and the survey [196] for the discussion of a more general class of forbidden configuration problems, called Turdn problems for expansion. The techniques of [148] are based on junta approximations, discussed in the previous section in the context of intersecting families.

Methods

I wanted to survey the methods that were used in the extremal set theory problems mentioned in the previous sections. Most of these methods are employed in this dissertation.

One of the basic methods in extremal set theory is shifting. It is an operation that replaces larger elements by smaller elements (in the sense of natural [n]

is given in Section 1.2.1. It allows to reduce the study of a certain class of extremal set theory problems to the class of shifted families: the families

FG FF Typically one can restrict oneself to shifted families, given that the problem is "monotone": i.e., shifting increases the sizes of minimum intersections, decreases the sizes of unions and the matching numbers, decreases the size of a shadow etc. In a certain sense, shifted families are similar to down-sets (or up-sets). Moreover, there is a similar combinatorial operation to produce down-sets from a family, which is, e.g., used in Frankl's proof of the Vapnik Chervonenkis Sauer Shelah lemma.

Shifting is particularly efficient if combined with induction: one would often decompose a shifted family into two families, typically all the sets containing x and all the sets not containing x, where x is either the first or the last element, and then apply inductive hypothesis plus the properties on these two families combined with shiftedness. One of the most beautiful examples of proofs of this kind is Frankl's proof of the Kruskal Katona theorem [79]. The limitation of this approach is that it is difficult/impossible to apply for subtler problems, such as forbidden one intersection, or when we impose additional restrictions on the family (such as not being a star).

Another classical extremal combinatorics method is Katona's circle method. It gained its name from the proof for the Erdds Ko Rado theorem, given by Katona [139]. The idea of that proof was as follows: fix a permutation and kk n

at most k can belong to an intersecting family F (which is a k/n-fraction n

k/n

F

More generally, one can fix more elaborate structures over which one av-

erages. This approach eventually allowed us to progress in the questions on

s

[94, 95]. The main difficulty (and the limitation of the method) is to choose a structure over which one averages: it should be sufficiently simple to analyze and it should capture the features of the problem. For example, the best known bound for the EMC that is obtained using this approach is the inequality displayed in the previous section. We simply do not know of any good configuration that could possibly give the correct bound.

The Kruskal Katona theorem itself is a very strong tool in extremal combinatorics. E.g., this is the main ingredient in proving that any monotone property has a threshold [35]. Here we only focus on its applications to intersecting and cross-intersecting families. Thanks to the Kruskal Katona theorem, some questions may be reduced to the so-called lexicographical families, i.e., families consisting of the initial segment of sets in the lexicographical order (for the precise statement, cf. Section 1.2.2). Thus, one may restrict to a very small and quite well-understood class of families. However, in many cases (e.g., in proving stability results) such reduction would potentially destroy certain other properties. For this purpose, one may employ certain exchange operations, which would transform any given family into a lexicographical family gradually (which allows to have better control of some parameters). One such operation, generalizing shifting, was found by Daykin [55], and another one was developed by myself and Zakharov [176].

The methods we have discussed so far work for any values of parameters n, k

being very powerful, works for n > n0(k) only. Erdos and Rado showed that in any sufficiently large family of k-sets there is a sunflower with t petals: sets F1,..., Ft, such that Uie[i]Fi = Fj R F/ for any j, l G [t]. The common intersection of all the sets in the sunflower is called a core. The method works

F

F

F

contains an element of the core, and it is easy to see that the vast majority

F2 left to understand the possible structure of the family of cores of small size 2

of Frankl (see, e.g., [78]).

Another method, which we have already discussed above, is the so-called junta method. The idea is to approximate a family with given properties by a j-junta with the same properties, where j-junta is a family that depends on at most j coordinates, called the center of the junta. Once such an approximation is obtained, one may again argue that most sets would intersect the center in few coordinates, and then, as in the case with the Delta-system method, it is sufficient to find the optimal arrangement of small sets. Here, as in the case with the Delta-system method, stability results play a crucial role: one first gets that the approximating junta must have a specific form, and then uses the result that states that such junta is "locally optimal". We refer to a recent paper of Keller and Lifshitz [148] for some general juntatype results. This method is applicable forn > Ck, where C is independent k

Conjecture, it depends on s. Thus, it has a wider range of applicability than

n

Long, and Minzer are currently working on junta-type results that would be applicable for n > Csk with C, independent of s.

Finally, let us say a couple of words about the algebraic methods. One of the methods is the eigenvalue method. One potential application goes as follows: interpret a family with a certain property as an independence set in a certain graph (e.g., for intersecting families, the relevant graph is the Kneser graph), and then use Hoffman's bound for the largest independent set in terms of eigenvalues of the adjacency matrix. Thus, one requires to find the eigenvalues. This approach works for all values of parameters, however, it is often very difficult to find the right interpretation of the problem, so that the bound would be sharp, and/or to find the eigenvalues/eigenspaces. The examples include the proof of the Erdds Ko Rado theorem (cf. Lovasz' famous paper [ ] and Wilson's result [ ] on ¿-intersecting families. More advanced applications use Delsarte's linear programming bound.

Frankl and Wilson's result [114] is most conveniently proved using polynomial method. The idea behind the method is to associate polynomials with each set in the family, and, using the restricted intersections property, show that these polynomials are independent over a certain field. Then, one bounds the size of the family by the dimension of the space of the polynomials (taking into account the possible monomials that may have appeared). We refer to an unfinished book of Babai and Frankl [17] for a systematic

4The presence of any set is determined by its intersection with a fixed set of size at most j.

treatment of this topic. e

Extremal set theory has important applications in computational geometry

e

Let X be a finite set and let F be a system of subsets of an X. The pair (X, F) is usually called a range space. A subset X' C X is called an e-net for (X, F) if X'nF = 0 for every F £ F with at least e|X| elements. (In words, e

e

technique in discrete and computational geometry, with many combinatorial

e

provably capture the most important quantitative and qualitative properties that one would expect from a random sample. Typical applications include the existence of spanning trees and simplicial partitions with low crossing number, upper bounds for discrepancy of set systems, LP rounding, range searching, streaming algorithms; see [187, 201].

A remarkable result due to Haussler and Welzl, based on a ground-breaking work of Vapnik and Chervonenkis [ ], states that if VC(F) < d then the minimum size of an e-net is O(d log1). It was shown by Komlos, Pach, and Woeginger that this bound is essentially tight for random range spaces. Over the past two decades, a number of specialized techniques have been devele

range spaces [15, 16, 45, 46, 47, 50, 155, 186, 190, 198, 207, 232, 233]. Based on these successes, it was generally believed that in most geometric scenarios one should be able to substantially strengthen the e-net theorem, and obtain perhaps even a O( 1) upper bound for the size of the smallest e-nets. Similar questions were raised in the statistical learning community. However, in

e

range spaces induced by points and lines In a recent breakthrough, Balogh and Solymosi [22] applied the recently developed container method (coming from extremal combinatorics) to give the lower bound of 1 log1/3—o(1) 1)

e

Shortly after Alon's paper [5], Pach and Tardos [202] constructed a range space induced by points and halfspaces in R4 with the smallest e-net of (the worst possible) size 1 log 1).

On the other hand, following the work of Clarkson and Varadarajan [50], it

has been gradually realized that if one replaces the condition that the range space (X, R) has bounded VC-dimension by a more refined combinatorial property, one can prove the existence of e-nets of size o( 1 log 1). This lead to the introduction of the new complexity measure: shallow cell complexity (cf. the definition in Chapter 5). A series of elegant results [15, 46, 197, 233] illustrate that if the shallow-cell complexity of a set system is ^(n) = o(n),

ee

The questions studied in the dissertation

In this dissertation, we address the following questions.

• How stable is the Erdos-Ko-Rado theorem? More precisely, how large could an intersecting family be in terms of its distance from the closest star?

•s

be?

theorems for families of {0, ±1}-vectors?

•s

kind of structure does it have?

Matching Conjecture?

graphs behave?

•e

spaces in Rd?

•e

complexity of a range space?

conjecture?

large cliques or large girth?

The structure of the dissertation

The dissertation consists of the Introduction chapter, 6 chapters in which I present my results, and a bibliography of 237 items.

In Chapter 1, I present the results on families and pairs of families with restricted intersections. In Chapter 2, I present the restricted intersections-type results for the families of {0, ±1}-vectors. In Chapter , I present my

s

results on random Kneser graphs and hypergraphs. In Chapter 5, I present

e

present the applications of extremal set theory to the combinatorial geometry problems: the chromatic number of the space and Borsuk's problem.

Each of the chapters has its own introduction, in which the area is surveyed and the main results are stated. The proofs are presented in the later sections.

The main results of the dissertation

secting family in terms of its distance from the closest star (diversity).

• I have shown that the diversity of an intersecting family is at most (/I3), provided n > Ck.

• I have showed that a typical intersecting family is a star, provided n > 2k + 2Vk log k.

•

Khachatrian theorems for families of {0, ±1}-vectors.

s

very powerful averaging method. Conjecture.

that it stays almost the same as the chromatic number of Kneser graphs in many scenarios.

•e

paces in has size d log1) in the worst case, thus giving a conclu-

sive answer to the question on whether the geometric range spaces are simpler then abstract range spaces.

• I have obtained sharp lower bounds on the smallest e-nets for range spaces as a function of their shallow cell complexity.

lying on the spheres of radius arbitrarily close to 1/2.

mension chromatic number and with large girth.

My stability result for the Erdds Ko Rado theorem has already found applications in the studies of intersecting families (some of which are presented here), and we believe that it would find more. More generally, the bipartite switching trick that I have introduced seems to be a powerful tool.

The situation is similar with the stability result for the Erdds Matching Conjecture. In the paper [102], we have applied it to advance on an anti-Ramsey type problem. The averaging technique I developed for Kleitman's problem on families with matching number s is very powerful and should find applications elsewhere, in particular, for problems on forbidden subposets. e

ing: in a work with Csikos and Mustafa, [52], we proved that the construction given in [168] allows to resolve a long-standing question on the VC-dimension of a k-fold union FUk of range spaces defined by halfspaces. The notion of shallow cell complexity seems to be very useful in different areas where random sampling is employed, and it is of importance to understand the strength and the limitations of this measure.

Finally the extremal set theory techniques that I introduced in studying distance problems enhance the connections between these two areas and should open the possibilities for some new applications.

Список литературы диссертационного исследования доктор наук Купавский Андрей Борисович, 2019 год

Bibliography

[1] R. Ahlswede and L. Khachatrian, The complete intersection theorem for systems of finite sets, Eur. J. Comb. 18 (1997), N2, 125-136.

[2] P. K. Agarwal, J. Pach, and M. Sharir, State of the union (of geometric objects): A review, In J. Goodman, J. Pach, and R. Pollack (Eds.) Computational Geometry: Twenty Years Later, Amer. Math. Soc. (2008), 9 48.

[3] P. Agarwal and M. Sharir, The Number of Congruent Simplices in a Point Set, Disc. Comput. Geom. 28 (2002), N2, 123-150.

[4] M. Alishahi and H. Hajiabolhassan, Chromatic Number of Random Kneser Hypergraphs, J. Comb. Theory Ser. A 154 (2018), 1-20.

[5] N. Alon, A Non-linear Lower Bound for Planar Epsilon-nets, Disc. Comput. Geom. 47 (2012), N2, 235-244.

[6] N. Alon, L. Babai, and H. Suzuki, Multilinear polynomials and Frankl - Ray-Chaudhuri - Wilson type intersection theorems, J. Comb. Theory Ser. A 58 (1991), 165-180.

[7] N. Alon, L. Drewnowski, and T. Luczak, Stable Kneser hypergraphs and ideals in N with the Nikodym property, Proc. Amer. Math. Soc. 137 (2009), N2, 467-471.

[8] N. Alon, P. Frankl, H. Huang, V. Rodl, A. Rucihski, and B. Sudakov, Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels, J. Comb. Theory Ser. A 119 (2012), 1200-1215.

[9] N. Alon, P. Frankl, and L. Lovasz, The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc., 298 (1986), N1, 359-370.

[10] N. Alon and A. Kupavskii, Two notions of unit distance graphs, Proceedings of the Seventh European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2013), J. Nesetril, Jaroslav, M. Pellegrini (Eds.) (2013), 105-110.

[11] N. Alon and A. Kupavskii, Two notions of unit distance graphs, J. Comb. Theory Ser. A 125 (2014), UJ-17.

[12] N. Alon, G. Moshkovitz, and N. Solomon, Traces of Hypergraphs (2018), arXiv:1804.10717.

[13] N. Alon and J. Spencer, The probabilistic method, Third Edition, John Wiley & Sons (2004).

[14] G.E. Andrews and K. Eriksson, Integer partitions, Cambridge University Press (2004).

e

rectangles and boxes, SIAM J. Comput. 39 (2010), N7, 3248-3282.

[16] P. Ashok, U. Azmi, and S. Govindarajan, Small strong epsilon-nets, Comput. Geom. 47 (2014), N9, 899-909.

[17] L. Babai and P. Frankl, Linear algebra methods in combinatorics, Part 1, Department of Computer Science, The University of Chicago, Preliminary version 2, September 1992.

[18] R.C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes, If Proc. London Math. Soc., 83 (2001), 532-562.

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

[20] J. Balogh, S. Das, M. Delcourt, H. Liu, and M. Sharifzadeh, Intersecting families of dicrete structures are typically trivial\ J. Comb. Theory Ser. A 132 (2015), 224-245.

[21] J. Balogh, S. Das, H. Liu, M. Sharifzadeh, and T. Tran, Structure and supersaturation for intersecting families (2018), arXiv:1802.08018.

[22] J. Balogh and J. Solymosi, On the number of points in general position in the plane, Discrete Analysis (2018), 16, 20pp.

[23] I. Barany, A short proof of Kneser's conjecture, J. Comb. Theory Ser. A 25 (1978), N3, 325-326.

[24] M. Benda and M. Perles, Colorings of metric spaces, Geombinatorics 9 (2000), 113-126.

[25] A. Bjorner and G. Kalai, An extended Euler-Poincare theorem, Acta Math. 161 (1988), N1, 279-303.

[26] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, J. ACM 36 (1989), N4, 929965.

[27] A. Bobu, A. Kupriyanov and A.M. Raigorodskii, On chromatic numbers of nearly Kneser distance graphs, Dokl. Math. 93 (2016), N3, 267-269.

[28] 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 Math 90 (2014), N1, 462-465.

[29] 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, Sbornik Math. 206 (2015), N10, 1340 1374.

[30] B. Bollobas, On generalized graphs, Acta Math. Acad. Sci. Hungar. 16 (1965), 447-452.

[31] B. Bollobas, Random Graphs, Cambridge University Press, Second Edition (2001).

[32] B. Bollobas, D.E. Daykin, and P. Erdos, Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser. 27 (1976), N2, 25-32.

[33] B. Bollobas, B.P. Narayanan, and A.M. Raigorodskii, On the stability of the Erdos Ko Rado theorem, J. Comb. Theory Ser. A 137 (2016), 64-78.

[34] B. Bollobas and I. Leader, Set Systems with few Disjoint Pairs, Combi-natorica 23 (2003), N4, 559-570.

[35] B. Bollobas and A.G. Thomason, Threshold functions, Combinatorica 7 (1987), N1, 35-38.

[36] V.G. Boltyanski, H. Martini, and P.S. Soltan, Excursions into combinatorial geometry, Universitext, Springer (1997).

[37] A. Bondarenko, On Borsuk's Conjecture for Two-Distance Sets, Disc. Comput. Geom. 51 (2014), N3, 509-515.

[38] P. Borg, Intersecting and cross-intersecting families of labeled sets, Electron. J. Comb., 15 (2008), paper 9.

[39] P. Borg, Extremal t-intersecting sub-families of hereditary families, J. London Math. Soc. 79 (2009), 167-185.

[40] P. Borg, Non-trivial intersecting uniform sub-families of hereditary families, Disc. Math. 313 (2013), N17, 1754-1761.

[41] K. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fund. Math. 20 (1933), 177-190.

[42] J. Bourgain, J. Lindenstrauss, On covering a, set in by balls of the same diameter, Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.), Lecture Notes in Math. 1469, SpringerVerlag, Berlin (1991), 138-144.

[43] P. Brass, W. Moser, and J. Pach, Research problems in discrete geometry, Springer, Berlin (2005).

[44] N. G. de Bruijn and P. Erdos, A colour problem for infinite graphs and a problem in the theory of relations, Nederl. Akad. Wetensch. Proc. Ser. A 54 (1951), 3711,1-373.

[45] N. Bus, S. Garg, N. H. Mustafa, and S. Ray, Tighter estimates for epsilon-nets for disks, Comput. Geom. 53 (2016), 27-35.

[46] T. M. Chan, E. Grant, J. Könemann, and M. Sharpe, Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling, In Proceedings of Symposium on Discrete Algorithms (SODA) (2012), 1576-1585.

[47] B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990), N3, 229-249.

[48] D.D. Cherkashin and A.M. Raigorodskii, On the chromatic numbers of small-dimensional spaces, Doklady Math. 95 (2017), N1, 5-6.

[49] V. Chvätal, Intersecting families of edges in hypergraphs having the hereditary property, in Hypergraph Seminar 411, C. Berge and D. Ray-Chaudhuri, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg (1974), 61-66.

[50] K. Clarkson and K. Varadarajan. Improved approximation algorithms for geometric set cover, Disc. Comput. Geom. 37 (2007), 43-58.

[51] K. L. Clarkson and P. W. Shor, Application of random sampling in computational geometry, //, Disc. Comput. Geom. 4 (1989), 387-421.

[52] M. Csikös, A. Kupavskii, and N. Mustafa, Optimal bounds on the VC-dimension, arXiv: 1807.07924

[53] S. Das, W. Gan, and B. Sudakov, The minimum number of disjoint pairs in set systems and related problems, Combinatorica 36 (2016), 623-660.

[54] S. Das and T. Tran, Removal and Stability for Erdos-Ko-Rado, SIAM J. Disc. Math. 30 (2016), 1102-1114.

[55] D. E. Daykin, A Simple Proof of the KruskalflKatona, Theorem, J. Com-bin. Theory Ser. A 17 (1974), 252-253.

[56] D.E. Daykin, Erdos-Ko-Rado from Kruskal-Katona, J. Comb. Theory Ser. A 17 (1974), 254-255.

[57] E.E. Demechin, A.M. Raigorodskii, and O.I. Rubanov, Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size, Sbornik: Mathematics 204 (2013), N4, 508-538.

[58] M. Deza and P. Frankl, Every large set of equidistant (0, +1, — 1)-vectors forms a sunflower, Combinatorica 1 (1981), 225-231.

[59] P. Devlin and J. Kahn, On "stability" in the Erdos-Ko-Rado Theorem, SIAM J. Disc. Math. 30 (2016), 1283-1289.

[60] I. Dinur and E. Friedgut, Intersecting families are essentially contained in juntas, Comb. Probab. Comput. 18 (2009), 107-122.

[61] I. Dinur and S. Safra, On the hardness of approximating minimum vertex-cover, Ann. Math. 162 (2005), 4391,1-485.

[62] V.L. DolYnikov, Transversals of families of sets, in Studies in the theory of functions of several real variables (in Russian), Yaroslav. Gos. Univ., Yaroslaviy, 109 (1981), 30-36.

[63] P. O'Donnell, Arbitrary girth, J^-chromatic unit distance graphs in the plane I. Graph embedding, Geombinatorics, 9 (2000), 180-193.

[64] P. O'Donnell, Arbitrary girth, J^-chromatic unit distance graphs in the plane II. Graph description, Geombinatorics, 9 (2000), 145-152.

[65] R. OYDonnell, Analysis of boolean functions, Cambridge University Press, New York, NY (2014).

[66] D. Ellis, N. Keller, and N. Lifshitz, Stability versions of Erdosfl-Ko-flRado type theorems, via isoperimetry, arXiv:1604.02160 (2016).

[67] D. Ellis, N. Keller, and N. Lifshitz, Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem, of Erdos and Sos, arXiv:1604.06135 (2016).

[68] P. Erdos, Graph, theory and, probability, Canad. J. Math. 11 (1959), 34 38.

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

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

[71] P. Erdos, Unsolved Problems, Congres Numerantium XV - Proceedings of the 5th British Comb. Conf. 1975 (1976), p. 681.

[72] P. Erdos and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337-356.

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

[74] P. Erdos and L. Lovasz, Problems and results on 8-chromatic hyper-graphs and some related questions, Infinite and finite sets 10 (1975), N2, 609-627.

[75] J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl, A semi-algebraic version of Zarankiewicz's problem, J. Eur. Math. Soc. 19 (2017), N6, 1785-1810.

[76] P. Frankl, The Erdos-Ko-Rado theorem is true for n—ckt, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, 365-375, Colloq. Math. Soc. Janos Bolyai, 18, North-Holland.

[77] P. Frankl, Families of finite sets containing no k disjoint sets and their union, Periodica Mathematica Hungarica 8 (1977), N1, 29-31.

[78] P. Frankl, On intersecting families of finite sets, Bull. Austral. Math. Soc. 21 (1980), 363-372.

[79] P. Frankl, A new short proof for the KruskaFKatona theorem, Disc. Math. 48 (1984), N2-3, 327-329.

[80] P. Frankl, The shifting technique in extremal, set theory, Surveys in combinatorics, Lond. Math. Soc. Lecture Note Ser. 123 (1987), 81 110, Cambridge University Press, Cambridge.

[81] P. Frankl, Erdos Ko Rado theorem with conditions on the maximal degree, J. Comb. Theory Ser. A 46 (1987), N2, 252 263.

[82] P. Frankl, On cross-intersecting families. Disc. Math. 108 (1992), 291 295.

[83] P. Frankl, Improved bounds for Erdos Matching Conjecture, J. Comb. Theory Ser. A 120 (2013), 1068 1072.

[84] P. Frankl, Antichains of fixed diameter., Moscow Journal of Combinatorics and Number Theory 7 (2017), N3.

[85] P. Frankl, Proof of the Erdos matching conjecture in a new range, Isr. J. Math. 222 (2017), N1, 421 430.

[86] P. Frankl, On the maximum number of edges in a hypergraph with given matching number, Disc. Appl. Math. 216 (2017), 5621,1-581.

[87] P. Frankl, A near exponential improvement on a bound of Erdos and Lovasz, preprint, https://users.renyi.hu/~pfrankl/2017-4. pdf (2017).

[88] P. Frankl and Z. Fiiredi, Non-trivial intersecting families, J. Comb. Theory Ser. A 41 (1986), N1, 150 153.

[89] P. Frankl and Z. Fiiredi, Beyond the Erdos Ko Rado theorem, J. Comb. Theory Ser. A 56 (1991) N2, 182 194.

[90] P. Frankl and R.L. Graham, Old and new proofs of the Erdos Ko Rado theorem, Sichuan Daxue Xuebao 26 (1989), 112 122.

[91] P. Frankl and A. Kupavskii, A size-sensitive inequality for cross-intersecting families, Eur. J. Comb. 62 (2017), 263 271.

[92] P. Frankl and A.B. Kupavskii, Uniform s-cross-intersecting families, Combin. Probab. Comput. 26 (2017), N4, 517 524.

[93] P. Frankl and A. Kupavskii, Intersection theorems for {0, ±1}-vectors and s-cross-intersecting families, Moscow Journal of Combinatorics and Number Theory 7 (2017), N2, 91 109.

[94] P. Frankl and A. Kupavskii, Families with no s pairwise disjoint sets, J. London Math. Soc. 95 (2017), N3, 875-894.

s

tron. Notes Disc. Math. 61 (2017), 483-489.

[96] P. Frankl and A. Kupavskii, A short proof for an extension of the Erdos-Ko-Rado Theorem, in Proceedings of Connections in Discrete Mathematics conference, Cambridge University Press (2018), 169-172.

[97] P. Frankl and A. Kupavskii, Erdos-Ko-Rado theorem for {0±1}-vectors, J. Comb. Theory Ser. A 155 (2018), 157-179.

[98] P. Frankl and A. Kupavskii, Counting intersecting and pairs of cross-intersecting families, Comb. Probab. Comput. 27 (2018), N1, 60-68.

[99] P. Frankl and A. Kupavskii, Families of vectors without antipodal pairs, Studia Sci. Math. Hungarica 55 (2018), N2, 231-237.

[100] P. Frankl and A. Kupavskii, New inequalities for families without k pairwise disjoint members, J. Comb. Theory Ser. A 157 (2018), 427434.

[101] P. Frankl and A. Kupavskii, Families of sets with no matching of sizes 3 and 4, Eur. J. Comb. 75 (2019), 123-135.

[102] P. Frankl and A. Kupavskii, Two problems on matchings in set families — in the footsteps of Erdos and Kleitman, accepted at J. Comb. Theory Ser. B, arXiv:1607.06126

[103] P. Frankl and A. Kupavskii, Partition-free families of sets, accepted at Proc. London Math. Soc., arXiv:1706.00215

[104] P. Frankl and A. Kupavskii, The Erdos Matching Conjecture and Concentration inequalities, arXiv: 1806.08855

[105] P. Frankl and A. Kupavskii, Diversity, arXiv:1811.01111

[106] P. Frankl and A. Kupavskii, Simple juntas for shifted families, preprint

[107] P. Frankl, S. J. Lee, M. Siggers, and N. Tokushige, An Erdos-Ko-Rado theorem for cross t-intersecting families, J.Comb. Theory Ser. A 128 (2014), 207-249.

[108] P. Frankl, T. Luczak, and K. Mieczkowska, On matchings in hyper-graphs, Electron. J. Comb. 19 (2012), Paper 42.

[109] P. Frankl, K. Ota, and N. Tokushige, Uniform intersecting families with covering number four, J. Comb. Theory Ser. A 71 (1995), 127-145.

[110] P. Frankl, K. Ota, and N. Tokushige, Covers in uniform intersecting families and a counterexample to a conjecture of Lovasz, J. Comb. Theory Ser. A 74 (1996), 33-42.

[111] P. Frankl and V. Rodl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), N1, 259-286.

[112] P. Frankl, V. Rodl and A. Ruciriski, On the Maximum Number of Edges in a Triple System Not Containing a Disjoint Family of a Given Size, Combinatorics, Probability and Computing 21 (2012), N1-2, 141-148.

[113] P. Frankl and N. Tokushige, Some best possible inequalities concerning cross-intersecting families, J. Comb. Theory Ser. A 61 (1992), N1, 87-97.

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

[115] E. Friedgut, On the measure of intersecting families, uniqueness and stability, Combinatorica 28 (2008), 503-528.

[116] E. Friedgut, J. Kahn, G. Kalai, and N. Keller, ChvdtaFs conjecture and correlation inequalities, J. Comb. Theory Ser. A 156 (2018), 22-43.

[117] E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), N10, 2993-3002.

[118] Z. Fiiredi and J.R. Griggs, Families of finite sets with minimum shadows, Combinatorica 6 (1986), 355-363.

[119] E.S. Gorskaya, I.M. Mitricheva, and V.Yu. Protasov, A.M. Raigorod-skii, Estimating the chromatic numbers of Euclidean spaces by methods of convex minimization, Sbornik Math. 200 (2009), N6, 783-801.

[120] J.E. Greene, A new short proof of Kneser's conjecture, Amer. Math. Monthly 109 (2002), N10, 918-920.

[121] A. de Grey, The chromatic number of the plane is at least 5, arXiv: 1804.02385 (2018).

[122] J.R. Griggs, W.T. Li, Progress on poset-free families of subsets, Recent Trends in Combinatorics, Springer International Publishing (2016), 317— 338.

[123] B. Grünbaum, Borsuk/s problem, and related questions, Proc. Symp. Pure Math. 7 (1963), 271 284.

[124] H. Hadwiger, Uberdeckung einer Menge durch Mengen kleineren Durchmessers, Comm. Math. Helv. 18 (1945/46), 73-75; Mitteilung betreffend meine Note: Uberdeckung einer Menge durch Mengen kleineren Durchmessers, Comm. Math. Helv. 19 (1946/47), 72-73.

[125] P. Hall, On Representatives of Subsets, J. London Math. Soc. 10 (1935), N1, 26 30.

[126] D. Haussler and E. Welzl, e-nets and simplex range queries, Disc. Corn-put. Geom. 2 (1987), 127 151.

[127] A.J.W. Hilton, The Erdos Ko Rado theorem with valency conditions, (1976), unpublished manuscript.

[128] A.J.W. Hilton and E.G. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford 18 (1967), 369 384.

[129] H. Huang, Two problems on intersecting families, Eur. J. Comb. 76 (2019), 1IJ-9.

[130] H. Huang, P. Loh, and B. Sudakov, The size of a hypergraph and, its matching number, Combin. Probab. Comput. 21 (2012), 442 450.

[131] F. Jaeger and C. Payan, Nombre maximal d/aretes d/un hypergraphe critique de rang /?., CR Acad. Sei. Paris 273 (1971), 221 223.

[132] T. Jenrich and A. Brouwer, 64-Dimensiona,l Counterexample to Borsuk/s Conjecture, Electron. J. Comb. 21 (2014), N4, paper 4.29.

[133] H.W.E. Jung, Uber die kleinste Kugel, die eine räumliche Figur ein-schliesst, J. reine und angew. Math. 123 (1901), 241 257.

[134] J. Kahn and G. Kalai, A counterexample to Borsuk/s conjecture, Bull. Amer. Math. Soc. 29 (1993), 60 62.

[135] J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions, Proc. 29th Annual Symposium on Foundations of Computer Science (FOGS) (1988), 68 80.

[136] G. Kalai, A post on MathOverflow, https://mathoverflow.net/ questions/105086/kahn-kalai-linial-for-intersecting-upsets

[137] G.O.H. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hung. 15 (1964), 329-337.

[138] G.O.H. Katona, A theorem of finite sets, Theory of Graphs, Proc. Coll. Tihany (1966), Akad, Kiado, Budapest (1968); Classic Papers in Combinatorics (1987), 381-401.

[139] G.O.H. Katona, A simple proof of the ErdosflKoflRado Theorem, J. Comb. Theory Ser. B 13 (1972), 183-184.

[140] G.O.H. Katona, Extremal problems for hypergraphs, Combinatorics, Mathematical Centre Tracts 56 (1974), Part 2, 13-42.

[141] G.O.H. Katona, Solution of a problem of A. Ehrenfeucht and J. My-cielski, J. Comb. Theory Ser. A 17 (1974), N2, 265-266.

[142] G.O.H. Katona, The cycle method and its limits, in: Numbers, Information and Complexity (I. Althofer, Ning Cai, G. Dueck, L. Khachatrian, M.S. Pinsker, A. Sarkozy, I. Wegener, Zhen Zhang, eds.), Kluwer (2000), 129-141.

[143] G.O.H. Katona, T. Tarjan, Extremal problems with excluded subgraphs in the n-cube, Graph Theory, Lagow (1981), Lecture Notes in Math. 1018 (Springer-Verlag, Berlin, 1983) 84-93.

[144] P. Keevash, Shadows and intersections: Stability and new proofs, Advances in Mathematics 218 (2008), N5, 1685-1703.

[145] P. Keevash and E. Long, Frankl-Rddl type theorems for codes and permutations, arXiv:1402.6294vl

[146] P. Keevash and E. Long, Stability for vertex isoperimetry in the cube (2018) arXiv:1807.09618

[147] P. Keevash and D. Mubayi, Set systems without a simplex or a cluster; Combinatorica 30 (2010), N2, 175-200.

[148] N. Keller and N. Lifshitz, The junta method for hypergraphs and the Erdos-Chvatal simplex conjecture (2017), arXiv: 1707.02643

[149] S. Kiselev and A. Kupavskii, Sharp bounds for the chromatic number of random Kneser graphs and hypergraphs, arXiv:1810.01161

[150] D. Kleitman, On a combinatorial conjecture of Erdos, J. Comb. Theory 1 (1966) 209-214.

[151] D.J. Kleitman, Maximal number of subsets of a finite set no k of which are pairwise disjoint, J. Comb. Theory 5 (1968), 157-163.

[152] D.J. Kleitman, On families of subsets of a finite set containing no two disjoint sets and their union, J. Combin. Theory 5 (1968), N3, 235-237.

[153] D.J. Kleitman, Extremal properties of collections of subsets containing no two sets and their union, Journal of Combinatorial Theory, Series A 20 (1976), N3, 390-392.

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

[155] J. Komlös, J. Pach, and G. J. Woeginger, Almost tight bounds for epsilon-nets, Disc. Comput. Geom. 7 (1992), 163-173.

[156] D. König, Grafok es matrixok, Matematikai es Fizikai Lapok 38 (1931), 116-119.

[157] I. Kriz, Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc. 333 (1992), 567-577.

[158] I. Kriz, A correction to 'Equivariant cohomology and lower bounds for chromatic numbers" (Trans. Amer. Math. Soc. 333 (1992), 567-577), Trans. Amer. Math. Soc. 352 (2000), N4, 1951-1952.

[159] J.B. Kruskal, The Number of Simplices in a Complex; Mathematical optimization techniques 251 (1963), 251-278.

[160] A. Kupavskii, On the coloring of spheres, embedded in Rn, Sbornik: Mathematics 202 (2011), N6, 859-886.

[161] A. Kupavskii, Distance graphs with large chromatic number and arbitrary girth, Moscow Journal of Combinatorics and Number Theory 2 (2012), N2, 52-62.

[162] A. Kupavskii, Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers, Izvestiya: Mathematics 78 (2014), N1, 59-89.

[163] A. Kupavskii, On random subgraphs of Kneser and Schrijver graphs, J. Comb. Theory Ser. A 141 (2016), 8-15.

[164] A. Kupavskii, Diversity of uniform, intersecting families, Eur. J. Comb. 74 (2018), 39-47.

[165] A. Kupavskii, Random Kneser graphs and hypergraphs, Electron. J. Comb. 25 (2018), N4, paper 4.52.

[166] A. Kupavskii, Structure and properties of large intersecting families, arXiv:1810.00920 (2018).

[167] A. Kupavskii, Degree versions of intersection theorems, arXiv:1810.00915 (2018).

[168] A.B. Kupavskii, N. Mustafa, and J. Pach New lower bounds for e-nets, In Proceedings of Symposium on Computational Geometry (SOCG) (2016), 54:1-54:16.

[169] A. Kupavskii, N. Mustafa, and J. Pach, Near-Optimal Lower Bounds

e

Through Discrete Mathematics. Springer, Cham (2017), 527-541.

[170] A. Kupavskii and A.M. Raigorodskii, Counterexamples to Borsuk's conjecture on spheres of small radii, Moscow Journal of Combinatorics and Number Theory 2 (2012), N4, 27-48.

[171] .B. Kupavskii and A.M. Raigorodskii, On distance graphs with large chromatic numbers and small clique numbers, Doklady Math. 85 (2012), N3, 394-398.

[172] .B. Kupavskii, A.M.Raigorodskii, Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii, Sbornik: Math. 204 (2013), N10, 1435-1479.

[173] .B. Kupavskii, D.A. Shabanov, Colorings of uniform hypergraphs with large girth, Doklady Math. 85 (2012), N2, 247-250.

[174] . Kupavskii and D.A. Shabanov, Colorings of Partial Steiner Systems and Their Applications, J. Math. Sci. 206 (2015), N6, 511-538.

[175] . Kupavskii and D.A. Shabanov, Colorings of uniform, hypergraphs with large girth and applications, Comb. Probab. Comput. 27 (2018), N2, 245-273.

[176] A. Kupavskii and D. Zakharov, Regular bipartite graphs and intersecting families, J. Comb. Theory Ser. A 155 (2018), 180-189.

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

[178] L.C. Lau, R. Ravi, and M. Singh Iterative methods in combinatorial optimization, Cambridge University Press (2011).

[179] N. Lemons and C. Palmer, Unbalance of set systems, Graphs and Combinatorics 24 (2008), N4, 361-365.

[180] L. Lovâsz, On Chromatic Number of Finite Set-Systems, Acta Math. Acad. Sci. Hungar. 19 (1968), 59-67.

[181] L. Lovâsz, Kneser's conjecture, chromatic number, and homotopy; J. Comb. Theory Ser. A 25 (1978), N3, 319-324.

[182] L. Lovâsz, Combinatorial Problems and Exercises, 13.31, North-Holland, Amsterdam (1979).

[183] L. Lovâsz, On the Shannon capacity of a graph, IEEE Transactions on Information theory 25 (1979), N1, 1-7.

[184] T. Luczak and K. Mieczkowska, On Erdos' extremal problem on match-ings in hypergraphs, J. Comb. Theory Ser A 124 (2014), 178-194.

[185] R. Luo, The maximum number of cliques in graphs without long cycles, J. Comb. Theory Ser. B 128 (2018) 219-226.

[186] J. Matousek, On constants for cuttings in the plane, Disc. Comput. Geom., 20 (1998), N4, 427-448.

[187] J. Matousek, Lectures in Discrete Geometry, Springer-Verlag, New York, NY (2002).

[188] J. Matousek, On the chromatic number of Kneser hypergraphs, Proc. Amer. Math. Soc. 130 (2002), N9, 2509-2514.

[189] J. Matousek, Using the Borsuk-Ulam theorem, Springer (2003).

[190] J. Matousek, R. Seidel, and E. Welzl, How to net a lot with little: Small epsilon-nets for disks and halfspaces, In Proceedings of Symposium on Computational Geometry (SOCG) (1990), 16-22.

[191] M. Matsumoto and N. Tokushige, The exact bound in the Erdos Ko Rado theorem for cross-intersecting families, J. Comb. Theory Ser. A, 52 (1989), N1, 90-97.

[192] A. Methuku, D. Pâlvôlgyi, Forbidden hypermatrices imply general bounds on induced forbidden subposet problems, Combinatorics, Probability and Computing 26 (2017), N4, 593-602.

[193] F. Meunier, The chromatic number of almost stable Kneser hyper-graphs, J. Comb. Theory Ser. A 118 (2011), N6, 1820-1828.

[194] M. Mors, A generalization of a theorem of Kruskal, Graphs and Combinatorics 1 (1985), N1, 167-183.

[195] V.F. Moskva and A.M. Raigorodskii, New lower bounds for the independence numbers of distance graphs with vertices in {—1,0,1}n, Math. Notes 89 (2011), N2, 307-308.

[196] D. Mubayi and J. Verstraete, A survey of Turan problems for expansions, In Recent Trends in Combinatorics. Springer (2016), 117-143.

[197] N. H. Mustafa, K. Dutta, and A. Ghosh, A simple proof of optimal epsilon-nets, Combinatorica 38 (2018), N5, 1269-1277.

[198] N. H. Mustafa and S. Ray, Near-optimal generalisations of a theorem of Macbeath, In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS) (2014), 578-589.

[199] N. H. Mustafa and K. Varadarajan, Epsilon-approximations and epsilon-nets, In J. E. Goodman, J. O'Rourke, and C. D. Toth, editors, Handbook of Discrete and Computational Geometry Third edition. CRC Press LLC (2017), 1241-1267.

[200] F. Quinn, PhD Thesis, Massachusetts Institute of Technology (1986).

[201] J. Pach and P. K. Agarwal, Combinatorial Geometry, John Wiley & Sons, New York, NY (1995).

[202] J. Pach and G. Tardos, Tight lower bounds for the size of epsilon-nets, J. Amer. Math. Soc. 26 (2013), N3, 645-658.

[203] E.I. Ponomarenko and A.M. Raigorodskii, New upper bounds for the independence numbers with vertices at {—1,0,1}n and their applications to the problems on the chromatic numbers of distance graphs, Math. Notes 96 (2014), N1, 140-148.

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

[205] M. Pyaderkin and A. Raigorodskii, On random subgraphs of Kneser graphs and their generalizations, Dokl. Math. 94 (2016), N2, 547-549.

[206] L. Pyber, A new generalization of the Erdos-Ko-Rado theorem, J. Comb. Theory Ser. A 43 (1986), 85-90.

[207] E. Pyrga and S. Ray, New existence proofs for epsilon-nets, In Proceedings of the Symposium on Computational Geometry (SoCG) (2008), 199-207.

[208] A.M. Raigorodskii, On a bound in Borsuk's problem, Russian Math. Surveys 54 (1999), N2, 453-454.

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

[210] A.M. Raigorodskii, On distance graphs with large chromatic number but without large simplices, Russian Mathematical Surveys 62 (2007), N6, 12241,1-1225.

[211] A.M. Raigorodskii, The linear algebra method in combinatorics, Moscow Centre for Continuous Mathematical Education (MCCME), Moscow, Russia (2007) (in Russian).

[212] A.M. Raigorodskii, Around Borsuk's conjecture, J. of Math. Sci. 154 (2008), N4, 604-623.

[213] A.M. Raigorodskii, Three lectures on the Borsuk partition problem, London Math. Soc. Lecture Note Series 347 (2007), 202-248.

[214] A.M. Raigorodskii, Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer (2013), 429-460.

[215] A.M. Raigorodskii, Combinatorial geometry and coding theory, Fundamenta Informática, 145 (2016), 359-369.

[216] A.M. Raigorodskii, On the stability of the independence number of a random subgraph, Dokl. Math. 96 (2017), N3, 628-630.

[217] A.M. Raigorodskii and I.M. Shitova, On the chromatic numbers of real and rational spaces with several real or rational forbidden distances, Sbornik Math. 199 (2008), N4, 579-612.

[218] A.A. Razborov and N.K. Vereshchagin. One property of cross-intersecting families, Research Communications of the conference held in memory of Paul Erdós (1999).

[219] C.A. Rogers, Covering a sphere with spheres, Mathematika 10 (1963), 157-164.

[220] M. Rosenfeld, Almost orthogonal lines in Applied geometry and discrete mathematics. The Victor Klee Festschrift (Peter Gritzmann and Bernd Sturmfels, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 4, Amer. Math. Soc., Providence, RI (1991), 489-492.

[221] A. Sali, Some intersection theorems, Combinatorica 12 (1992), 351-361.

[222] N. Sauer, On the density of families of sets, J. Comb. Theory Ser. A 13 (1972), 145-147.

[223] O. Schramm, Illuminating sets of constant width, Mathematika 35 (1988), 180-189.

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

[225] M. Sharir, On k-sets in arrangement of curves and surfaces, Disc. Comput. Geom., 6 (1991), 593-613.

[226] S. Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific Journal of Mathematics 41 (1972), 247-261.

[227] H. Snevily, A new result on ChvdtaVs conjecture, J. Comb. Theory Ser. A 61 (1992), N1, 137-141.

[228] E. Sperner, Ein Satz uber Untermengen einer endlichen Menge, Math. Z. 27 (1928), N1, 544-548.

[229] L.A. Szekely, Erdos on unit distances and the Szemeredi-Trotter theorems,, Paul Erdos and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649-666.

[230] T. Tao, Structure and randomness in combinatorics, arXiv:0707.4269 (2007).

[231] V. N. Vapnik and A. Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications 16 (1971), N2, 264-280.

[232] K. Varadarajan, Epsilon nets and union complexity, In Proceedings of the Symposium on Computational Geometry (SoCG) (2009), 11-16.

[233] K. Varadarajan, Weighted geometric set cover via quasi uniform sampling, In Proceedings of the Symposium on Theory of Computing (STOC) (2010), 641-648, New York, USA. ACM.

[234] J. Wang and H. Zhang, Nontrivial independent sets of bipartite graphs and cross-intersecting families, J. Comb. Theory Ser. A 120 (2013), N1, 129-141.

[235] R.M. Wilson, The exact bound in the Erdos-Ko-Rado theorem, Com-binatorica, 4 (1984), N2-3, 247-257.

[236] Y. Zhao, Recent advances on dirac-type problems for hypergraphs, In Recent Trends in Combinatorics, volume 159 of the IMA Volumes in Mathematics and its Applications. Springer, New York, 2016.

[237] G. M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), 671-691. Erratum ibid., 163 (2006), 227-228.