Local to Global Phenomenon and Other Topics in Probabilistic and Extremal Combinatorics
Matija Bucić · Repository for Publications and Research Data (ETH Zurich) · 2021
Extremal combinatorics is one of the fundamental fields of study in modern combinatorics, tracing its origins at the very least to the work of Euler in the 18-th century.In a very general sense, extremal combinatorics is concerned with questions of the form how large or how small a collection of finite objects can be, provided it has to satisfy certain restrictions.Another fundamental branch of modern combinatorics is probabilistic combinatorics which was first systematically studied by Erdős in the 1940s.Probabilistic combinatorics entails the use of probability theory to obtain combinatorial results, which in many cases have no inherent randomness at all.In this thesis, we explore a number of different topics in extremal and probabilistic combinatorics.The first half of the discussed topics have a common theme.Namely, they are concerned with instances of the local to global principle, which states that one can obtain a global understanding of a structure from having a good understanding of its local properties, or vice versa.This phenomenon has been ubiquitous in many areas of mathematics and beyond, with profound consequences.Our first topic is concerned with the classical, extensively studied, Erdős-Rogers problem dating back to 1962, which can be restated as follows.How large must the independence number α(G) of a graph G be, whose every m vertices contain an independent set of size r?This restatement is due to Erdős and Hajnal and independently Linial and Rabinovich from the early '90s.It arose from a change in perspective, which shifts the focus from fixing α(G) and r to fixing the local parameters m and r instead.We develop two new approaches to attack this problem which allow us to significantly improve previously best known bounds due to Linial and Rabinovich, Erdős and Hajnal, Alon and Sudakov, Krivelevich, and Kostochka and Jancey, depending on the regime.We also discuss a related topic of connecting a local Ramsey property to its global counterpart, introduced by Erdős and Hajnal, which we exploit to obtain new examples of Ramsey graphs.The next topic is concerned with the following type of questions.How many monochromatic paths, cycles, or general trees does one need to cover all vertices of a given r-edge-coloured graph G?These problems date back to the 1960s and were intensively studied by various researchers over the last 50 years.We establish a connection between this problem and the following natural Helly-type, local to global question for hypergraphs.What is the maximum number of vertices needed to cover all the edges of a hypergraph H if it is known that any collection of a few edges of H has a small cover?This problem was raised by Erdős, Hajnal, and Tuza about 30 years ago.We vii unerwartete Antworten auf verschiedene Fragen zur Abdeckung von Graphen durch monochromatische Bäume zu geben, die von Bal und DeBiasio; Kohayakawa, Mota und Schacht; Lang und Lo; und Girão, Letzter und Sahasrabudhe aufgeworfen wurden.Wir werden auch Konzepte für das lokale und globale Erzwingen von Turnieren diskutieren.Hier wird beispielsweise ein Turnier H als lokal erzwungen bezeichnet, wenn ein grosses Turnier T mit korrekten Zählungen von H (ungefähr das gleiche wie im Zufallsturnier) als Subturnier in allen grossen induzierten Subturnieren zwangsläufig quasi-zufällig sein muss.Wir entwickeln eine analoge Theorie zu der von Chung und Graham eingeführten für übliche Graphen mit einigen überraschenden Ergebnissen.Ein Highlight ist ein Ergebnis, das besagt, dass H, um H selbst lokal zu erzwingen, sehr stark quasi-zufällig sein muss.Rotas Vermutung aus dem Jahr 1989 besagt Folgendes.Gegeben n Basen B 1 , . . ., B n in einem n-dimensionalen Vektorraum V, kann man immer n disjunkte Basen von V finden, die jeweils genau ein Element von jedem B i enthalten (wir nennen solche Basen transversale Basen).Rotas Basis-Vermutung bleibt trotz ihrer offensichtlichen weit offen Einfachheit und der Bemühungen vieler Forscher in den letzten 30 Jahren weit offen.Wir erhalten die erste lineare Schranke für die Anzahl von disjunkte transversale Basen Anzahl disjunkter transversaler Basen, die man finden kann.Die Vermutung hat eine natürliche Erweiterung für Matroide, wo unsere Ergebnisse auch zutreffen.Das klassische Erdős-Szekeres-Theorem aus fast hundert Jahren besagt, dass jede Folge von (n -1) 2 + 1 verschiedenen reellen Zahlen eine monotone Teilfolge der Länge n enthält.Es wurde auf verschiedene Weise auf höhere Dimensionen verallgemeinert, aber das vielleicht natürlichste wurde vor etwa 25 Jahren von Fishburn und Graham vorgeschlagen.Sie definierten Konzepte eines monotonen und eines lexmonotonen Arrays und fragten, wie gross ein Array sein müsse, um ein monotones oder ein lex-monotones Subarray der Grösse n × . . .× n zu finden.In beiden Fällen erhielten sie für ihr Problem Schranken vom Typ Ackermann.Wir verbessern diese Ergebnisse deutlich.Unabhängig von der Dimension erhalten wir in beiden Fällen höchstens eine vierfache Exponentialgrenze in n.Wir verbinden das Problem auch mit einer Reihe interessanter Themen, die von verschiedenen Forschern im Laufe der Jahre behandelt wurden.Wir schliessen mit zwei Themen der extremalen-Mengentheorie.Die erste betrifft die minimal mögliche Grösse des Schnittspektrums eines 3-chromatischen sich überschneidenden Hypergraphen, wobei wir in sehr starker Form eine Vermutung von Erdős und Lovász aus dem Jahr 1973 beweisen.Die zweite betrifft gesättigte Familien von Mengen, in denen wir eine Frage von Frankl und Tokushige beantworten und erste wesentliche Fortschritte bei einer Vermutung von Erdős und Kleitman aus dem Jahr 1974 machen.Der Hauptbestandteil ist eine Verbindung, die wir zwischen dem Problem und einer berühmten Korrelationsungleichheit beobachten.x Main parts of this thesis correspond closely to a number of papers completed during my doctorate.Specifically:-Section 2.1 corresponds to the paper "Large independent sets from local considerations", joint work with Benny Sudakov.-Section 2.2 corresponds to the paper "Large cliques and independent sets all over the place", joint work with N. Alon and B. Sudakov (published in Proceedings of AMS).-Section 3.1 corresponds to the paper "Covering graphs by monochromatic trees and Helly-type results for hypergraphs", joint work with D. Korándi and B. Sudakov (accepted for publication in Combinatorica).-Section 3.2 corresponds to the paper "Tournament quasirandomness from local counting", joint work with E. Long, A. Shapira and B. Sudakov (accepted for publication in Combinatorica).-Chapter 4 corresponds to the paper "Erdős-Szekeres theorem for multidimensional arrays", joint work with B. Sudakov and T. Tran.-Chapter 5 corresponds to the paper "Halfway to Rota's basis conjecture", joint work with M. Kwan, A. Pokrovskiy and B. Sudakov (published in International Mathematics Research Notices).-Section 6.1 corresponds to the paper "The intersection spectrum of 3-chromatic intersecting hypergraphs", joint work with S. Glock and B.Sudakov.-Section 6.2 corresponds to the paper "Minimum saturated families of sets", joint work with S. Letzter, B. Sudakov and T. Tran (published in Bulletin of the LMS).