SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

On the singularity of random symmetric matrices

2021-03-30
Marcelo Campos , Letícia Mattos , Robert Morris +1 more
A well-known conjecture states that a random symmetric n×n matrix with entries in {−1,1} is singular with probability Θ(n22−n). We prove that the probability of this event is at most … A well-known conjecture states that a random symmetric n×n matrix with entries in {−1,1} is singular with probability Θ(n22−n). We prove that the probability of this event is at most exp(−Ω(n)), improving the best-known bound of exp(−Ω(n1∕4 logn)), which was obtained recently by Ferber and Jain. The main new ingredient is an inverse Littlewood–Offord theorem in Zpn that applies under very mild conditions, whose statement is inspired by the method of hypergraph containers.
View PDF Chat

On the singularity of random symmetric matrices

2019-04-25
Marcelo Campos , Letícia Mattos , Robert Morris +1 more
A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta\big( n^2 2^{-n} \big)$. In this paper we prove that … A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta\big( n^2 2^{-n} \big)$. In this paper we prove that the probability of this event is at most $\exp\big( - \Omega( \sqrt{n} ) \big)$, improving the best known bound of $\exp\big( - \Omega( n^{1/4} \sqrt{\log n} ) \big)$, which was obtained recently by Ferber and Jain. The main new ingredient is an inverse Littlewood-Offord theorem in $\mathbb{Z}_p^n$ that applies under very mild conditions, whose statement is inspired by the method of hypergraph containers.

Asymmetric Ramsey properties of random graphs involving cliques and cycles

2022-07-21
Anita Liebenau , Letícia Mattos , Walner Mendonça +1 more
Abstract We say that if, in every edge coloring , we can find either a 1‐colored copy of or a 2‐colored copy of . The well‐known Kohayakawa‐Kreuter conjecture states that … Abstract We say that if, in every edge coloring , we can find either a 1‐colored copy of or a 2‐colored copy of . The well‐known Kohayakawa‐Kreuter conjecture states that the threshold for the property is equal to , where is given by for any pair of graphs and with . In this article, we show the 0‐statement of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques.
View PDF Chat

On the singularity of random symmetric matrices

2019-01-01
Marcelo Campos , Letícia Mattos , Robert D. Morris +1 more
A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta\big( n^2 2^{-n} \big)$. In this paper we prove that … A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta\big( n^2 2^{-n} \big)$. In this paper we prove that the probability of this event is at most $\exp\big( - \Omega( \sqrt{n} ) \big)$, improving the best known bound of $\exp\big( - \Omega( n^{1/4} \sqrt{\log n} ) \big)$, which was obtained recently by Ferber and Jain. The main new ingredient is an inverse Littlewood-Offord theorem in $\mathbb{Z}_p^n$ that applies under very mild conditions, whose statement is inspired by the method of hypergraph containers.

Asymmetric Ramsey Properties of Random Graphs for Cliques and Cycles

2020-01-01
Anita Liebenau , Letícia Mattos , Walner Mendonça +1 more
We say that $G \to (F,H)$ if, in every edge colouring $c: E(G) \to \{1,2\}$, we can find either a $1$-coloured copy of $F$ or a $2$-coloured copy of $H$. … We say that $G \to (F,H)$ if, in every edge colouring $c: E(G) \to \{1,2\}$, we can find either a $1$-coloured copy of $F$ or a $2$-coloured copy of $H$. The well-known Kohayakawa--Kreuter conjecture states that the threshold for the property $G(n,p) \to (F,H)$ is equal to $n^{-1/m_{2}(F,H)}$, where $m_{2}(F,H)$ is given by \[ m_{2}(F,H):= \max \left\{\dfrac{e(J)}{v(J)-2+1/m_2(H)} : J \subseteq F, e(J)\ge 1 \right\}. \] In this paper, we show the $0$-statement of the Kohayakawa--Kreuter conjecture for every pair of cycles and cliques.

Counting r-graphs without forbidden configurations

2022-07-27
József Balogh , Felix Christian Clemen , Letícia Mattos
View PDF Chat

On the anti-Ramsey threshold for non-balanced graphs

2022-01-01
P.M.A.G. Araújo , Táısa Martins , Letícia Mattos +3 more
For graphs $G$ and $H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if any proper edge-coloring of $G$ contains a rainbow copy of $H$, i.e., a copy where no color appears … For graphs $G$ and $H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if any proper edge-coloring of $G$ contains a rainbow copy of $H$, i.e., a copy where no color appears more than once. Kohayakawa, Konstadinidis and the last author proved that the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow}H$ is at most $n^{-1/m_2(H)}$. Previous results have matched the lower bound for this anti-Ramsey threshold for cycles and complete graphs with at least 5 vertices. Kohayakawa, Konstadinidis and the last author also presented an infinite family of graphs $H$ for which the anti-Ramsey threshold is asymptotically smaller than $n^{-1/m_2(H)}$. In this paper, we devise a framework that provides a richer and more complex family of such graphs that includes all the previously known examples.

On the Anti-Ramsey Threshold for Non-Balanced Graphs

2024-03-21
P.M.A.G. Araújo , Táısa Martins , Letícia Mattos +3 more
For graphs $G,H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if for every proper edge-coloring of $G$ there is a rainbow copy of $H$, i.e., a copy where no color appears … For graphs $G,H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if for every proper edge-coloring of $G$ there is a rainbow copy of $H$, i.e., a copy where no color appears more than once. Kohayakawa, Konstadinidis and the last author proved that the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow} H$ is at most $n^{-1/m_2(H)}$. Previous results have matched the lower bound for this anti-Ramsey threshold for cycles and complete graphs with at least 5 vertices. Kohayakawa, Konstadinidis and the last author also presented an infinite family of graphs $H$ for which the anti-Ramsey threshold is asymptotically smaller than $n^{-1/m_2(H)}$. In this paper, we devise a framework that provides a richer family of such graphs.
View PDF Chat

On Multicolor Turán Numbers

2024-08-26
József Balogh , Anita Liebenau , Letícia Mattos +1 more

Long rainbow arithmetic progressions.

2019-05-09
József Balogh , William Linz , Letícia Mattos
Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungic, Licht … Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungic, Licht (Fox), Mahdian, Nesetril and Radoicic proved that $\lfloor{\frac{k^2}{4}\rfloor}\le T_k$. We almost close the gap between the upper and lower bounds by proving that $T_k \le k^2e^{(\ln\ln k)^2(1+o(1))}$. Conlon, Fox and Sudakov have independently shown a stronger statement that $T_k=O(k^2\log k)$.

Long rainbow arithmetic progressions

2021-01-01
József Balogh , William Linz , Letícia Mattos
Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungic, Licht … Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungic, Licht (Fox), Mahdian, Nesetril and Radoicic proved that $\lfloor{\frac{k^2}{4}\rfloor}\le T_k$. We almost close the gap between the upper and lower bounds by proving that $T_k \le k^2e^{(\ln\ln k)^2(1+o(1))}$. Conlon, Fox and Sudakov have independently shown a stronger statement that $T_k=O(k^2\log k)$.
View PDF Chat

Counting $r$-graphs without forbidden configurations

2021-01-01
József Balogh , Felix Christian Clemen , Letícia Mattos
One of the major problems in combinatorics is to determine the number of $r$-uniform hypergraphs ($r$-graphs) on $n$ vertices which are free of certain forbidden structures. This problem dates back … One of the major problems in combinatorics is to determine the number of $r$-uniform hypergraphs ($r$-graphs) on $n$ vertices which are free of certain forbidden structures. This problem dates back to the work of Erd\H{o}s, Kleitman and Rothschild, who showed that the number of $K_r$-free graphs on $n$ vertices is $2^{\text{ex}(n,K_r)+o(n^2)}$. Their work was later extended to forbidding graphs as induced subgraphs by Pr\"omel and Steger. Here, we consider one of the most basic counting problems for $3$-graphs. Let $E_1$ be the $3$-graph with $4$ vertices and $1$ edge. What is the number of induced $\{K_4^3,E_1\}$-free $3$-graphs on $n$ vertices? We show that the number of such $3$-graphs is of order $n^{\Theta(n^2)}$. More generally, we determine asymptotically the number of induced $\mathcal{F}$-free $3$-graphs on $n$ vertices for all families $\mathcal{F}$ of $3$-graphs on $4$ vertices. We also provide upper bounds on the number of $r$-graphs on $n$ vertices which do not induce $i \in L$ edges on any set of $k$ vertices, where $L \subseteq \big \{0,1,\ldots,\binom{k}{r} \big\}$ is a list which does not contain $3$ consecutive integers in its complement. Our bounds are best possible up to a constant multiplicative factor in the exponent when $k = r+1$. The main tool behind our proof is counting the solutions of a constraint satisfaction problem.

