JSJulian Sahasrabudhe
Julian Sahasrabudhe
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Julian Sahasrabudhe has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Bhargav Narayanan
University of Cambridge
3 shared publications - István Tomon
University of Cambridge
3 shared publications - Shoham Letzter
Department of Mathematics University College London Gower Street WC1E 6BT London U.K
3 shared publications - Béla Bollobás
University of Cambridge, Cambridge, UK
2 shared publications - Oliver Riordan
University of Oxford
2 shared publications - António Girão
School of Mathematics University of Birmingham Edgbaston B15 2TT Birmingham United Kingdom
1 shared publication
Latest Publications
- 1 March 2020
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 236 (2) , 591-601
On Existentially Complete Triangle-Free Graphs
- 1 March 2020
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 236 (2) , 591-601
On Existentially Complete Triangle-Free Graphs
- Open Access
Counting Zeros of Cosine Polynomials: On a Problem of Littlewood
We show that if $A$ is a finite set of non-negative integers then the number of zeros of the function \[ f_A(\theta) = \sum_{a \in A} \cos(a\theta), \] in $[0,2\pi]$, is at least $(\log \log \log |A|)^{1/2-\varepsilon}$. This gives the first unconditional lower bound on a problem of Littlewood, solves a conjecture of Borwein, Erd\'elyi, Ferguson and Lockhart and improves upon work of Borwein and Erd\'elyi. We also prove a result that applies to more general cosine polynomials with "few" distinct rational coefficients. One of the main ingredients in the proof is perhaps of independent interest: we show that if $f$ is an exponential polynomial with "few" distinct integer coefficients and $f$ "correlates" with a low-degree exponential polynomial $P$, then $f$ has a very particular structure.Open AccessCounting Zeros of Cosine Polynomials: On a Problem of Littlewood
We show that if $A$ is a finite set of non-negative integers then the number of zeros of the function \[ f_A(\theta) = \sum_{a \in A} \cos(a\theta), \] in $[0,2\pi]$, is at least $(\log \log \log |A|)^{1/2-\varepsilon}$. This gives the first unconditional lower bound on a problem of Littlewood, solves a conjecture of Borwein, Erd\'elyi, Ferguson and Lockhart and improves upon work of Borwein and Erd\'elyi. We also prove a result that applies to more general cosine polynomials with "few" distinct rational coefficients. One of the main ingredients in the proof is perhaps of independent interest: we show that if $f$ is an exponential polynomial with "few" distinct integer coefficients and $f$ "correlates" with a low-degree exponential polynomial $P$, then $f$ has a very particular structure. - 1 August 2018
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 158, 548-559
Monochromatic solutions to systems of exponential equations
- 1 August 2018
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 158, 548-559
Monochromatic solutions to systems of exponential equations
- Open Access
A Stability Theorem for Maximal $K_{r+1}$-free Graphs
For $r \geq 2$, we show that every maximal $K_{r+1}$-free graph $G$ on $n$ vertices with $(1-\frac{1}{r})\frac{n^2}{2}-o(n^{\frac{r+1}{r}})$ edges contains a complete $r$-partite subgraph on $(1 - o(1))n$ vertices. We also show that this is best possible. This result answers a question of Tyomkyn and Uzzell.Open AccessA Stability Theorem for Maximal $K_{r+1}$-free Graphs
For $r \geq 2$, we show that every maximal $K_{r+1}$-free graph $G$ on $n$ vertices with $(1-\frac{1}{r})\frac{n^2}{2}-o(n^{\frac{r+1}{r}})$ edges contains a complete $r$-partite subgraph on $(1 - o(1))n$ vertices. We also show that this is best possible. This result answers a question of Tyomkyn and Uzzell. - 7 February 2018
- Published by Springer Nature in Combinatorica
- Vol. 39 (1) , 215-237
Ramsey Graphs Induce Subgraphs of Many Different Sizes
- 7 February 2018
- Published by Springer Nature in Combinatorica
- Vol. 39 (1) , 215-237
Ramsey Graphs Induce Subgraphs of Many Different Sizes
- 1 January 2018
- Published by Institute of Mathematics, Polish Academy of Sciences in Acta Arithmetica
- Vol. 182 (1) , 13-42
Exponential patterns in arithmetic Ramsey theory
We show that for every finite colouring of the natural numbers there exist $a,b \gt 1$ such that the triple $\{a,b,a^b\}$ is monochromatic. We go on to show the partition regularity of a much richer class of patterns involving exponentiation. For example,- 1 January 2018
- Published by Institute of Mathematics, Polish Academy of Sciences in Acta Arithmetica
- Vol. 182 (1) , 13-42
Exponential patterns in arithmetic Ramsey theory
We show that for every finite colouring of the natural numbers there exist $a,b \gt 1$ such that the triple $\{a,b,a^b\}$ is monochromatic. We go on to show the partition regularity of a much richer class of patterns involving exponentiation. For example,- Open Access
Ramsey graphs induce subgraphs of many different sizes
A graph on $n$ vertices is said to be \emph{$C$-Ramsey} if every clique or independent set of the graph has size at most $C \log n$. The only known constructions of Ramsey graphs are probabilistic in nature, and it is generally believed that such graphs possess many of the same properties as dense random graphs. Here, we demonstrate one such property: for any fixed $C>0$, every $C$-Ramsey graph on $n$ vertices induces subgraphs of at least $n^{2-o(1)}$ distinct sizes. This near-optimal result is closely related to two unresolved conjectures, the first due to Erd\H{o}s and McKay and the second due to Erd\H{o}s, Faudree and S\'{o}s, both from 1992.Open AccessRamsey graphs induce subgraphs of many different sizes
A graph on $n$ vertices is said to be \emph{$C$-Ramsey} if every clique or independent set of the graph has size at most $C \log n$. The only known constructions of Ramsey graphs are probabilistic in nature, and it is generally believed that such graphs possess many of the same properties as dense random graphs. Here, we demonstrate one such property: for any fixed $C>0$, every $C$-Ramsey graph on $n$ vertices induces subgraphs of at least $n^{2-o(1)}$ distinct sizes. This near-optimal result is closely related to two unresolved conjectures, the first due to Erd\H{o}s and McKay and the second due to Erd\H{o}s, Faudree and S\'{o}s, both from 1992. - Open Access
On Existentially Complete Triangle-free Graphs
For a positive integer $k$, we say that a graph is $k$-existentially complete if for every $0 \leq a \leq k$, and every tuple of distinct vertices $x_1,\ldots,x_a$, $y_1,\ldots,y_{k-a}$, there exists a vertex $z$ that is joined to all of the vertices $x_1,\ldots,x_a$ and none of the vertices $y_1,\ldots,y_{k-a}$. While it is easy to show that the binomial random graph $G_{n,1/2}$ satisfies this property with high probability for $k \sim c\log n$, little is known about the "triangle-free" version of this problem; does there exist a finite triangle-free graph $G$ with a similar "extension property". This question was first raised by Cherlin in 1993 and remains open even in the case $k=4$. We show that there are no $k$-existentially complete triangle-free graphs with $k >\frac{8\log n}{\log\log n}$, thus giving the first non-trivial, non-existence result on this "old chestnut" of Cherlin. We believe that this result breaks through a natural barrier in our understanding of the problem.Open AccessOn Existentially Complete Triangle-free Graphs
For a positive integer $k$, we say that a graph is $k$-existentially complete if for every $0 \leq a \leq k$, and every tuple of distinct vertices $x_1,\ldots,x_a$, $y_1,\ldots,y_{k-a}$, there exists a vertex $z$ that is joined to all of the vertices $x_1,\ldots,x_a$ and none of the vertices $y_1,\ldots,y_{k-a}$. While it is easy to show that the binomial random graph $G_{n,1/2}$ satisfies this property with high probability for $k \sim c\log n$, little is known about the "triangle-free" version of this problem; does there exist a finite triangle-free graph $G$ with a similar "extension property". This question was first raised by Cherlin in 1993 and remains open even in the case $k=4$. We show that there are no $k$-existentially complete triangle-free graphs with $k >\frac{8\log n}{\log\log n}$, thus giving the first non-trivial, non-existence result on this "old chestnut" of Cherlin. We believe that this result breaks through a natural barrier in our understanding of the problem. - Open Access
Partitioning a graph into monochromatic connected subgraphs
A well-known result by Haxell and Kohayakawa states that the vertices of an $r$-coloured complete graph can be partitioned into $r$ monochromatic connected subgraphs of distinct colours; this is a slightly weaker variant of a conjecture by Erd\H{o}s, Pyber and Gy\'arf\'as that states that there exists a partition into $r-1$ monochromatic connected subgraphs. We consider a variant of this problem, where the complete graph is replaced by a graph with large minimum degree, and prove two conjectures of Bal and DeBiasio, for two and three colours.Open AccessPartitioning a graph into monochromatic connected subgraphs
A well-known result by Haxell and Kohayakawa states that the vertices of an $r$-coloured complete graph can be partitioned into $r$ monochromatic connected subgraphs of distinct colours; this is a slightly weaker variant of a conjecture by Erd\H{o}s, Pyber and Gy\'arf\'as that states that there exists a partition into $r-1$ monochromatic connected subgraphs. We consider a variant of this problem, where the complete graph is replaced by a graph with large minimum degree, and prove two conjectures of Bal and DeBiasio, for two and three colours. - Open Access
- 13 April 2017
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 24 (2) , P2.16
On the Maximum Running Time in Graph Bootstrap Percolation
Graph bootstrap percolation is a simple cellular automaton introduced by Bollobás in 1968. Given a graph $H$ and a set $G \subseteq E(K_n)$ we initially `infect' all edges in $G$ and then, in consecutive steps, we infect every $e \in K_n$ that completes a new infected copy of $H$ in $K_n$. We say that $G$ percolates if eventually every edge in $K_n$ is infected. The extremal question about the size of the smallest percolating sets when $H = K_r$ was answered independently by Alon, Kalai and Frankl. Here we consider a different question raised more recently by Bollobás: what is the maximum time the process can run before it stabilizes? It is an easy observation that for $r=3$ this maximum is $\lceil \log_2 (n-1) \rceil $. However, a new phenomenon occurs for $r=4$ when, as we show, the maximum time of the process is $n-3$. For $r \geq 5$ the behaviour of the dynamics is even more complex, which we demonstrate by showing that the $K_r$-bootstrap process can run for at least $n^{2-\varepsilon_r}$ time steps for some $\varepsilon_r$ that tends to $0$ as $r \to \infty$.- 13 April 2017
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 24 (2) , P2.16
Open AccessOn the Maximum Running Time in Graph Bootstrap Percolation
Graph bootstrap percolation is a simple cellular automaton introduced by Bollobás in 1968. Given a graph $H$ and a set $G \subseteq E(K_n)$ we initially `infect' all edges in $G$ and then, in consecutive steps, we infect every $e \in K_n$ that completes a new infected copy of $H$ in $K_n$. We say that $G$ percolates if eventually every edge in $K_n$ is infected. The extremal question about the size of the smallest percolating sets when $H = K_r$ was answered independently by Alon, Kalai and Frankl. Here we consider a different question raised more recently by Bollobás: what is the maximum time the process can run before it stabilizes? It is an easy observation that for $r=3$ this maximum is $\lceil \log_2 (n-1) \rceil $. However, a new phenomenon occurs for $r=4$ when, as we show, the maximum time of the process is $n-3$. For $r \geq 5$ the behaviour of the dynamics is even more complex, which we demonstrate by showing that the $K_r$-bootstrap process can run for at least $n^{2-\varepsilon_r}$ time steps for some $\varepsilon_r$ that tends to $0$ as $r \to \infty$.