{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/338929"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/338929","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Combinatorial Problems with Geometric Flavour","abstract":"This thesis consists of an introduction and nine chapters, each devoted to a different combinatorial problem. What gives these problems coherence is that although at first sight they look very different, the essential difficulties in most are geometric. In Chapters 2 and 3, we investigate sumset inequalities. For sets $A,B$ in an abelian group $G$, define the sumset $A+B=\\{a+b\\text{ : }a \\in A, b\\in B\\}$. We consider the ambient groups $\\mathbb{Z}^k$ and $\\mathbb{R}^k$, endowed with the measure $|\\cdot|$ representing cardinality and outer Lebesgue measure, respectively. One of the central questions in additive combinatorics is the inverse sumset problem of characterizing the finite subsets $A$ with small $\\textit{doubling constant}$ $|A+A|\\cdot|A|^{-1}$. Sets $A$ in $\\mathbb{R}^k$ have doubling constant at least $2^k$; this is no longer true for sets $A$ in $\\mathbb{Z}^k$, unless some $\\textit{non-degeneracy}$ condition is imposed. Our main result describes the structure of $\\textit{non-degenerate}$ sets $A$ in $\\mathbb{Z}^k$ with doubling constant close to $2^k$. We prove a sharp stability result for the classical Freiman--Bilu $2^k$-inequality (improved by Green--Tao) and a generalization of Freiman's $3k-4$ theorem to arbitrary dimension. For $\\delta>0$ sufficiently small and $A\\subset \\mathbb{Z}^k$ with $|A+A|\\le (2^k+\\delta)|A|$, we show either $A$ is covered by $m_k(\\delta)$ parallel hyperplanes, or it satisfies $|\\coo(A)\\setminus A|\\le c_k\\delta |A|$, where $\\coo(A)$ is the smallest convex progression (convex set intersected with an affine sub-lattice) containing $A$. In particular, we deduce the sharp stability result for the Brunn--Minkowski inequality for equal sets, conjectured by Figalli and Jerison. Given $\\delta>0$ sufficiently small and $A\\subset \\mathbb{R}^k$ with $|A+A|\\le (2^k+\\delta)|A|$, we show $|\\co(A)\\setminus A|\\le c_k\\delta |A|$, where $\\co(A)$ is the smallest convex set containing $A$. Finally, we prove a strengthen version of the aforementioned conjecture by Figalli and Jerison for a specific class of geometric objects. We find the optimal constants $c_k$, when $A \\subset \\mathbb{R}^k$ is the hypograph of a function defined on a convex domain in dimension $k-1 \\leq 3$. In Chapters 4, 5 and 6, we investigate covering systems. A covering system is a finite collection of arithmetic progressions $\\{a_1\\text{ }(\\text{mod } m_1),a_2\\text{ }(\\text{mod } m_2), \\hdots, a_k\\text{ }(\\text{mod } m_k) \\}$ that cover the integers, i.e., $\\cup_i \\{a_i+ n m_i \\text{ : } n \\in \\mathbb{Z}\\}=\\mathbb{Z}$. Since their introduction by Erdős in 1950, covering systems have been extensively studied, and numerous questions and conjectures have been posed regarding the existence of covering systems with various properties. More than fifty years ago, Erdős asked if the moduli can be distinct and all arbitrarily large, Erdős and Selfridge asked if the moduli can be distinct and all odd, and Schinzel conjectured that in any covering system there exists a pair of moduli, one of which divides the other. Another beautiful conjecture, proposed by Erdős and Graham in 1980, states that if the moduli are distinct elements of the interval $[n,Cn]$, and $n$ is sufficiently large, then the density of integers uncovered by the union is bounded below by a constant (depending only on~$C$). This conjecture was confirmed (in a strong form) by Filaseta, Ford, Konyagin, Pomerance and Yu in 2007, who moreover asked whether the same conclusion holds if the moduli are distinct and sufficiently large, and $\\sum_{i=1}^k \\frac{1}{d_i} < C$. Although, as it turns out, this condition is not sufficiently strong to imply the desired conclusion, as one of the main results of this paper we give an essentially best possible condition which is sufficient. More precisely, we show that if all of the moduli are sufficiently large, then the union misses a set of density at least $e^{-4C}/2$, where \\[ C = \\sum_{i=1}^k \\frac{\\mu(d_i)}{d_i} \\] and $\\mu$ is a multiplicative function defined by $\\mu(p^i)=1+(\\log p)^{3+\\eps}/p$ for some $\\eps > 0$. We also show that no such lower bound (i.e., depending only on~$C$) on the density of the uncovered set holds, when $\\mu(p^i)$ is replaced by any function of the form $1+O(1/p)$. Our method has a number of further applications. Most importantly, we prove the conjecture of Schinzel. In addition, we give an alternative (somewhat simpler) proof of a breakthrough result of Hough, who resolved Erdős' minimum modulus problem, with an improved bound on the smallest difference. Moreover, we make further progress on the problem of Erdős and Selfridge, which, in particular, we solve in the square free case. Finally, we answer another natural question of Erdős, asked in 1952, on the \\emph{number} of minimal covering systems. Addressing this question requires very different methods. %, that is, covering systems such that the removal of any progression leaves an element uncovered. More precisely, we show that the number of minimal covering systems with exactly $n$ elements is \\[ \\exp\\left( \\left(\\frac{4\\sqrt{\\tau}}{3} + o(1)\\right) \\frac{n^{3/2}}{(\\log n)^{1/2}} \\right) \\] as $n \\to \\infty$, where \\[ \\tau = \\sum_{t = 1}^\\infty \\left( \\log \\frac{t+1}{t} \\right)^2. \\] \\textit{En route} to this counting result, we obtain a structural description of all covering systems that are close to optimal in an appropriate sense. Chapter 7 is devoted to Littlewood polynomials. Answering a question of Erd\\H{o}s from 1957 and confirming a conjecture of Littlewood from 1966, we show that there exist absolute constants $\\Delta > \\delta > 0$ such that, for all $n \\ge 2$, there exists a polynomial $P$ of degree~$n$, with coefficients in $\\{-1,1\\}$, such that \\[ \\delta\\sqrt{n} \\le |P(z)| \\le \\Delta\\sqrt{n} \\] for all $z\\in\\C$ with $|z|=1$. Over time, this problem attracted considerable attention and, in particular, Littlewood included it in his well-known monograph containing $30$ of his favourite problems. Chapter 8 is devoted to judicious partitions. Bollobás, Reed and Thomason proved that every $3$-uniform hypergraph with $m$ hyperedges has a vertex-partition into $3$ parts such that each part meets at least $\\frac{1}{3}(1-\\frac{1}{e})m$ hyperedges. Halsegrave optimized the value to $0.6m$, confirming a special case of a conjecture of Bollobás and Thomason from $1993$. For large values of $m$, Ma and Yu improved the bound asymptotically to $0.65m+o(m)$. We further improve this asymptotic bound to $\\frac{19}{27}m+o(m)$, which is best possible up to the error term, resolving the next open case of a conjecture of Bollobás and Scott from $2000$. Chapter 9 is devoted to coloured structures in the Boolean lattice. Given a collection of coloured chain posets, we estimate the number of coloured subsets of the Boolean lattice which avoid all chains in this collection. Our proof relies on the recent powerful method of hypergraph containers developed independently by Balogh, Morris and Samotij as well as Saxton and Thomason, inspired by the previous work of Conlon and Gowers. In order to prove results about coloured chain posets we need to apply the hypergraph container lemma recursively, with different uniformities at each stage, using a balanced supersaturation result for a certain non-uniform hypergraph encoding forbidden configurations. Our work extends to a coloured setting the previous work of Collares and Morris as well as Balogh, Mycroft, and Treglown on the number of antichains in a random subset of the Boolean lattice. Chapter 10 is devoted to positional games. For two graphs $B$ and $H$ the strong Ramsey game $\\mathcal{R}(B,H)$ on the board $B$ and with target $H$ is played as follows. Two players alternately claim edges of $B$. The first player to build a copy of $H$ wins. If none of the players win, the game is declared a draw. A notorious open question of Beck asks whether the first player has a winning strategy in $\\mathcal{R}(K_n,K_k)$ in bounded time as $n\\rightarrow\\infty$. Surprisingly, in a recent paper Hefetz, Kusch, Narins, Pokrovskiy, Requilé and Sarid constructed a $5$-uniform hypergraph $\\mathcal{H}$ for which they proved that the first player does not have a winning strategy in $\\mathcal{R}(K_n^{(5)},\\mathcal{H})$ in bounded time. They naturally asked whether an analogous result holds for graphs. We make further progress towards this question.","abstract_html":"This thesis consists of an introduction and nine chapters, each devoted to a different combinatorial problem. What gives these problems coherence is that although at first sight they look very different, the essential difficulties in most are geometric. In Chapters 2 and 3, we investigate sumset inequalities. For sets $A,B$ in an abelian group $G$, define the sumset $A+B=\\{a+b\\text{ : }a \\in A, b\\in B\\}$. We consider the ambient groups \\mathbb{Z}k and \\mathbb{R}k, endowed with the measure $|\\cdot|$ representing cardinality and outer Lebesgue measure, respectively. One of the central questions in additive combinatorics is the inverse sumset problem of characterizing the finite subsets $A$ with small doubling constant |A+A|\\cdot|A|-1. Sets $A$ in \\mathbb{R}k have doubling constant at least 2k; this is no longer true for sets $A$ in \\mathbb{Z}k, unless some non-degeneracy condition is imposed. Our main result describes the structure of non-degenerate sets $A$ in \\mathbb{Z}k with doubling constant close to 2k. We prove a sharp stability result for the classical Freiman--Bilu 2k-inequality (improved by Green--Tao) and a generalization of Freiman's $3k-4$ theorem to arbitrary dimension. For δ>0 sufficiently small and A\\subset \\mathbb{Z}k with |A+A|\\le (2k+δ)|A|, we show either $A$ is covered by mk(δ) parallel hyperplanes, or it satisfies |\\coo(A)\\setminus A|\\le ckδ |A|, where $\\coo(A)$ is the smallest convex progression (convex set intersected with an affine sub-lattice) containing $A$. In particular, we deduce the sharp stability result for the Brunn--Minkowski inequality for equal sets, conjectured by Figalli and Jerison. Given δ>0 sufficiently small and A\\subset \\mathbb{R}k with |A+A|\\le (2k+δ)|A|, we show |\\co(A)\\setminus A|\\le ckδ |A|, where $\\co(A)$ is the smallest convex set containing $A$. Finally, we prove a strengthen version of the aforementioned conjecture by Figalli and Jerison for a specific class of geometric objects. We find the optimal constants ck, when A \\subset \\mathbb{R}k is the hypograph of a function defined on a convex domain in dimension $k-1 \\leq 3$. In Chapters 4, 5 and 6, we investigate covering systems. A covering system is a finite collection of arithmetic progressions \\{a1\\text{ }(\\text{mod } m1),a2\\text{ }(\\text{mod } m2), \\hdots, ak\\text{ }(\\text{mod } mk) \\} that cover the integers, i.e., \\cupi \\{ai+ n mi \\text{ : } n \\in \\mathbb{Z}\\}=\\mathbb{Z}. Since their introduction by Erdős in 1950, covering systems have been extensively studied, and numerous questions and conjectures have been posed regarding the existence of covering systems with various properties. More than fifty years ago, Erdős asked if the moduli can be distinct and all arbitrarily large, Erdős and Selfridge asked if the moduli can be distinct and all odd, and Schinzel conjectured that in any covering system there exists a pair of moduli, one of which divides the other. Another beautiful conjecture, proposed by Erdős and Graham in 1980, states that if the moduli are distinct elements of the interval $[n,Cn]$, and $n$ is sufficiently large, then the density of integers uncovered by the union is bounded below by a constant (depending only on~$C$). This conjecture was confirmed (in a strong form) by Filaseta, Ford, Konyagin, Pomerance and Yu in 2007, who moreover asked whether the same conclusion holds if the moduli are distinct and sufficiently large, and \\sumi=1k \\frac{1}{di} < C. Although, as it turns out, this condition is not sufficiently strong to imply the desired conclusion, as one of the main results of this paper we give an essentially best possible condition which is sufficient. More precisely, we show that if all of the moduli are sufficiently large, then the union misses a set of density at least e-4C/2, where \\[ C = \\sum_{i=1}^k \\frac{\\mu(d_i)}{d_i} \\] and μ is a multiplicative function defined by μ(pi)=1+(\\log p)3+\\eps/p for some $\\eps > 0$. We also show that no such lower bound (i.e., depending only on~$C$) on the density of the uncovered set holds, when μ(pi) is replaced by any function of the form $1+O(1/p)$. Our method has a number of further applications. Most importantly, we prove the conjecture of Schinzel. In addition, we give an alternative (somewhat simpler) proof of a breakthrough result of Hough, who resolved Erdős' minimum modulus problem, with an improved bound on the smallest difference. Moreover, we make further progress on the problem of Erdős and Selfridge, which, in particular, we solve in the square free case. Finally, we answer another natural question of Erdős, asked in 1952, on the \\emph{number} of minimal covering systems. Addressing this question requires very different methods. %, that is, covering systems such that the removal of any progression leaves an element uncovered. More precisely, we show that the number of minimal covering systems with exactly $n$ elements is \\[ \\exp\\left( \\left(\\frac{4\\sqrt{\\tau}}{3} + o(1)\\right) \\frac{n^{3/2}}{(\\log n)^{1/2}} \\right) \\] as $n \\to \\infty$, where \\[ \\tau = \\sum_{t = 1}^\\infty \\left( \\log \\frac{t+1}{t} \\right)^2. \\] \\textit{En route} to this counting result, we obtain a structural description of all covering systems that are close to optimal in an appropriate sense. Chapter 7 is devoted to Littlewood polynomials. Answering a question of Erd\\H{o}s from 1957 and confirming a conjecture of Littlewood from 1966, we show that there exist absolute constants \\Delta > δ > 0 such that, for all $n \\ge 2$, there exists a polynomial $P$ of degree~$n$, with coefficients in $\\{-1,1\\}$, such that \\[ \\delta\\sqrt{n} \\le |P(z)| \\le \\Delta\\sqrt{n} \\] for all $z\\in\\C$ with $|z|=1$. Over time, this problem attracted considerable attention and, in particular, Littlewood included it in his well-known monograph containing $30$ of his favourite problems. Chapter 8 is devoted to judicious partitions. Bollobás, Reed and Thomason proved that every $3$-uniform hypergraph with $m$ hyperedges has a vertex-partition into $3$ parts such that each part meets at least $\\frac{1}{3}(1-\\frac{1}{e})m$ hyperedges. Halsegrave optimized the value to $0.6m$, confirming a special case of a conjecture of Bollobás and Thomason from $1993$. For large values of $m$, Ma and Yu improved the bound asymptotically to $0.65m+o(m)$. We further improve this asymptotic bound to $\\frac{19}{27}m+o(m)$, which is best possible up to the error term, resolving the next open case of a conjecture of Bollobás and Scott from $2000$. Chapter 9 is devoted to coloured structures in the Boolean lattice. Given a collection of coloured chain posets, we estimate the number of coloured subsets of the Boolean lattice which avoid all chains in this collection. Our proof relies on the recent powerful method of hypergraph containers developed independently by Balogh, Morris and Samotij as well as Saxton and Thomason, inspired by the previous work of Conlon and Gowers. In order to prove results about coloured chain posets we need to apply the hypergraph container lemma recursively, with different uniformities at each stage, using a balanced supersaturation result for a certain non-uniform hypergraph encoding forbidden configurations. Our work extends to a coloured setting the previous work of Collares and Morris as well as Balogh, Mycroft, and Treglown on the number of antichains in a random subset of the Boolean lattice. Chapter 10 is devoted to positional games. For two graphs $B$ and $H$ the strong Ramsey game $\\mathcal{R}(B,H)$ on the board $B$ and with target $H$ is played as follows. Two players alternately claim edges of $B$. The first player to build a copy of $H$ wins. If none of the players win, the game is declared a draw. A notorious open question of Beck asks whether the first player has a winning strategy in \\mathcal{R}(Kn,Kk) in bounded time as $n\\rightarrow\\infty$. Surprisingly, in a recent paper Hefetz, Kusch, Narins, Pokrovskiy, Requilé and Sarid constructed a $5$-uniform hypergraph $\\mathcal{H}$ for which they proved that the first player does not have a winning strategy in \\mathcal{R}(Kn(5),\\mathcal{H}) in bounded time. They naturally asked whether an analogous result holds for graphs. We make further progress towards this question.","abstract_has_math":true,"creators":["Tiba, Marius"],"institution":"University of Cambridge","degree_name":null,"degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Bollobás, Béla"],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-05-01","date_published":"2021-05-01","updated_at":"2026-07-22T22:23:54Z","subjects":["Combinatorics"],"languages":["eng"],"rights":[],"rights_urls":["https://www.rioxx.net/licenses/all-rights-reserved/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.86336","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Bollobás, Béla"]},{"key":"dc:creator","label":"Author","values":["Tiba, Marius"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2021-05-01"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/338929"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://www.rioxx.net/licenses/all-rights-reserved/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["10.17863/CAM.86336"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://www.repository.cam.ac.uk/bitstreams/3e56a52b-af06-443e-b763-7a0f8ea9f784/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This thesis consists of an introduction and nine chapters, each devoted to a different combinatorial problem. What gives these problems coherence is that although at first sight they look very different, the essential difficulties in most are geometric. In Chapters 2 and 3, we investigate sumset inequalities. For sets $A,B$ in an abelian group $G$, define the sumset $A+B=\\{a+b\\text{ : }a \\in A, b\\in B\\}$. We consider the ambient groups $\\mathbb{Z}^k$ and $\\mathbb{R}^k$, endowed with the measure $|\\cdot|$ representing cardinality and outer Lebesgue measure, respectively. One of the central questions in additive combinatorics is the inverse sumset problem of characterizing the finite subsets $A$ with small $\\textit{doubling constant}$ $|A+A|\\cdot|A|^{-1}$. Sets $A$ in $\\mathbb{R}^k$ have doubling constant at least $2^k$; this is no longer true for sets $A$ in $\\mathbb{Z}^k$, unless some $\\textit{non-degeneracy}$ condition is imposed. Our main result describes the structure of $\\textit{non-degenerate}$ sets $A$ in $\\mathbb{Z}^k$ with doubling constant close to $2^k$. We prove a sharp stability result for the classical Freiman--Bilu $2^k$-inequality (improved by Green--Tao) and a generalization of Freiman's $3k-4$ theorem to arbitrary dimension. For $\\delta>0$ sufficiently small and $A\\subset \\mathbb{Z}^k$ with $|A+A|\\le (2^k+\\delta)|A|$, we show either $A$ is covered by $m_k(\\delta)$ parallel hyperplanes, or it satisfies $|\\coo(A)\\setminus A|\\le c_k\\delta |A|$, where $\\coo(A)$ is the smallest convex progression (convex set intersected with an affine sub-lattice) containing $A$. In particular, we deduce the sharp stability result for the Brunn--Minkowski inequality for equal sets, conjectured by Figalli and Jerison. Given $\\delta>0$ sufficiently small and $A\\subset \\mathbb{R}^k$ with $|A+A|\\le (2^k+\\delta)|A|$, we show $|\\co(A)\\setminus A|\\le c_k\\delta |A|$, where $\\co(A)$ is the smallest convex set containing $A$. Finally, we prove a strengthen version of the aforementioned conjecture by Figalli and Jerison for a specific class of geometric objects. We find the optimal constants $c_k$, when $A \\subset \\mathbb{R}^k$ is the hypograph of a function defined on a convex domain in dimension $k-1 \\leq 3$. In Chapters 4, 5 and 6, we investigate covering systems. A covering system is a finite collection of arithmetic progressions $\\{a_1\\text{ }(\\text{mod } m_1),a_2\\text{ }(\\text{mod } m_2), \\hdots, a_k\\text{ }(\\text{mod } m_k) \\}$ that cover the integers, i.e., $\\cup_i \\{a_i+ n m_i \\text{ : } n \\in \\mathbb{Z}\\}=\\mathbb{Z}$. Since their introduction by Erdős in 1950, covering systems have been extensively studied, and numerous questions and conjectures have been posed regarding the existence of covering systems with various properties. More than fifty years ago, Erdős asked if the moduli can be distinct and all arbitrarily large, Erdős and Selfridge asked if the moduli can be distinct and all odd, and Schinzel conjectured that in any covering system there exists a pair of moduli, one of which divides the other. Another beautiful conjecture, proposed by Erdős and Graham in 1980, states that if the moduli are distinct elements of the interval $[n,Cn]$, and $n$ is sufficiently large, then the density of integers uncovered by the union is bounded below by a constant (depending only on~$C$). This conjecture was confirmed (in a strong form) by Filaseta, Ford, Konyagin, Pomerance and Yu in 2007, who moreover asked whether the same conclusion holds if the moduli are distinct and sufficiently large, and $\\sum_{i=1}^k \\frac{1}{d_i} < C$. Although, as it turns out, this condition is not sufficiently strong to imply the desired conclusion, as one of the main results of this paper we give an essentially best possible condition which is sufficient. More precisely, we show that if all of the moduli are sufficiently large, then the union misses a set of density at least $e^{-4C}/2$, where \\[ C = \\sum_{i=1}^k \\frac{\\mu(d_i)}{d_i} \\] and $\\mu$ is a multiplicative function defined by $\\mu(p^i)=1+(\\log p)^{3+\\eps}/p$ for some $\\eps > 0$. We also show that no such lower bound (i.e., depending only on~$C$) on the density of the uncovered set holds, when $\\mu(p^i)$ is replaced by any function of the form $1+O(1/p)$. Our method has a number of further applications. Most importantly, we prove the conjecture of Schinzel. In addition, we give an alternative (somewhat simpler) proof of a breakthrough result of Hough, who resolved Erdős' minimum modulus problem, with an improved bound on the smallest difference. Moreover, we make further progress on the problem of Erdős and Selfridge, which, in particular, we solve in the square free case. Finally, we answer another natural question of Erdős, asked in 1952, on the \\emph{number} of minimal covering systems. Addressing this question requires very different methods. %, that is, covering systems such that the removal of any progression leaves an element uncovered. More precisely, we show that the number of minimal covering systems with exactly $n$ elements is \\[ \\exp\\left( \\left(\\frac{4\\sqrt{\\tau}}{3} + o(1)\\right) \\frac{n^{3/2}}{(\\log n)^{1/2}} \\right) \\] as $n \\to \\infty$, where \\[ \\tau = \\sum_{t = 1}^\\infty \\left( \\log \\frac{t+1}{t} \\right)^2. \\] \\textit{En route} to this counting result, we obtain a structural description of all covering systems that are close to optimal in an appropriate sense. Chapter 7 is devoted to Littlewood polynomials. Answering a question of Erd\\H{o}s from 1957 and confirming a conjecture of Littlewood from 1966, we show that there exist absolute constants $\\Delta > \\delta > 0$ such that, for all $n \\ge 2$, there exists a polynomial $P$ of degree~$n$, with coefficients in $\\{-1,1\\}$, such that \\[ \\delta\\sqrt{n} \\le |P(z)| \\le \\Delta\\sqrt{n} \\] for all $z\\in\\C$ with $|z|=1$. Over time, this problem attracted considerable attention and, in particular, Littlewood included it in his well-known monograph containing $30$ of his favourite problems. Chapter 8 is devoted to judicious partitions. Bollobás, Reed and Thomason proved that every $3$-uniform hypergraph with $m$ hyperedges has a vertex-partition into $3$ parts such that each part meets at least $\\frac{1}{3}(1-\\frac{1}{e})m$ hyperedges. Halsegrave optimized the value to $0.6m$, confirming a special case of a conjecture of Bollobás and Thomason from $1993$. For large values of $m$, Ma and Yu improved the bound asymptotically to $0.65m+o(m)$. We further improve this asymptotic bound to $\\frac{19}{27}m+o(m)$, which is best possible up to the error term, resolving the next open case of a conjecture of Bollobás and Scott from $2000$. Chapter 9 is devoted to coloured structures in the Boolean lattice. Given a collection of coloured chain posets, we estimate the number of coloured subsets of the Boolean lattice which avoid all chains in this collection. Our proof relies on the recent powerful method of hypergraph containers developed independently by Balogh, Morris and Samotij as well as Saxton and Thomason, inspired by the previous work of Conlon and Gowers. In order to prove results about coloured chain posets we need to apply the hypergraph container lemma recursively, with different uniformities at each stage, using a balanced supersaturation result for a certain non-uniform hypergraph encoding forbidden configurations. Our work extends to a coloured setting the previous work of Collares and Morris as well as Balogh, Mycroft, and Treglown on the number of antichains in a random subset of the Boolean lattice. Chapter 10 is devoted to positional games. For two graphs $B$ and $H$ the strong Ramsey game $\\mathcal{R}(B,H)$ on the board $B$ and with target $H$ is played as follows. Two players alternately claim edges of $B$. The first player to build a copy of $H$ wins. If none of the players win, the game is declared a draw. A notorious open question of Beck asks whether the first player has a winning strategy in $\\mathcal{R}(K_n,K_k)$ in bounded time as $n\\rightarrow\\infty$. Surprisingly, in a recent paper Hefetz, Kusch, Narins, Pokrovskiy, Requilé and Sarid constructed a $5$-uniform hypergraph $\\mathcal{H}$ for which they proved that the first player does not have a winning strategy in $\\mathcal{R}(K_n^{(5)},\\mathcal{H})$ in bounded time. They naturally asked whether an analogous result holds for graphs. We make further progress towards this question."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["8e6888e9086a37df16a776c2257df3b3"]},{"key":"dc:title","label":"Title","values":["Combinatorial Problems with Geometric Flavour"]}]}],"canonical_facts":{"dc:contributor.advisor":["Bollobás, Béla"],"dc:creator":["Tiba, Marius"],"dc:date.issued":["2021-05-01"],"dc:description.abstract":["This thesis consists of an introduction and nine chapters, each devoted to a different combinatorial problem. What gives these problems coherence is that although at first sight they look very different, the essential difficulties in most are geometric. In Chapters 2 and 3, we investigate sumset inequalities. For sets $A,B$ in an abelian group $G$, define the sumset $A+B=\\{a+b\\text{ : }a \\in A, b\\in B\\}$. We consider the ambient groups $\\mathbb{Z}^k$ and $\\mathbb{R}^k$, endowed with the measure $|\\cdot|$ representing cardinality and outer Lebesgue measure, respectively. One of the central questions in additive combinatorics is the inverse sumset problem of characterizing the finite subsets $A$ with small $\\textit{doubling constant}$ $|A+A|\\cdot|A|^{-1}$. Sets $A$ in $\\mathbb{R}^k$ have doubling constant at least $2^k$; this is no longer true for sets $A$ in $\\mathbb{Z}^k$, unless some $\\textit{non-degeneracy}$ condition is imposed. Our main result describes the structure of $\\textit{non-degenerate}$ sets $A$ in $\\mathbb{Z}^k$ with doubling constant close to $2^k$. We prove a sharp stability result for the classical Freiman--Bilu $2^k$-inequality (improved by Green--Tao) and a generalization of Freiman's $3k-4$ theorem to arbitrary dimension. For $\\delta>0$ sufficiently small and $A\\subset \\mathbb{Z}^k$ with $|A+A|\\le (2^k+\\delta)|A|$, we show either $A$ is covered by $m_k(\\delta)$ parallel hyperplanes, or it satisfies $|\\coo(A)\\setminus A|\\le c_k\\delta |A|$, where $\\coo(A)$ is the smallest convex progression (convex set intersected with an affine sub-lattice) containing $A$. In particular, we deduce the sharp stability result for the Brunn--Minkowski inequality for equal sets, conjectured by Figalli and Jerison. Given $\\delta>0$ sufficiently small and $A\\subset \\mathbb{R}^k$ with $|A+A|\\le (2^k+\\delta)|A|$, we show $|\\co(A)\\setminus A|\\le c_k\\delta |A|$, where $\\co(A)$ is the smallest convex set containing $A$. Finally, we prove a strengthen version of the aforementioned conjecture by Figalli and Jerison for a specific class of geometric objects. We find the optimal constants $c_k$, when $A \\subset \\mathbb{R}^k$ is the hypograph of a function defined on a convex domain in dimension $k-1 \\leq 3$. In Chapters 4, 5 and 6, we investigate covering systems. A covering system is a finite collection of arithmetic progressions $\\{a_1\\text{ }(\\text{mod } m_1),a_2\\text{ }(\\text{mod } m_2), \\hdots, a_k\\text{ }(\\text{mod } m_k) \\}$ that cover the integers, i.e., $\\cup_i \\{a_i+ n m_i \\text{ : } n \\in \\mathbb{Z}\\}=\\mathbb{Z}$. Since their introduction by Erdős in 1950, covering systems have been extensively studied, and numerous questions and conjectures have been posed regarding the existence of covering systems with various properties. More than fifty years ago, Erdős asked if the moduli can be distinct and all arbitrarily large, Erdős and Selfridge asked if the moduli can be distinct and all odd, and Schinzel conjectured that in any covering system there exists a pair of moduli, one of which divides the other. Another beautiful conjecture, proposed by Erdős and Graham in 1980, states that if the moduli are distinct elements of the interval $[n,Cn]$, and $n$ is sufficiently large, then the density of integers uncovered by the union is bounded below by a constant (depending only on~$C$). This conjecture was confirmed (in a strong form) by Filaseta, Ford, Konyagin, Pomerance and Yu in 2007, who moreover asked whether the same conclusion holds if the moduli are distinct and sufficiently large, and $\\sum_{i=1}^k \\frac{1}{d_i} < C$. Although, as it turns out, this condition is not sufficiently strong to imply the desired conclusion, as one of the main results of this paper we give an essentially best possible condition which is sufficient. More precisely, we show that if all of the moduli are sufficiently large, then the union misses a set of density at least $e^{-4C}/2$, where \\[ C = \\sum_{i=1}^k \\frac{\\mu(d_i)}{d_i} \\] and $\\mu$ is a multiplicative function defined by $\\mu(p^i)=1+(\\log p)^{3+\\eps}/p$ for some $\\eps > 0$. We also show that no such lower bound (i.e., depending only on~$C$) on the density of the uncovered set holds, when $\\mu(p^i)$ is replaced by any function of the form $1+O(1/p)$. Our method has a number of further applications. Most importantly, we prove the conjecture of Schinzel. In addition, we give an alternative (somewhat simpler) proof of a breakthrough result of Hough, who resolved Erdős' minimum modulus problem, with an improved bound on the smallest difference. Moreover, we make further progress on the problem of Erdős and Selfridge, which, in particular, we solve in the square free case. Finally, we answer another natural question of Erdős, asked in 1952, on the \\emph{number} of minimal covering systems. Addressing this question requires very different methods. %, that is, covering systems such that the removal of any progression leaves an element uncovered. More precisely, we show that the number of minimal covering systems with exactly $n$ elements is \\[ \\exp\\left( \\left(\\frac{4\\sqrt{\\tau}}{3} + o(1)\\right) \\frac{n^{3/2}}{(\\log n)^{1/2}} \\right) \\] as $n \\to \\infty$, where \\[ \\tau = \\sum_{t = 1}^\\infty \\left( \\log \\frac{t+1}{t} \\right)^2. \\] \\textit{En route} to this counting result, we obtain a structural description of all covering systems that are close to optimal in an appropriate sense. Chapter 7 is devoted to Littlewood polynomials. Answering a question of Erd\\H{o}s from 1957 and confirming a conjecture of Littlewood from 1966, we show that there exist absolute constants $\\Delta > \\delta > 0$ such that, for all $n \\ge 2$, there exists a polynomial $P$ of degree~$n$, with coefficients in $\\{-1,1\\}$, such that \\[ \\delta\\sqrt{n} \\le |P(z)| \\le \\Delta\\sqrt{n} \\] for all $z\\in\\C$ with $|z|=1$. Over time, this problem attracted considerable attention and, in particular, Littlewood included it in his well-known monograph containing $30$ of his favourite problems. Chapter 8 is devoted to judicious partitions. Bollobás, Reed and Thomason proved that every $3$-uniform hypergraph with $m$ hyperedges has a vertex-partition into $3$ parts such that each part meets at least $\\frac{1}{3}(1-\\frac{1}{e})m$ hyperedges. Halsegrave optimized the value to $0.6m$, confirming a special case of a conjecture of Bollobás and Thomason from $1993$. For large values of $m$, Ma and Yu improved the bound asymptotically to $0.65m+o(m)$. We further improve this asymptotic bound to $\\frac{19}{27}m+o(m)$, which is best possible up to the error term, resolving the next open case of a conjecture of Bollobás and Scott from $2000$. Chapter 9 is devoted to coloured structures in the Boolean lattice. Given a collection of coloured chain posets, we estimate the number of coloured subsets of the Boolean lattice which avoid all chains in this collection. Our proof relies on the recent powerful method of hypergraph containers developed independently by Balogh, Morris and Samotij as well as Saxton and Thomason, inspired by the previous work of Conlon and Gowers. In order to prove results about coloured chain posets we need to apply the hypergraph container lemma recursively, with different uniformities at each stage, using a balanced supersaturation result for a certain non-uniform hypergraph encoding forbidden configurations. Our work extends to a coloured setting the previous work of Collares and Morris as well as Balogh, Mycroft, and Treglown on the number of antichains in a random subset of the Boolean lattice. Chapter 10 is devoted to positional games. For two graphs $B$ and $H$ the strong Ramsey game $\\mathcal{R}(B,H)$ on the board $B$ and with target $H$ is played as follows. Two players alternately claim edges of $B$. The first player to build a copy of $H$ wins. If none of the players win, the game is declared a draw. A notorious open question of Beck asks whether the first player has a winning strategy in $\\mathcal{R}(K_n,K_k)$ in bounded time as $n\\rightarrow\\infty$. Surprisingly, in a recent paper Hefetz, Kusch, Narins, Pokrovskiy, Requilé and Sarid constructed a $5$-uniform hypergraph $\\mathcal{H}$ for which they proved that the first player does not have a winning strategy in $\\mathcal{R}(K_n^{(5)},\\mathcal{H})$ in bounded time. They naturally asked whether an analogous result holds for graphs. We make further progress towards this question."],"dc:format.checksum.md5":["8e6888e9086a37df16a776c2257df3b3"],"dc:identifier.doi":["10.17863/CAM.86336"],"dc:identifier.uri":["https://www.repository.cam.ac.uk/bitstreams/3e56a52b-af06-443e-b763-7a0f8ea9f784/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/338929"],"dc:rights":["https://www.rioxx.net/licenses/all-rights-reserved/"],"dc:subject":["Combinatorics"],"dc:title":["Combinatorial Problems with Geometric Flavour"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"]},"updated_at":"2026-07-22T22:23:54Z"}