New Lower Bounds For Essential Covers Of The Cube

2022-01-01
Igor Araújo , József Balogh , Letícia Mattos
An essential cover of the vertices of the $n$-cube $\{0,1\}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at … An essential cover of the vertices of the $n$-cube $\{0,1\}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with $\lceil \frac{n}{2} \rceil + 1$ hyperplanes and showed that $\Omega(\sqrt{n})$ hyperplanes are required. Recently, Yehuda and Yehudayoff improved the lower bound by showing that any essential cover of the $n$-cube contains at least $\Omega(n^{0.52})$ hyperplanes. In this paper, building on the method of Yehuda and Yehudayoff, we prove that $\Omega \left( \frac{n^{5/9}}{(\log n)^{4/9}} \right)$ hyperplanes are needed.
View PDF Chat

Long rainbow arithmetic progressions

2019-01-01
József Balogh , William Linz , Letícia Mattos
Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungi\'{c}, Licht … Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungi\'{c}, Licht (Fox), Mahdian, Nesetril and Radoici\'{c} proved that $\lfloor{\frac{k^2}{4}\rfloor}\le T_k$. We almost close the gap between the upper and lower bounds by proving that $T_k \le k^2e^{(\ln\ln k)^2(1+o(1))}$. Conlon, Fox and Sudakov have independently shown a stronger statement that $T_k=O(k^2\log k)$.

Local central limit theorem for triangle counts in sparse random graphs

2023-01-01
P.M.A.G. Araújo , Letícia Mattos
Let $X_H$ be the number of copies of a fixed graph $H$ in $G(n,p)$. In 2016, Gilmer and Kopparty conjectured that a local central limit theorem should hold for $X_H$ … Let $X_H$ be the number of copies of a fixed graph $H$ in $G(n,p)$. In 2016, Gilmer and Kopparty conjectured that a local central limit theorem should hold for $X_H$ as long as $H$ is connected, $p \gg n^{-1/m(H)}$ and $n^2(1-p)\gg 1$. Recently, Sah and Sahwney showed that the Gilmer--Kopparty conjecture holds for constant $p$. In this paper, we show that the Gilmer--Kopparty conjecture holds for triangle counts in the sparse range. More precisely, there exists $C>0$ such that if $p \in (Cn^{-1/2}, 1/2)$, then \[ \sup_{x\in \mathcal{L}}\left| \dfrac{1}{\sqrt{2\pi}}e^{-x^2/2}-\sigma\cdot \mathbb{P}(X^* = x)\right|\rightarrow 0,\] where $\sigma^2 = \mathbb{V}\text{ar}(X_{K_3})$, $X^{*}=(X_{K_3}-\mathbb{E}(X_{K_3}))/\sigma$ and $\mathcal{L}$ is the support of $X^*$. By combining our result with the results of R\"ollin--Ross and Gilmer--Kopparty, this establishes the Gilmer--Kopparty conjecture for triangle counts for $n^{-1}\ll p < c$, for any constant $c\in (0,1)$. Our result is the first local central limit theorem for subgraph counts above the $m_2$-density.
View PDF Chat

On product Schur triples in the integers

2023-01-01
Letícia Mattos , Domenico Mergoni Cecchelli , Olaf Parczyk
Schur's theorem states that in any $k$-colouring of the set of integers $[n]$ there is a monochromatic solution to $a+b=c$, provided $n$ is sufficiently large. Abbott and Wang studied the … Schur's theorem states that in any $k$-colouring of the set of integers $[n]$ there is a monochromatic solution to $a+b=c$, provided $n$ is sufficiently large. Abbott and Wang studied the size of the largest subset of $[n]$ such that there is a $k$-colouring avoiding a monochromatic $a+b=c$. In other directions, the minimum number of $a+b=c$ in $k$-colourings of $[n]$ and the probability threshold in random subsets of $[n]$ for the property of having a monochromatic $a+b=c$ in any $k$-colouring were investigated. In this paper, we study natural generalisations of these streams to products $ab=c$, in a deterministic, random, and randomly perturbed environments.
View PDF Chat

On multicolor Tur\'an numbers

2024-02-07
József Balogh , Anita Liebenau , Letícia Mattos +1 more
We address a problem which is a generalization of Tur\'an-type problems recently introduced by Imolay, Karl, Nagy and V\'ali. Let $F$ be a fixed graph and let $G$ be the … We address a problem which is a generalization of Tur\'an-type problems recently introduced by Imolay, Karl, Nagy and V\'ali. Let $F$ be a fixed graph and let $G$ be the union of $k$ edge-disjoint copies of $F$, namely $G = \mathbin{\dot{\cup}}_{i=1}^{k} F_i$, where each $F_i$ is isomorphic to a fixed graph $F$ and $E(F_i)\cap E(F_j)=\emptyset$ for all $i \neq j$. We call a subgraph $H\subseteq G$ multicolored if $H$ and $F_i$ share at most one edge for all $i$. Define $\text{ex}_F(H,n)$ to be the maximum value $k$ such that there exists $G = \mathbin{\dot{\cup}}_{i=1}^{k} F_i$ on $n$ vertices without a multicolored copy of $H$. We show that $\text{ex}_{C_5}(C_3,n) \le n^2/25 + 3n/25+o(n)$ and that all extremal graphs are close to a blow-up of the 5-cycle. This bound is tight up to the linear error term.
View PDF Chat

Clique packings in random graphs

2024-05-01
Simon Griffiths , Letícia Mattos
We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erd\H{o}s-R\'enyi random graph $G(n,p)$. Recently Acan and Kahn showed that the largest such family … We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erd\H{o}s-R\'enyi random graph $G(n,p)$. Recently Acan and Kahn showed that the largest such family contains only $O(n^2/(\log{n})^3)$ cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound, $\Omega(n^2/(\log{n})^3)$, by considering a random graph process which sequentially selects and deletes near-maximal cliques. To analyse this process we use the Differential Equation Method. We also give a new proof of the upper bound $O(n^2/(\log{n})^3)$ and discuss the problem of the precise size of the largest such clique packing.
View PDF Chat

Subgraphs of random graphs in hereditary families

2024-05-15
Alexander Clifton , Hong Liu , Letícia Mattos +1 more
For a graph $G$ and a hereditary property $\mathcal{P}$, let $\text{ex}(G,\mathcal{P})$ denote the maximum number of edges of a subgraph of $G$ that belongs to $\mathcal{P}$. We prove that for … For a graph $G$ and a hereditary property $\mathcal{P}$, let $\text{ex}(G,\mathcal{P})$ denote the maximum number of edges of a subgraph of $G$ that belongs to $\mathcal{P}$. We prove that for every non-trivial hereditary property $\mathcal{P}$ such that $L \notin \mathcal{P}$ for some bipartite graph $L$ and for every fixed $p \in (0,1)$ we have \[\text{ex}(G(n,p),\mathcal{P}) \le n^{2-\varepsilon}\] with high probability, for some constant $\varepsilon = \varepsilon(\mathcal{P})>0$. This answers a question of Alon, Krivelevich and Samotij.
View PDF Chat

New lower bounds for essential covers of the cube

2024-12-01
Igor Araújo , József Balogh , Letícia Mattos

On Product Schur Triples in the Integers

2025-05-09
Letícia Mattos , Domenico Mergoni Cecchelli , Olaf Parczyk
View PDF Chat

On Product Schur Triples in the Integers

2025-05-09
Letícia Mattos , Domenico Mergoni Cecchelli , Olaf Parczyk
View PDF Chat

New lower bounds for essential covers of the cube

2024-12-01
Igor Araújo , József Balogh , Letícia Mattos

On Multicolor Turán Numbers

2024-08-26
József Balogh , Anita Liebenau , Letícia Mattos +1 more

Subgraphs of random graphs in hereditary families

