Source author record

Wouter Cames van Batenburg

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.PR

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Bipartite induced density in triangle-free graphs

We prove that any triangle-free graph on $n$ vertices with minimum degree at least $d$ contains a bipartite induced subgraph of minimum degree at least $d^2/(2n)$ . This is sharp up to a logarithmic factor in $n$ . Relatedly, we show that the fractional chromatic number of any such triangle-free graph is at most the minimum of $n/d$ and $(2+o(1))\sqrt{n/\log n}$ as $n\to\infty$ . This is sharp up to constant factors. Similarly, we show that the list chromatic number of any such triangle-free graph is at most $O(\min\{\sqrt{n},(n\log n)/d\})$ as $n\to\infty$ . Relatedly, we also make two conjectures. First, any triangle-free graph on $n$ vertices has fractional chromatic number at most $(\sqrt{2}+o(1))\sqrt{n/\log n}$ as $n\to\infty$ . Second, any triangle-free graph on $n$ vertices has list chromatic number at most $O(\sqrt{n/\log n})$ as $n\to\infty$ .

preprint2020arXiv

Erdős-Pósa from ball packing

A classic theorem of Erdős and Pósa (1965) states that every graph has either $k$ vertex-disjoint cycles or a set of $O(k \log k)$ vertices meeting all its cycles. While the standard proof revolves around finding a large `frame' in the graph (a subdivision of a large cubic graph), an alternative way of proving this theorem is to use a ball packing argument of Kühn and Osthus (2003) and Diestel and Rempel (2005). In this paper, we argue that the latter approach is particularly well suited for studying edge variants of the Erdős-Pósa theorem. As an illustration, we give a short proof of a theorem of Bruhn, Heinlein, and Joos (2019), that cycles of length at least $\ell$ have the so-called edge-Erdős-Pósa property. More precisely, we show that every graph $G$ either contains $k$ edge-disjoint cycles of length at least $\ell$ or an edge set $F$ of size $O(k\ell \cdot \log (k\ell))$ such that $G-F$ has no cycle of length at least $\ell$ . For fixed $\ell$ , this improves on the previously best known bound of $O(k^2 \log k +k\ell)$ .

preprint2020arXiv

Large independent sets in triangle-free cubic graphs: beyond planarity

Every $n$ -vertex planar triangle-free graph with maximum degree at most $3$ has an independent set of size at least $\frac{3}{8}n$ . This was first conjectured by Albertson, Bollobás and Tucker, and was later proved by Heckman and Thomas. Fraughnaugh and Locke conjectured that the planarity requirement could be relaxed into just forbidding a few specific nonplanar subgraphs: They described a family $\mathcal{F}$ of six nonplanar graphs (each of order at most $22$ ) and conjectured that every $n$ -vertex triangle-free graph with maximum degree at most $3$ having no subgraph isomorphic to a member of $\mathcal{F}$ has an independent set of size at least $\frac{3}{8}n$ . In this paper, we prove this conjecture. As a corollary, we obtain that every $2$ -connected $n$ -vertex triangle-free graph with maximum degree at most $3$ has an independent set of size at least $\frac{3}{8}n$ , with the exception of the six graphs in $\mathcal{F}$ . This confirms a conjecture made independently by Bajnok and Brinkmann, and by Fraughnaugh and Locke.

preprint2020arXiv

Structure and colour in triangle-free graphs

Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $χ$ contains a rainbow independent set of size $\lceil\frac12χ\rceil$ . This is sharp up to a factor $2$ . This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $χ$ contains an induced cycle of length $Ω(χ\logχ)$ as $χ\to\infty$ . Even if one only demands an induced path of length $Ω(χ\logχ)$ , the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$ -free graph has chromatic number at most $c D/\log D$ . We prove this assertion with `triangle-free' replaced by `regular girth $5$ '.

preprint2016arXiv

Packing graphs of bounded codegree

Two graphs $G_1$ and $G_2$ on $n$ vertices are said to pack if there exist injective mappings of their vertex sets into $[n]$ such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobás and Eldridge and, independently, Catlin, asserts that, if $(Δ_1(G)+1) (Δ_2(G)+1) \le n+1$ , then $G_1$ and $G_2$ pack. We consider the validity of this assertion under the additional assumption that $G_1$ or $G_2$ has bounded codegree. In particular, we prove for all $t \ge 2$ that, if $G_1$ contains no copy of the complete bipartite graph $K_{2,t}$ and $Δ_1 > 17 t \cdot Δ_2$ , then $(Δ_1(G)+1) (Δ_2(G)+1) \le n+1$ implies that $G_1$ and $G_2$ pack. We also provide a mild improvement if moreover $G_2$ contains no copy of the complete tripartite graph $K_{1,1,s}$ , $s\ge 1$ .

preprint2014arXiv

The dimension of the Incipient Infinite Cluster

We study the Incipient Infinite Cluster (IIC) of high-dimensional bond percolation on $\mathbb{Z}^d$ . We prove that the mass dimension of IIC almost surely equals $4$ and the volume growth exponent of IIC almost surely equals $2$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Wouter Cames van Batenburg

Research overview

Is this your work?

6 publications

Bipartite induced density in triangle-free graphs

Erdős-Pósa from ball packing

Large independent sets in triangle-free cubic graphs: beyond planarity

Structure and colour in triangle-free graphs

Packing graphs of bounded codegree

The dimension of the Incipient Infinite Cluster

See the researcher in context

Building this map preview