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

Краткое описание

Купавский Андрей Борисович Семейства множеств с запрещенными конфигурациями и приложения к дискретной геометрии независимости / Families of Sets With Forbidden Configurations and Applications to Discrete Geometry
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
доктор наук Купавский Андрей Борисович
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