2024-05-15
Alexander Clifton , Hong Liu , Letícia Mattos +1 more
For a graph $G$ and a hereditary property $\mathcal{P}$, let $\text{ex}(G,\mathcal{P})$ denote the maximum number of edges of a subgraph of $G$ that belongs to $\mathcal{P}$. We prove that for … For a graph $G$ and a hereditary property $\mathcal{P}$, let $\text{ex}(G,\mathcal{P})$ denote the maximum number of edges of a subgraph of $G$ that belongs to $\mathcal{P}$. We prove that for every non-trivial hereditary property $\mathcal{P}$ such that $L \notin \mathcal{P}$ for some bipartite graph $L$ and for every fixed $p \in (0,1)$ we have \[\text{ex}(G(n,p),\mathcal{P}) \le n^{2-\varepsilon}\] with high probability, for some constant $\varepsilon = \varepsilon(\mathcal{P})>0$. This answers a question of Alon, Krivelevich and Samotij.
View PDF Chat

Clique packings in random graphs

2024-05-01
Simon Griffiths , Letícia Mattos
We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erd\H{o}s-R\'enyi random graph $G(n,p)$. Recently Acan and Kahn showed that the largest such family … We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erd\H{o}s-R\'enyi random graph $G(n,p)$. Recently Acan and Kahn showed that the largest such family contains only $O(n^2/(\log{n})^3)$ cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound, $\Omega(n^2/(\log{n})^3)$, by considering a random graph process which sequentially selects and deletes near-maximal cliques. To analyse this process we use the Differential Equation Method. We also give a new proof of the upper bound $O(n^2/(\log{n})^3)$ and discuss the problem of the precise size of the largest such clique packing.
View PDF Chat

On the Anti-Ramsey Threshold for Non-Balanced Graphs

2024-03-21
P.M.A.G. Araújo , Táısa Martins , Letícia Mattos +3 more
For graphs $G,H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if for every proper edge-coloring of $G$ there is a rainbow copy of $H$, i.e., a copy where no color appears … For graphs $G,H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if for every proper edge-coloring of $G$ there is a rainbow copy of $H$, i.e., a copy where no color appears more than once. Kohayakawa, Konstadinidis and the last author proved that the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow} H$ is at most $n^{-1/m_2(H)}$. Previous results have matched the lower bound for this anti-Ramsey threshold for cycles and complete graphs with at least 5 vertices. Kohayakawa, Konstadinidis and the last author also presented an infinite family of graphs $H$ for which the anti-Ramsey threshold is asymptotically smaller than $n^{-1/m_2(H)}$. In this paper, we devise a framework that provides a richer family of such graphs.
View PDF Chat

On multicolor Tur\'an numbers

2024-02-07
József Balogh , Anita Liebenau , Letícia Mattos +1 more
We address a problem which is a generalization of Tur\'an-type problems recently introduced by Imolay, Karl, Nagy and V\'ali. Let $F$ be a fixed graph and let $G$ be the … We address a problem which is a generalization of Tur\'an-type problems recently introduced by Imolay, Karl, Nagy and V\'ali. Let $F$ be a fixed graph and let $G$ be the union of $k$ edge-disjoint copies of $F$, namely $G = \mathbin{\dot{\cup}}_{i=1}^{k} F_i$, where each $F_i$ is isomorphic to a fixed graph $F$ and $E(F_i)\cap E(F_j)=\emptyset$ for all $i \neq j$. We call a subgraph $H\subseteq G$ multicolored if $H$ and $F_i$ share at most one edge for all $i$. Define $\text{ex}_F(H,n)$ to be the maximum value $k$ such that there exists $G = \mathbin{\dot{\cup}}_{i=1}^{k} F_i$ on $n$ vertices without a multicolored copy of $H$. We show that $\text{ex}_{C_5}(C_3,n) \le n^2/25 + 3n/25+o(n)$ and that all extremal graphs are close to a blow-up of the 5-cycle. This bound is tight up to the linear error term.
View PDF Chat

Local central limit theorem for triangle counts in sparse random graphs

2023-01-01
P.M.A.G. Araújo , Letícia Mattos
Let $X_H$ be the number of copies of a fixed graph $H$ in $G(n,p)$. In 2016, Gilmer and Kopparty conjectured that a local central limit theorem should hold for $X_H$ … Let $X_H$ be the number of copies of a fixed graph $H$ in $G(n,p)$. In 2016, Gilmer and Kopparty conjectured that a local central limit theorem should hold for $X_H$ as long as $H$ is connected, $p \gg n^{-1/m(H)}$ and $n^2(1-p)\gg 1$. Recently, Sah and Sahwney showed that the Gilmer--Kopparty conjecture holds for constant $p$. In this paper, we show that the Gilmer--Kopparty conjecture holds for triangle counts in the sparse range. More precisely, there exists $C>0$ such that if $p \in (Cn^{-1/2}, 1/2)$, then \[ \sup_{x\in \mathcal{L}}\left| \dfrac{1}{\sqrt{2\pi}}e^{-x^2/2}-\sigma\cdot \mathbb{P}(X^* = x)\right|\rightarrow 0,\] where $\sigma^2 = \mathbb{V}\text{ar}(X_{K_3})$, $X^{*}=(X_{K_3}-\mathbb{E}(X_{K_3}))/\sigma$ and $\mathcal{L}$ is the support of $X^*$. By combining our result with the results of R\"ollin--Ross and Gilmer--Kopparty, this establishes the Gilmer--Kopparty conjecture for triangle counts for $n^{-1}\ll p < c$, for any constant $c\in (0,1)$. Our result is the first local central limit theorem for subgraph counts above the $m_2$-density.
View PDF Chat

On product Schur triples in the integers

2023-01-01
Letícia Mattos , Domenico Mergoni Cecchelli , Olaf Parczyk
Schur's theorem states that in any $k$-colouring of the set of integers $[n]$ there is a monochromatic solution to $a+b=c$, provided $n$ is sufficiently large. Abbott and Wang studied the … Schur's theorem states that in any $k$-colouring of the set of integers $[n]$ there is a monochromatic solution to $a+b=c$, provided $n$ is sufficiently large. Abbott and Wang studied the size of the largest subset of $[n]$ such that there is a $k$-colouring avoiding a monochromatic $a+b=c$. In other directions, the minimum number of $a+b=c$ in $k$-colourings of $[n]$ and the probability threshold in random subsets of $[n]$ for the property of having a monochromatic $a+b=c$ in any $k$-colouring were investigated. In this paper, we study natural generalisations of these streams to products $ab=c$, in a deterministic, random, and randomly perturbed environments.
View PDF Chat

Counting r-graphs without forbidden configurations

2022-07-27
József Balogh , Felix Christian Clemen , Letícia Mattos
View PDF Chat

Asymmetric Ramsey properties of random graphs involving cliques and cycles

2022-07-21
Anita Liebenau , Letícia Mattos , Walner Mendonça +1 more
Abstract We say that if, in every edge coloring , we can find either a 1‐colored copy of or a 2‐colored copy of . The well‐known Kohayakawa‐Kreuter conjecture states that … Abstract We say that if, in every edge coloring , we can find either a 1‐colored copy of or a 2‐colored copy of . The well‐known Kohayakawa‐Kreuter conjecture states that the threshold for the property is equal to , where is given by for any pair of graphs and with . In this article, we show the 0‐statement of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques.
View PDF Chat

On the anti-Ramsey threshold for non-balanced graphs

2022-01-01
P.M.A.G. Araújo , Táısa Martins , Letícia Mattos +3 more
For graphs $G$ and $H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if any proper edge-coloring of $G$ contains a rainbow copy of $H$, i.e., a copy where no color appears … For graphs $G$ and $H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if any proper edge-coloring of $G$ contains a rainbow copy of $H$, i.e., a copy where no color appears more than once. Kohayakawa, Konstadinidis and the last author proved that the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow}H$ is at most $n^{-1/m_2(H)}$. Previous results have matched the lower bound for this anti-Ramsey threshold for cycles and complete graphs with at least 5 vertices. Kohayakawa, Konstadinidis and the last author also presented an infinite family of graphs $H$ for which the anti-Ramsey threshold is asymptotically smaller than $n^{-1/m_2(H)}$. In this paper, we devise a framework that provides a richer and more complex family of such graphs that includes all the previously known examples.

New Lower Bounds For Essential Covers Of The Cube

