Jacques Verstraëte
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Jacques Verstraëte has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Thomas Lam
Department of Mathematics, University of Michigan, Ann Arbor, USA
2 shared publications - Benny Sudakov
ETH Zurich, Switzerland
1 shared publication - Bollobás1 shared publication
Béla
1 shared publication- Dhruv Mubayi
University of Illinois
1 shared publication - Jeong Han Kim
Microsoft Research, One Microsoft Way, Redmond, Washington 98052
1 shared publication
Latest Publications
- 4 September 2006
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 16 (1) , 109-126
Rainbow Turán Problems
For a fixed graph $H$, we define the rainbow Turán number $\ex^*(n,H)$ to be the maximum number of edges in a graph on $n$ vertices that has a proper edge-colouring with no rainbow $H$. Recall that the (ordinary) Turán number $\ex(n,H)$ is the maximum number of edges in a graph on $n$ vertices that does not contain a copy of $H$. For any non-bipartite $H$ we show that $\ex^*(n,H)=(1+o(1))\ex(n,H)$, and if $H$ is colour-critical we show that $\ex^{*}(n,H)=\ex(n,H)$. When $H$ is the complete bipartite graph $K_{s,t}$ with $s \leq t$ we show $\ex^*(n,K_{s,t}) = O(n^{2-1/s})$, which matches the known bounds for $\ex(n,K_{s,t})$ up to a constant. We also study the rainbow Turán problem for even cycles, and in particular prove the bound $\ex^*(n,C_6) = O(n^{4/3})$, which is of the correct order of magnitude.- 4 September 2006
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 16 (1) , 109-126
Rainbow Turán Problems
For a fixed graph $H$, we define the rainbow Turán number $\ex^*(n,H)$ to be the maximum number of edges in a graph on $n$ vertices that has a proper edge-colouring with no rainbow $H$. Recall that the (ordinary) Turán number $\ex(n,H)$ is the maximum number of edges in a graph on $n$ vertices that does not contain a copy of $H$. For any non-bipartite $H$ we show that $\ex^*(n,H)=(1+o(1))\ex(n,H)$, and if $H$ is colour-critical we show that $\ex^{*}(n,H)=\ex(n,H)$. When $H$ is the complete bipartite graph $K_{s,t}$ with $s \leq t$ we show $\ex^*(n,K_{s,t}) = O(n^{2-1/s})$, which matches the known bounds for $\ex(n,K_{s,t})$ up to a constant. We also study the rainbow Turán problem for even cycles, and in particular prove the bound $\ex^*(n,C_6) = O(n^{4/3})$, which is of the correct order of magnitude.- 8 May 2006
- Published by Wiley in Random Structures & Algorithms
- Vol. 29 (1) , 1-13
Regular subgraphs of random graphs
In this paper, we prove that there exists a function ρk = (4 + o(1))k such that G(n,ρ/n) contains a k−regular graph with high probability whenever ρ > ρk. In the case of k = 3, it is also shown that G(n,ρ/n) contains a 3−regular graph with high probability whenever ρ > λ ≈︁ 5.1494. These are the first constant bounds on the average degree in G(n,p) for the existence of a k−regular subgraph. We also discuss the appearance of 3−regular subgraphs in cores of random graphs. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006
- 8 May 2006
- Published by Wiley in Random Structures & Algorithms
- Vol. 29 (1) , 1-13
Regular subgraphs of random graphs
In this paper, we prove that there exists a function ρk = (4 + o(1))k such that G(n,ρ/n) contains a k−regular graph with high probability whenever ρ > ρk. In the case of k = 3, it is also shown that G(n,ρ/n) contains a 3−regular graph with high probability whenever ρ > λ ≈︁ 5.1494. These are the first constant bounds on the average degree in G(n,p) for the existence of a k−regular subgraph. We also discuss the appearance of 3−regular subgraphs in cores of random graphs. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006
- Open Access
A note on graphs without short even cycles
We show that any n-vertex graph without even cycles of length at most 2k has at most 1/2(n^{1 + 1/k}) + O(n) edges, and polarity graphs of generalized polygons show that this is asymptotically tight when k = 2,3,5.
Open AccessA note on graphs without short even cycles
We show that any n-vertex graph without even cycles of length at most 2k has at most 1/2(n^{1 + 1/k}) + O(n) edges, and polarity graphs of generalized polygons show that this is asymptotically tight when k = 2,3,5.
- 21 March 2005
- Published by Wiley in Journal of Graph Theory
- Vol. 49 (2) , 151-167
Unavoidable cycle lengths in graphs
- 21 March 2005
- Published by Wiley in Journal of Graph Theory
- Vol. 49 (2) , 151-167
Unavoidable cycle lengths in graphs
- Open Access
- 7 January 2005
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 12 (1) , N5
A Note on Graphs Without Short Even Cycles
In this note, we show that any $n$-vertex graph without even cycles of length at most $2k$ has at most ${1\over2}n^{1 + 1/k} + O(n)$ edges, and polarity graphs of generalized polygons show that this is asymptotically tight when $k \in \{2,3,5\}$.- 7 January 2005
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 12 (1) , N5
Open AccessA Note on Graphs Without Short Even Cycles
In this note, we show that any $n$-vertex graph without even cycles of length at most $2k$ has at most ${1\over2}n^{1 + 1/k} + O(n)$ edges, and polarity graphs of generalized polygons show that this is asymptotically tight when $k \in \{2,3,5\}$.