Wouter Cames van Batenburg
I am a postdoctoral researcher in the algorithm research group of the Université Libre de Bruxelles.
My main research interests are in combinatorics. In particular: colouring problems and extremal combinatorics on graphs.
E-mail
Preprints
Publications
In preparation
- W. Cames van Batenburg, R.J. Kang and F. Pirot. Strong cliques and forbidden cycles. (Part of this is already publicly available in chapter 4 of my PhD thesis)
Theses
Other
Teaching
As a student at Leiden University (until 2013) and then as a PhD student at Radboud University (until 2017), I have taught exercise classes for the following courses:
- Autumn 2017 and Autumn 2016, Advanced Probability.
- Spring 2017, Game theory.
- Spring 2016 and Spring 2015, Inleiding Kansrekening (Introduction to probability theory).
- Autumn 2015, Autumn 2014 and Spring 2014, Applied Stochastics (Random graphs and Ramsey theory).
- Autumn 2012 and Autumn 2010, Analyse 1 (Calculus).
- Spring 2011, Analyse 4 (Complex analysis).
- Spring 2010, Analyse 2 (Advanced calculus).
- Autumn 2010, Calculus A (Basic calculus for the Biopharmaceutical Sciences).
Co-authors
Louis Esperet,
Rémi de Joannis de Verclos,
Gwenaël Joret,
Tony Huynh,
Ross J. Kang,
François Pirot ,
Jean-Florent Raymond,
Tobias Müller.
Some open problems that interest(ed) me.
- Esperet-Kang-Thomassé-conjecture (2018). Let G be a triangle-free graph on n vertices with minimum degree d. Does G have an induced bipartite subgraph of order Omega(log d)? The conjecture holds for regular graphs by the Johansson-Molloy theorem. Moreover, it is known that G has an induced bipartite subgraph of minimum degree d^2/(2n), which is even polynomial in d if d>n^(1/2+epsilon). Thus it suffices to prove the conjecture for graphs with d << (n*log(n))^(1/2).
- Strong immersion conjecture (1989, 2003). Is the chromatic number of a graph G bounded from above by its (strong) immersion number i(G)? Two known upper bounds are 3.54 i(G)+4 and (i(G)+delta(G))/2, rounded upwards. Here delta(G) denotes the degeneracy of G.
- Erdos-Nesetril-conjecture (~1988). Let G be a graph with maximum degree Delta. Is it true that the (fractional) chromatic number of the square of the line graph of G is at most 5/4*Delta^2? Is it at most Delta^2 if G is bipartite?
- BEC-conjecture (1976). Let G1 and G2 be two graphs on n vertices with maximum degrees Delta1 and Delta2, respectively. Show that G1 and G2 pack if (Delta1+1)(Delta2+1) <= n+1.
- Variance in Last Passage Percolation. Put iid random weights on each vertex of Z^2. Consider oriented (North-East) paths of length n that start in (0,0). The weight of a path is the sum of the weights of the vertices that are visited by the path. The heaviest path is the path with the largest weight, among all paths of length n. Does it hold that the variance of the weight of the heaviest path is asymptotically equal to a constant multiple of n^{2/3}, as n goes to infinity? This (and more) is known to be true if the distribution of the vertex weights is either an exponential or a geometric distribution, but it is expected to hold for a much wider class of distributions. In general, roughly, the variance is only known to be between log(n) and n/log(n). See this survey for more details.
- Hard squares constant. Let N and n be positive integers. Consider the set A(n,N) of all 0,1-words of length n for which there are no pairs of 1's that are adjacent or at distance exactly N. Find a nice exact expression for \lim_{N \rightarrow \infty} \lim_{n \rightarrow \infty} |A(n,N)|^{1/n}. This limit exists and it is equal to the so-called Hard squares constant, of which many digits are semi-rigorously known. Equivalently, this problem asks to asymptotically count the number of stable sets in a large gridgraph.
Last update: August 23, 2018