2022-01-01
Igor Araújo , József Balogh , Letícia Mattos
An essential cover of the vertices of the $n$-cube $\{0,1\}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at … An essential cover of the vertices of the $n$-cube $\{0,1\}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with $\lceil \frac{n}{2} \rceil + 1$ hyperplanes and showed that $\Omega(\sqrt{n})$ hyperplanes are required. Recently, Yehuda and Yehudayoff improved the lower bound by showing that any essential cover of the $n$-cube contains at least $\Omega(n^{0.52})$ hyperplanes. In this paper, building on the method of Yehuda and Yehudayoff, we prove that $\Omega \left( \frac{n^{5/9}}{(\log n)^{4/9}} \right)$ hyperplanes are needed.
View PDF Chat

On the singularity of random symmetric matrices

2021-03-30
Marcelo Campos , Letícia Mattos , Robert Morris +1 more
A well-known conjecture states that a random symmetric n×n matrix with entries in {−1,1} is singular with probability Θ(n22−n). We prove that the probability of this event is at most … A well-known conjecture states that a random symmetric n×n matrix with entries in {−1,1} is singular with probability Θ(n22−n). We prove that the probability of this event is at most exp(−Ω(n)), improving the best-known bound of exp(−Ω(n1∕4 logn)), which was obtained recently by Ferber and Jain. The main new ingredient is an inverse Littlewood–Offord theorem in Zpn that applies under very mild conditions, whose statement is inspired by the method of hypergraph containers.
View PDF Chat

Long rainbow arithmetic progressions

2021-01-01
József Balogh , William Linz , Letícia Mattos
Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungic, Licht … Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungic, Licht (Fox), Mahdian, Nesetril and Radoicic proved that $\lfloor{\frac{k^2}{4}\rfloor}\le T_k$. We almost close the gap between the upper and lower bounds by proving that $T_k \le k^2e^{(\ln\ln k)^2(1+o(1))}$. Conlon, Fox and Sudakov have independently shown a stronger statement that $T_k=O(k^2\log k)$.
View PDF Chat

Counting $r$-graphs without forbidden configurations

2021-01-01
József Balogh , Felix Christian Clemen , Letícia Mattos
One of the major problems in combinatorics is to determine the number of $r$-uniform hypergraphs ($r$-graphs) on $n$ vertices which are free of certain forbidden structures. This problem dates back … One of the major problems in combinatorics is to determine the number of $r$-uniform hypergraphs ($r$-graphs) on $n$ vertices which are free of certain forbidden structures. This problem dates back to the work of Erd\H{o}s, Kleitman and Rothschild, who showed that the number of $K_r$-free graphs on $n$ vertices is $2^{\text{ex}(n,K_r)+o(n^2)}$. Their work was later extended to forbidding graphs as induced subgraphs by Pr\"omel and Steger. Here, we consider one of the most basic counting problems for $3$-graphs. Let $E_1$ be the $3$-graph with $4$ vertices and $1$ edge. What is the number of induced $\{K_4^3,E_1\}$-free $3$-graphs on $n$ vertices? We show that the number of such $3$-graphs is of order $n^{\Theta(n^2)}$. More generally, we determine asymptotically the number of induced $\mathcal{F}$-free $3$-graphs on $n$ vertices for all families $\mathcal{F}$ of $3$-graphs on $4$ vertices. We also provide upper bounds on the number of $r$-graphs on $n$ vertices which do not induce $i \in L$ edges on any set of $k$ vertices, where $L \subseteq \big \{0,1,\ldots,\binom{k}{r} \big\}$ is a list which does not contain $3$ consecutive integers in its complement. Our bounds are best possible up to a constant multiplicative factor in the exponent when $k = r+1$. The main tool behind our proof is counting the solutions of a constraint satisfaction problem.

Asymmetric Ramsey Properties of Random Graphs for Cliques and Cycles

2020-01-01
Anita Liebenau , Letícia Mattos , Walner Mendonça +1 more
We say that $G \to (F,H)$ if, in every edge colouring $c: E(G) \to \{1,2\}$, we can find either a $1$-coloured copy of $F$ or a $2$-coloured copy of $H$. … We say that $G \to (F,H)$ if, in every edge colouring $c: E(G) \to \{1,2\}$, we can find either a $1$-coloured copy of $F$ or a $2$-coloured copy of $H$. The well-known Kohayakawa--Kreuter conjecture states that the threshold for the property $G(n,p) \to (F,H)$ is equal to $n^{-1/m_{2}(F,H)}$, where $m_{2}(F,H)$ is given by \[ m_{2}(F,H):= \max \left\{\dfrac{e(J)}{v(J)-2+1/m_2(H)} : J \subseteq F, e(J)\ge 1 \right\}. \] In this paper, we show the $0$-statement of the Kohayakawa--Kreuter conjecture for every pair of cycles and cliques.

Long rainbow arithmetic progressions.

2019-05-09
József Balogh , William Linz , Letícia Mattos
Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungic, Licht … Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungic, Licht (Fox), Mahdian, Nesetril and Radoicic proved that $\lfloor{\frac{k^2}{4}\rfloor}\le T_k$. We almost close the gap between the upper and lower bounds by proving that $T_k \le k^2e^{(\ln\ln k)^2(1+o(1))}$. Conlon, Fox and Sudakov have independently shown a stronger statement that $T_k=O(k^2\log k)$.

On the singularity of random symmetric matrices

2019-04-25
Marcelo Campos , Letícia Mattos , Robert Morris +1 more
A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta\big( n^2 2^{-n} \big)$. In this paper we prove that … A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta\big( n^2 2^{-n} \big)$. In this paper we prove that the probability of this event is at most $\exp\big( - \Omega( \sqrt{n} ) \big)$, improving the best known bound of $\exp\big( - \Omega( n^{1/4} \sqrt{\log n} ) \big)$, which was obtained recently by Ferber and Jain. The main new ingredient is an inverse Littlewood-Offord theorem in $\mathbb{Z}_p^n$ that applies under very mild conditions, whose statement is inspired by the method of hypergraph containers.

On the singularity of random symmetric matrices

2019-01-01
Marcelo Campos , Letícia Mattos , Robert D. Morris +1 more
A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta\big( n^2 2^{-n} \big)$. In this paper we prove that … A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta\big( n^2 2^{-n} \big)$. In this paper we prove that the probability of this event is at most $\exp\big( - \Omega( \sqrt{n} ) \big)$, improving the best known bound of $\exp\big( - \Omega( n^{1/4} \sqrt{\log n} ) \big)$, which was obtained recently by Ferber and Jain. The main new ingredient is an inverse Littlewood-Offord theorem in $\mathbb{Z}_p^n$ that applies under very mild conditions, whose statement is inspired by the method of hypergraph containers.

Long rainbow arithmetic progressions

2019-01-01
József Balogh , William Linz , Letícia Mattos
Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungi\'{c}, Licht … Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungi\'{c}, Licht (Fox), Mahdian, Nesetril and Radoici\'{c} proved that $\lfloor{\frac{k^2}{4}\rfloor}\le T_k$. We almost close the gap between the upper and lower bounds by proving that $T_k \le k^2e^{(\ln\ln k)^2(1+o(1))}$. Conlon, Fox and Sudakov have independently shown a stronger statement that $T_k=O(k^2\log k)$.
Coauthor Papers Together
József Balogh 9
Natasha Morrison 5
Walner Mendonça 4
Anita Liebenau 4
William Linz 3
P.M.A.G. Araújo 3
Domenico Mergoni Cecchelli 2
Igor Araújo 2
Jozef Skokan 2
Robert Morris 2
Marcelo Campos 2
Luíz Felipe Pinho Moreira 2
Táısa Martins 2
Guilherme Oliveira Mota 2
Olaf Parczyk 2
Felix Christian Clemen 2
Alexander Clifton 1
Hong Liu 1
Michael Zheng 1
Simon Griffiths 1
Robert D. Morris 1
Marcelo Campos 1

Independent sets in hypergraphs

2014-08-07
József Balogh , Robert Morris , Wojciech Samotij
Many important theorems and conjectures in combinatorics, such as the theorem of Szemerédi on arithmetic progressions and the Erdős–Stone Theorem in extremal graph theory, can be phrased as statements about … Many important theorems and conjectures in combinatorics, such as the theorem of Szemerédi on arithmetic progressions and the Erdős–Stone Theorem in extremal graph theory, can be phrased as statements about families of independent sets in certain uniform hypergraphs. In recent years, an important trend in the area has been to extend such classical results to the so-called ‘sparse random setting’. This line of research has recently culminated in the breakthroughs of Conlon and Gowers and of Schacht, who developed general tools for solving problems of this type. Although these two articles solved very similar sets of longstanding open problems, the methods used are very different from one another and have different strengths and weaknesses. In this article, we provide a third, completely different, approach to proving extremal and structural results in sparse random sets that also yields their natural ‘counting’ counterparts. We give a structural characterization of the independent sets in a large class of uniform hypergraphs by showing that every independent set is almost contained in one of a small number of relatively sparse sets. We then derive many interesting results as fairly straightforward consequences of this abstract theorem. In particular, we prove the well-known conjecture of Kohayakawa, Łuczak, and Rödl, a probabilistic embedding lemma for sparse graphs. We also give alternative proofs of many of the results of Conlon and Gowers and of Schacht, such as sparse random versions of Szemerédi’s theorem, the Erdős–Stone Theorem, and the Erdős–Simonovits Stability Theorem, and obtain their natural ‘counting’ versions, which in some cases are considerably stronger. For example, we show that for each positive <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="beta"> <mml:semantics> <mml:mi>β<!-- β --></mml:mi> <mml:annotation encoding="application/x-tex">\beta</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and integer <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, there are at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartBinomialOrMatrix beta n Choose m EndBinomialOrMatrix"> <mml:semantics> <mml:mrow> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-OPEN"> <mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo> </mml:mrow> </mml:mstyle> <mml:mfrac linethickness="0"> <mml:mrow> <mml:mi>β<!-- β --></mml:mi> <mml:mi>n</mml:mi> </mml:mrow> <mml:mi>m</mml:mi> </mml:mfrac> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-CLOSE"> <mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo> </mml:mrow> </mml:mstyle> </mml:mrow> <mml:annotation encoding="application/x-tex">\binom {\beta n}{m}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> sets of size <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"> <mml:semantics> <mml:mi>m</mml:mi> <mml:annotation encoding="application/x-tex">m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> that contain no <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-term arithmetic progression, provided that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m greater-than-or-slanted-equals upper C n Superscript 1 minus 1 slash left-parenthesis k minus 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>⩾<!-- ⩾ --></mml:mo> <mml:mi>C</mml:mi> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">m \geqslant Cn^{1-1/(k-1)}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C"> <mml:semantics> <mml:mi>C</mml:mi> <mml:annotation encoding="application/x-tex">C</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a constant depending only on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="beta"> <mml:semantics> <mml:mi>β<!-- β --></mml:mi> <mml:annotation encoding="application/x-tex">\beta</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We also obtain new results, such as a sparse version of the Erdős–Frankl–Rödl Theorem on the number of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H"> <mml:semantics> <mml:mi>H</mml:mi> <mml:annotation encoding="application/x-tex">H</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-free graphs and, as a consequence of the KŁR conjecture, we extend a result of Rödl and Ruciński on Ramsey properties in sparse random graphs to the general, non-symmetric setting.
View PDF Chat

Hypergraph containers

2015-01-07
David Saxton , Andrew Thomason
View PDF Chat

On a lemma of Littlewood and Offord

1945-01-01
P. Erdős
Recently Littlewood and Recently Littlewood and
View PDF Chat

Inverse Littlewood–Offord theorems and the condition number of random discrete matrices

2009-03-01
Terence Tao , Van Vu
Consider a random sum η 1 v 1 + • • • + η n v n , where η 1 , . . ., η n are independently and … Consider a random sum η 1 v 1 + • • • + η n v n , where η 1 , . . ., η n are independently and identically distributed (i.i.d.) random signs and v 1 , . . ., v n are integers.The Littlewood-Offord problem asks to maximize concentration probabilities such as P(ηIn this paper we develop an inverse Littlewood-Offord theory (somewhat in the spirit of Freiman's inverse theory in additive combinatorics), which starts with the hypothesis that a concentration probability is large, and concludes that almost all of the v 1 , . . ., v n are efficiently contained in a generalized arithmetic progression.As an application we give a new bound on the magnitude of the least singular value of a random Bernoulli matrix, which in turn provides upper tail estimates on the condition number.
View PDF Chat

Inverse Littlewood–Offord problems and the singularity of random symmetric matrices

2012-03-01
Hoi H. Nguyen
Let Mn denote a random symmetric (n×n)-matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take value −1 and 1 with probability 1/2). Improving the … Let Mn denote a random symmetric (n×n)-matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take value −1 and 1 with probability 1/2). Improving the earlier result by Costello, Tao, and Vu [4], we show that Mn is nonsingular with probability 1−O(n−C) for any positive constant C. The proof uses an inverse Littlewood–Offord result for quadratic forms, which is of interest of its own.
View PDF Chat

On a Problem of Formal Logic

1930-01-01
Frank Plumpton Ramsey

On the Kolmogorov-Rogozin inequality for the concentration function

1966-01-01
Carl-Gustav Esseen

SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS

2017-01-01
Luca Gugelmann , Rajko Nenadov , Yury Person +3 more
A celebrated result of Rödl and Ruciński states that for every graph $F$ , which is not a forest of stars and paths of length 3, and fixed number of … A celebrated result of Rödl and Ruciński states that for every graph $F$ , which is not a forest of stars and paths of length 3, and fixed number of colours $r\geqslant 2$ there exist positive constants $c,C$ such that for $p\leqslant cn^{-1/m_{2}(F)}$ the probability that every colouring of the edges of the random graph $G(n,p)$ contains a monochromatic copy of $F$ is $o(1)$ (the ‘0-statement’), while for $p\geqslant Cn^{-1/m_{2}(F)}$ it is $1-o(1)$ (the ‘1-statement’). Here $m_{2}(F)$ denotes the 2-density of $F$ . On the other hand, the case where $F$ is a forest of stars has a coarse threshold which is determined by the appearance of a certain small subgraph in $G(n,p)$ . Recently, the natural extension of the 1-statement of this theorem to $k$ -uniform hypergraphs was proved by Conlon and Gowers and, independently, by Friedgut, Rödl and Schacht. In particular, they showed an upper bound of order $n^{-1/m_{k}(F)}$ for the 1-statement, where $m_{k}(F)$ denotes the $k$ -density of $F$ . Similarly as in the graph case, it is known that the threshold for star-like hypergraphs is given by the appearance of small subgraphs. In this paper we show that another type of threshold exists if $k\geqslant 4$ : there are $k$ -uniform hypergraphs for which the threshold is determined by the asymmetric Ramsey problem in which a different hypergraph has to be avoided in each colour class. Along the way we obtain a general bound on the 1-statement for asymmetric Ramsey properties in random hypergraphs. This extends the work of Kohayakawa and Kreuter, and of Kohayakawa, Schacht and Spöhel who showed a similar result in the graph case. We prove the corresponding 0-statement for hypergraphs satisfying certain balancedness conditions.
View PDF Chat

Threshold functions for asymmetric Ramsey properties with respect to vertex colorings

1996-10-01
B. Kreuter
In this note we investigate Ramsey properties of random graphs. The threshold functions for symmetric Ramsey properties with respect to vertex colorings were determined by Łuczak, Ruciński, and Voigt [6]. … In this note we investigate Ramsey properties of random graphs. The threshold functions for symmetric Ramsey properties with respect to vertex colorings were determined by Łuczak, Ruciński, and Voigt [6]. As a generalization of this problem we consider asymmetric Ramsey properties and establish the values of the threshold functions. Furthermore, we investigate canonical colorings. © 1996 John Wiley & Sons, Inc.
View PDF Chat

Ramsey properties of random graphs

1992-09-01
Tomasz Łuczak , Andrzej Ruciński , Bernd Voigt

THE METHOD OF HYPERGRAPH CONTAINERS

2019-05-01
József Balogh , Robert Morris , Wojciech Samotij
View PDF Chat

Threshold functions for asymmetric Ramsey properties involving cycles

1997-10-01
Yoshiharu Kohayakawa , B. Kreuter
We consider the binomial random graph Gp and determine a sharp threshold function for the edge-Ramsey propertyfor all l1,…,lr, where Cl denotes the cycle of length l. As deterministic consequences … We consider the binomial random graph Gp and determine a sharp threshold function for the edge-Ramsey propertyfor all l1,…,lr, where Cl denotes the cycle of length l. As deterministic consequences of our results, we prove the existence of sparse graphs having the above Ramsey property as well as the existence of infinitely many critical graphs with respect to the property above. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11, 245–276, 1997
View PDF Chat

From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices

2009-02-24
Terence Tao , Van Vu
The famous circular law asserts that if $M_n$ is an $n \times n$ matrix with iid complex entries of mean zero and unit variance, then the empirical spectral distribution of … The famous circular law asserts that if $M_n$ is an $n \times n$ matrix with iid complex entries of mean zero and unit variance, then the empirical spectral distribution of the normalized matrix $\frac {1}{\sqrt {n}} M_n$ converges both in probability and almost surely to the uniform distribution on the unit disk $\{ z \in \mathbf {C}: |z| \leq 1 \}$. After a long sequence of partial results that verified this law under additional assumptions on the distribution of the entries, the circular law is now known to be true for arbitrary distributions with mean zero and unit variance. In this survey we describe some of the key ingredients used in the establishment of the circular law at this level of generality, in particular recent advances in understanding the Littlewood-Offord problem and its inverse.
View PDF Chat

Sharp thresholds for certain Ramsey properties of random graphs

2000-01-01
Ehud Friedgut , Michael Krivelevich

Invertibility of symmetric random matrices

2012-05-11
Roman Vershynin
Abstract We study symmetric random matrices H , possibly discrete, with iid above‐diagonal entries. We show that H is singular with probability at most , and . Furthermore, the spectrum … Abstract We study symmetric random matrices H , possibly discrete, with iid above‐diagonal entries. We show that H is singular with probability at most , and . Furthermore, the spectrum of H is delocalized on the optimal scale . These results improve upon a polynomial singularity bound due to Costello, Tao and Vu, and they generalize, up to constant factors, results of Tao and Vu, and Erdös, Schlein and Yau.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 135‐182, 2014
View PDF Chat

The Littlewood–Offord problem and invertibility of random matrices

2008-03-11
Mark Rudelson , Roman Vershynin
View PDF Chat

SINGULARITY OF RANDOM SYMMETRIC MATRICES—A COMBINATORIAL APPROACH TO IMPROVED BOUNDS

2019-01-01
Asaf Ferber , Vishesh Jain
Let $M_{n}$ denote a random symmetric $n\times n$ matrix whose upper-diagonal entries are independent and identically distributed Bernoulli random variables (which take values $1$ and $-1$ with probability $1/2$ each). … Let $M_{n}$ denote a random symmetric $n\times n$ matrix whose upper-diagonal entries are independent and identically distributed Bernoulli random variables (which take values $1$ and $-1$ with probability $1/2$ each). It is widely conjectured that $M_{n}$ is singular with probability at most $(2+o(1))^{-n}$ . On the other hand, the best known upper bound on the singularity probability of $M_{n}$ , due to Vershynin (2011), is $2^{-n^{c}}$ , for some unspecified small constant $c&gt;0$ . This improves on a polynomial singularity bound due to Costello, Tao, and Vu (2005), and a bound of Nguyen (2011) showing that the singularity probability decays faster than any polynomial. In this paper, improving on all previous results, we show that the probability of singularity of $M_{n}$ is at most $2^{-n^{1/4}\sqrt{\log n}/1000}$ for all sufficiently large $n$ . The proof utilizes and extends a novel combinatorial approach to discrete random matrix theory, which has been recently introduced by the authors together with Luh and Samotij.
View PDF Chat

Singularity of random Bernoulli matrices

2020-02-13
Konstantin Tikhomirov
For each $n$, let $M_n$ be an $n\times n$ random matrix with independent $\pm 1$ entries. We show that $\mathbb{P}\{M_n \mathrm{is\ singular}\} = (1/2 + o_n(1))^n$, which settles an old … For each $n$, let $M_n$ be an $n\times n$ random matrix with independent $\pm 1$ entries. We show that $\mathbb{P}\{M_n \mathrm{is\ singular}\} = (1/2 + o_n(1))^n$, which settles an old problem. Some generalizations are considered.
View PDF Chat

On the singularity probability of random Bernoulli matrices

2007-02-06
Terence Tao , Van Vu
Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a large integer and let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M Subscript n"> <mml:semantics> <mml:msub> <mml:mi>M</mml:mi> … Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a large integer and let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M Subscript n"> <mml:semantics> <mml:msub> <mml:mi>M</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">M_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×<!-- × --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \times n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> matrix whose entries are i.i.d. Bernoulli random variables (each entry is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="plus-or-minus 1"> <mml:semantics> <mml:mrow> <mml:mo>±<!-- ± --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\pm 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with probability <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 slash 2"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">1/2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>). We show that the probability that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M Subscript n"> <mml:semantics> <mml:msub> <mml:mi>M</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">M_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is singular is at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis 3 slash 4 plus o left-parenthesis 1 right-parenthesis right-parenthesis Superscript n"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>3</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>4</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">(3/4 +o(1))^n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, improving an earlier estimate of Kahn, Komlós and Szemerédi, as well as earlier work by the authors. The key new ingredient is the applications of Freiman-type inverse theorems and other tools from additive combinatorics.
View PDF Chat

On the probability that a random ±1-matrix is singular

1995-01-01
Jeff Kahn , János Komlós , Endre Szemerédi
We report some progress on the old problem of estimating the probability, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n}</mml:annotation> … We report some progress on the old problem of estimating the probability, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, that a random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n plus-or-minus 1"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×<!-- × --></mml:mo> <mml:mi>n</mml:mi> <mml:mo>±<!-- ± --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n \times n \pm 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-matrix is singular: <bold>Theorem</bold>. <italic>There is a positive constant</italic> <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon"> <mml:semantics> <mml:mi>ε<!-- ε --></mml:mi> <mml:annotation encoding="application/x-tex">\varepsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> <italic>for which</italic> <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n Baseline greater-than left-parenthesis 1 minus epsilon right-parenthesis Superscript n"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mi>ε<!-- ε --></mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n} &gt; {(1 - \varepsilon )^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. This is a considerable improvement on the best previous bound, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n Baseline equals upper O left-parenthesis 1 slash StartRoot n EndRoot right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n} = O(1/\sqrt n )</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, given by Komlós in 1977, but still falls short of the often-conjectured asymptotical formula <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n Baseline equals left-parenthesis 1 plus o left-parenthesis 1 right-parenthesis right-parenthesis n squared 2 Superscript 1 minus n"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n} = (1 + o(1)){n^2}{2^{1 - n}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The proof combines ideas from combinatorial number theory, Fourier analysis and combinatorics, and some probabilistic constructions. A key ingredient, based on a Fourier-analytic idea of Halász, is an inequality (Theorem 2) relating the probability that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a underbar element-of bold upper R Superscript n"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mi>a</mml:mi> <mml:mo>_<!-- _ --></mml:mo> </mml:munder> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">R</mml:mi> </mml:mrow> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\underline a \in {{\mathbf {R}}^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is orthogonal to a random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon underbar element-of left-brace plus-or-minus 1 right-brace Superscript n"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mi>ε<!-- ε --></mml:mi> <mml:mo>_<!-- _ --></mml:mo> </mml:munder> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mo>±<!-- ± --></mml:mo> <mml:mn>1</mml:mn> <mml:msup> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\underline \varepsilon \in {\{ \pm 1\} ^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to the corresponding probability when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon underbar"> <mml:semantics> <mml:munder> <mml:mi>ε<!-- ε --></mml:mi> <mml:mo>_<!-- _ --></mml:mo> </mml:munder> <mml:annotation encoding="application/x-tex">\underline \varepsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is random from <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-brace negative 1 comma 0 comma 1 right-brace Superscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:msup> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{\{ - 1,0,1\} ^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P r left-parenthesis epsilon Subscript i Baseline equals negative 1 right-parenthesis equals upper P r left-parenthesis epsilon Subscript i Baseline equals 1 right-parenthesis equals p"> <mml:semantics> <mml:mrow> <mml:mi>P</mml:mi> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ε<!-- ε --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>P</mml:mi> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ε<!-- ε --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">Pr({\varepsilon _i} = - 1) = Pr({\varepsilon _i} = 1) = p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon Subscript i"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ε<!-- ε --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\varepsilon _i}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>’s chosen independently.
View PDF Chat

Optimal inverse Littlewood–Offord theorems

2011-01-22
Hoi H. Nguyen , Van Vu
View PDF Chat

Solution of the Littlewood-Offord Problem in High Dimensions

1988-09-01
Péter Frankl , Zoltán Füredi
Consider the 2' partial sums of arbitrary n vectors of length at least one in d-dimensional Euclidean space. It is shown that as n goes to infinity no closed ball … Consider the 2' partial sums of arbitrary n vectors of length at least one in d-dimensional Euclidean space. It is shown that as n goes to infinity no closed ball of diameter A contains more than ([A] + 1 + o(l))(ln2I) out of these sums and this is best possible. For A - [A] small an exact formula is given.

Large triangle-free subgraphs in graphs withoutK 4

1986-12-01
Péter Frankl , Vojtěch Rödl

On the singularity probability of discrete random matrices

2009-05-14
Jean Bourgain , Van H. Vu , Philip Matchett Wood
View PDF Chat

Smallest singular value of a random rectangular matrix

2009-06-29
Mark Rudelson , Roman Vershynin
Abstract We prove an optimal estimate of the smallest singular value of a random sub‐Gaussian matrix, valid for all dimensions. For an N × n matrix A with independent and … Abstract We prove an optimal estimate of the smallest singular value of a random sub‐Gaussian matrix, valid for all dimensions. For an N × n matrix A with independent and identically distributed sub‐Gaussian entries, the smallest singular value of A is at least of the order √ N − √ n − 1 with high probability. A sharp estimate on the probability is also obtained. © 2009 Wiley Periodicals, Inc.
View PDF Chat

On the Number of Real Roots of a Random Algebraic Equation

1938-10-01
J. E. Littlewood , A. C. Offord

Threshold Functions for Ramsey Properties

1995-10-01
Vojtěch Rödl , Andrzej Ruciński

Random symmetric matrices are almost surely nonsingular

2006-10-18
Kevin Costello , Terence Tao , Van Vu
Let Qn denote a random symmetric (n×n)-matrix, whose upper-diagonal entries are independent and identically distributed (i.i.d.) Bernoulli random variables (which take values 0 and 1 with probability 1/2). We prove … Let Qn denote a random symmetric (n×n)-matrix, whose upper-diagonal entries are independent and identically distributed (i.i.d.) Bernoulli random variables (which take values 0 and 1 with probability 1/2). We prove that Qn is nonsingular with probability 1-O(n-1/8+δ) for any fixed δ>0. The proof uses a quadratic version of Littlewood-Offord-type results concerning the concentration functions of random variables and can be extended for more general models of random matrices
View PDF Chat

An exact result for 3-graphs

1984-01-01
Péter Frankl , Zoltán Füredi

On a Theorem of Hardy and Ramanujan

1934-10-01
P. Túrán

Excluding induced subgraphs II: extremal graphs

1993-07-01
Hans Jürgen Prömel , Angelika Steger

Maximum induced matchings in graphs

1997-06-01
Jiping Liu , Huishan Zhou

Hereditary properties of hypergraphs

2008-10-29
R. Dotson , Brendan Nagle
View PDF Chat

A 2-Coloring of $[1,N]$ can have $(1/22)N^2+O(N)$ Monochromatic Schur Triples, but not less!

1998-03-25
Aaron Robertson , Doron Zeilberger
We prove the statement of the title, thereby solving a $100 problem of Ron Graham. This was solved independently by Tomasz Schoen. We prove the statement of the title, thereby solving a $100 problem of Ron Graham. This was solved independently by Tomasz Schoen.
View PDF Chat

Rainbow subgraphs in properly edge‐colored graphs

1992-01-01
Vojtěch Rödl , Źsolt Tuza
Abstract We prove that there exist graphs G with arbitrarily large girth such that every proper edge coloring of G contains a rainbow cycle (i.e., a cycle having no pair … Abstract We prove that there exist graphs G with arbitrarily large girth such that every proper edge coloring of G contains a rainbow cycle (i.e., a cycle having no pair of monochromatic edges). This answers a problem raised by J. Spencer more than 10 years ago.

The Number of Monochromatic Schur Triples

1999-11-01
Tomasz Schoen

Sum-free sets of integers

1977-01-01
H. L. Abbott , E. T. H. Wang
A set<italic>S</italic>of integers is said to be sum-free if<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a comma b element-of upper S"><mml:semantics><mml:mrow><mml:mi>a</mml:mi><mml:mo>,</mml:mo><mml:mi>b</mml:mi><mml:mo>∈<!-- ∈ --></mml:mo><mml:mi>S</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">a,b \in S</mml:annotation></mml:semantics></mml:math></inline-formula>implies<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a plus b not-an-element-of upper S"><mml:semantics><mml:mrow><mml:mi>a</mml:mi><mml:mo>+</mml:mo><mml:mi>b</mml:mi><mml:mo>∉<!-- … A set<italic>S</italic>of integers is said to be sum-free if<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a comma b element-of upper S"><mml:semantics><mml:mrow><mml:mi>a</mml:mi><mml:mo>,</mml:mo><mml:mi>b</mml:mi><mml:mo>∈<!-- ∈ --></mml:mo><mml:mi>S</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">a,b \in S</mml:annotation></mml:semantics></mml:math></inline-formula>implies<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a plus b not-an-element-of upper S"><mml:semantics><mml:mrow><mml:mi>a</mml:mi><mml:mo>+</mml:mo><mml:mi>b</mml:mi><mml:mo>∉<!-- ∉ --></mml:mo><mml:mi>S</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">a + b \notin S</mml:annotation></mml:semantics></mml:math></inline-formula>. In this paper, we investigate two new problems on sum-free sets: (1) Let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">f(k)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the largest positive integer for which there exists a partition of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 1 comma 2 comma ellipsis comma f left-parenthesis k right-parenthesis EndSet"><mml:semantics><mml:mrow><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo>…<!-- … --></mml:mo><mml:mo>,</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo fence="false" stretchy="false">}</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\{ 1,2, \ldots ,f(k)\}</mml:annotation></mml:semantics></mml:math></inline-formula>into<italic>k</italic>sum-free sets, and let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h left-parenthesis k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>h</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">h(k)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the largest positive integer for which there exists a partition of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 1 comma 2 comma ellipsis comma h left-parenthesis k right-parenthesis EndSet"><mml:semantics><mml:mrow><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo>…<!-- … --></mml:mo><mml:mo>,</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo fence="false" stretchy="false">}</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\{ 1,2, \ldots ,h(k)\}</mml:annotation></mml:semantics></mml:math></inline-formula>into<italic>k</italic>sets which are sum-free<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mod h left-parenthesis k right-parenthesis plus 1"><mml:semantics><mml:mrow><mml:mo lspace="thickmathspace" rspace="thickmathspace">mod</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">\bmod h(k) + 1</mml:annotation></mml:semantics></mml:math></inline-formula>. We obtain evidence to support the conjecture that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis k right-parenthesis equals h left-parenthesis k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">f(k) = h(k)</mml:annotation></mml:semantics></mml:math></inline-formula>for all<italic>k</italic>. (2) Let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="g left-parenthesis n comma k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">g(n,k)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the cardinality of a largest subset of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 1 comma 2 comma ellipsis comma n EndSet"><mml:semantics><mml:mrow><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo>…<!-- … --></mml:mo><mml:mo>,</mml:mo><mml:mi>n</mml:mi><mml:mo fence="false" stretchy="false">}</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\{ 1,2, \ldots ,n\}</mml:annotation></mml:semantics></mml:math></inline-formula>that can be partitioned into<italic>k</italic>sum-free sets. We obtain upper and lower bounds for<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="g left-parenthesis n comma k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">g(n,k)</mml:annotation></mml:semantics></mml:math></inline-formula>. We also show that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="g left-parenthesis n comma 1 right-parenthesis equals left-bracket left-parenthesis n plus 1 right-parenthesis slash 2 right-bracket"><mml:semantics><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">g(n,1) = [(n + 1)/2]</mml:annotation></mml:semantics></mml:math></inline-formula>and indicate how one may show that for all<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n less-than-or-slanted-equals 54 comma g left-parenthesis n comma 2 right-parenthesis equals n minus left-bracket n slash 5 right-bracket"><mml:semantics><mml:mrow><mml:mi>n</mml:mi><mml:mo>⩽<!-- ⩽ --></mml:mo><mml:mn>54</mml:mn><mml:mo>,</mml:mo><mml:mi>g</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo>−<!-- − --></mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>5</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">n \leqslant 54,g(n,2) = n - [n/5]</mml:annotation></mml:semantics></mml:math></inline-formula>.
View PDF Chat

Small Ball Probability, Inverse Theorems, and Applications

2013-01-01
Hoi H. Nguyen , Van H. Vu
View PDF Chat

Rainbow 3-term arithmetic progressions.

2003-01-01
Veselin Jungić , Radoš Radoičić
Consider a coloring of {1, 2, . . . , n} in 3 colors, where n ≡ 0 (mod 3). If all the color classes have the same cardinality, then … Consider a coloring of {1, 2, . . . , n} in 3 colors, where n ≡ 0 (mod 3). If all the color classes have the same cardinality, then there is a 3-term arithmetic progression whose elements are colored in distinct colors. This rainbow variant of van der Waerden’s theorem proves the conjecture of the second author.

On subspaces spanned by random selections of ±1 vectors

1988-01-01
Andrew Odlyzko
View PDF Chat

On an anti-Ramsey threshold for random graphs

2014-03-04
Yoshiharu Kohayakawa , Pavlos B. Konstadinidis , Guilherme Oliveira Mota
For graphs G and H, let G⟶prbH denote the property that, for every proper edge-colouring of G (with an arbitrary number of colours) there is a totally multicoloured, or rainbow, … For graphs G and H, let G⟶prbH denote the property that, for every proper edge-colouring of G (with an arbitrary number of colours) there is a totally multicoloured, or rainbow, copy of H in G, that is, a copy of H with no two edges of the same colour. We consider the problem of establishing the threshold pHrb=pHrb(n) of this property for the binomial random graph G(n,p). More specifically, we give an upper bound for pHrb and we extend our result to certain locally bounded colourings that generalize proper colourings. Our method is heavily based on a characterization of sparse quasi-randomness given by Chung and Graham (2008).

How many random edges make a dense graph hamiltonian?

2002-11-19
Tom Bohman , Alan Frieze , Ryan R. Martin
Abstract This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding Θ(n) … Abstract This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding Θ(n) random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 33–42, 2003
View PDF Chat

Almost all triangle-free triple systems are tripartite

2012-03-01
József Balogh , Dhruv Mubayi
View PDF Chat

Threshold functions for Ramsey properties

1995-01-01
Vojtěch Rödl , Andrzej Ruciński
Probabilistic methods have been used to approach many problems of Ramsey theory. In this paper we study Ramsey type questions from the point of view of random structures. Let <inline-formula … Probabilistic methods have been used to approach many problems of Ramsey theory. In this paper we study Ramsey type questions from the point of view of random structures. Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K left-parenthesis n comma upper N right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">K(n,N)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be the random graph chosen uniformly from among all graphs with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> edges. For a fixed graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and an integer <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula> we address the question what is the minimum <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N equals upper N left-parenthesis upper G comma r comma n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>,</mml:mo> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">N = N(G,r,n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that the random graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K left-parenthesis n comma upper N right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">K(n,N)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> contains, almost surely, a monochromatic copy of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-coloring of its edges ( <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K left-parenthesis n comma upper N right-parenthesis right-arrow left-parenthesis upper G right-parenthesis Subscript r"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">→<!-- → --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mi>r</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">K(n,N) \to {(G)_r}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, in short). We find a graph parameter <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="gamma equals gamma left-parenthesis upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>γ<!-- γ --></mml:mi> <mml:mo>=</mml:mo> <mml:mi>γ<!-- γ --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\gamma = \gamma (G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> yielding <disp-formula content-type="math/mathml"> \[ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="limit Underscript n right-arrow normal infinity Endscripts upper P r o b left-parenthesis upper K left-parenthesis n comma upper N right-parenthesis right-arrow left-parenthesis upper G right-parenthesis Subscript r Baseline right-parenthesis equals StartLayout Enlarged left-brace 1st Row 0 if upper N greater-than c n Superscript y Baseline comma 2nd Row 1 if upper N greater-than upper C n Superscript y Baseline comma EndLayout"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mo form="prefix">lim</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo stretchy="false">→<!-- → --></mml:mo> <mml:mi mathvariant="normal">∞<!-- ∞ --></mml:mi> </mml:mrow> </mml:munder> <mml:mi>Prob</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>K</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">→<!-- → --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mi>r</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtable rowspacing="4pt" columnspacing="1em"> <mml:mtr> <mml:mtd> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>0</mml:mn> <mml:mspace width="1em" /> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>if </mml:mtext> </mml:mrow> <mml:mspace width="thickmathspace" /> <mml:mi>N</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi>c</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mi>y</mml:mi> </mml:msup> </mml:mrow> <mml:mo>,</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mspace width="1em" /> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>if</mml:mtext> </mml:mrow> <mml:mspace width="thickmathspace" /> <mml:mi>N</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi>C</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mi>y</mml:mi> </mml:msup> </mml:mrow> <mml:mo>,</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> <mml:mo fence="true" stretchy="true" symmetric="true" /> </mml:mrow> <mml:mspace width="1em" /> </mml:mrow> <mml:annotation encoding="application/x-tex">\lim \limits _{n \to \infty } \operatorname {Prob}(K(n,N) \to {(G)_r}) = \left \{ {\begin {array}{*{20}{c}} {0\quad {\text {if }}\;N &gt; c{n^y},} \\ {1\quad {\text {if}}\;N &gt; C{n^y},} \\ \end {array} } \right .\quad</mml:annotation> </mml:semantics> </mml:math> \] </disp-formula> for some <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c"> <mml:semantics> <mml:mi>c</mml:mi> <mml:annotation encoding="application/x-tex">c</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C greater-than 0"> <mml:semantics> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">C &gt; 0</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We use this to derive a number of consequences that deal with the existence of sparse Ramsey graphs. For example we show that for all <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r greater-than-or-equal-to 2"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>≥<!-- ≥ --></mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">r \geq 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k greater-than-or-equal-to 3"> <mml:semantics> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥<!-- ≥ --></mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">k \geq 3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> there exists <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C greater-than 0"> <mml:semantics> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">C &gt; 0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that almost all graphs <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H"> <mml:semantics> <mml:mi>H</mml:mi> <mml:annotation encoding="application/x-tex">H</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C n Superscript StartFraction 2 k Over k plus 1 EndFraction"> <mml:semantics> <mml:mrow> <mml:mi>C</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mfrac> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">C{n^{\frac {{2k}}{{k + 1}}}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> edges which are <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K Subscript k plus 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{K_{k + 1}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-free, satisfy <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H right-arrow left-parenthesis upper K Subscript k Baseline right-parenthesis Subscript r"> <mml:semantics> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo stretchy="false">→<!-- → --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:mrow> <mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mi>r</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">H \to {({K_k})_r}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We also apply our method to the problem of finding the smallest <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N equals upper N left-parenthesis k comma r comma n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">N = N(k,r,n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> guaranteeing that almost all sequences <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 less-than-or-equal-to a 1 greater-than a 2 greater-than midline-horizontal-ellipsis greater-than a Subscript upper N Baseline less-than-or-equal-to n"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mo>⋯<!-- ⋯ --></mml:mo> <mml:mo>&gt;</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>N</mml:mi> </mml:msub> </mml:mrow> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">1 \leq {a_1} &gt; {a_2} &gt; \cdots &gt; {a_N} \leq n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> contain an arithmetic progression of length <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-coloring, and show that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N equals normal upper Theta left-parenthesis n Superscript StartFraction k minus 2 Over k minus 1 EndFraction Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mi mathvariant="normal">Θ<!-- Θ --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mfrac> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">N = \Theta ({n^{\frac {{k - 2}}{{k - 1}}}})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the threshold.
View PDF Chat

The first classical Ramsey number for hypergraphs is computed

1991-03-01
Brendan D. McKay , Stanisław Radziszowski

The Ramsey property for graphs with forbidden complete subgraphs

1976-06-01
Jaroslav Nešetřil , Vojtěch Rödl

Extremal Hypergraph Problems and the Regularity Method

2007-05-28
Brendan Nagle , Vojtěch Rödl , Mathias Schacht

Hereditary and Monotone Properties of Graphs

2013-01-01
Béla Bollobás , Andrew Thomason

Essential covers of the cube by hyperplanes

2004-11-16
Nathan Linial , Jaikumar Radhakrishnan

The plank problem for symmetric bodies

1991-12-01
Keith Ball
View PDF Chat