Source author record

Kevin Hendrey

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

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs ${(\ell, z)}$ of integers where such a duality holds for the family of cycles of length $\ell$ modulo $z$ . We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface.

preprint2024arXiv

Linear bounds on treewidth in terms of excluded planar minors

One of the fundamental results in graph minor theory is that for every planar graph $H$ , there is a minimum integer $f(H)$ such that graphs with no minor isomorphic to $H$ have treewidth at most $f(H)$ . A lower bound for ${f(H)}$ can be obtained by considering the maximum integer $k$ such that $H$ contains $k$ vertex-disjoint cycles. There exists a graph of treewidth ${Ω(k\log k)}$ which does not contain $k$ vertex-disjoint cycles, from which it follows that ${f(H) = Ω(k\log k)}$ . In particular, if ${f(H)}$ is linear in ${\lvert{V(H)}\rvert}$ for graphs $H$ from a subclass of planar graphs, it is necessary that $n$ -vertex graphs from the class contain at most ${O(n/\log(n))}$ vertex-disjoint cycles. We ask whether this is also a sufficient condition, and demonstrate that this is true for classes of planar graphs with bounded component size. For an $n$ -vertex graph $H$ which is a disjoint union of $r$ cycles, we show that ${f(H) \leq 3n/2 + O(r^2 \log r)}$ , and improve this to ${f(H) \leq n + O(\sqrt{n})}$ when ${r = 2}$ . In particular this bound is linear when ${r=O(\sqrt{n}/\log(n))}$ . We present a linear bound for ${f(H)}$ when $H$ is a subdivision of an $r$ -edge planar graph for any constant $r$ . We also improve the best known bounds for ${f(H)}$ when $H$ is the wheel graph or the ${4 \times 4}$ grid, obtaining a bound of $160$ for the latter.

preprint2023arXiv

Twin-width of sparse random graphs

We show that the twin-width of every $n$ -vertex $d$ -regular graph is at most $n^{\frac{d-2}{2d-2}+o(1)}$ and that almost all $d$ -regular graphs attain this bound. More generally, we obtain bounds on the twin-width of sparse Erdős-Renyi and regular random graphs, complementing the bounds in the denser regime due to Ahn, Chakraborti, Hendrey, Kim and Oum.

preprint2022arXiv

Extremal functions for sparse minors

The "extremal function" $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor, where the "density" of a graph $G$ is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$ , as well as almost all graphs $H$ of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example, we prove that for every planar graph $H$ , $c(H) = (1+o(1))\cdot\max\left\{\frac{|V(H)|}{2},|V(H)| - α(H)\right\},$ extending recent results of Haslegrave, Kim and Liu (2020). We also show that an asymptotically tight bound on the extremal function of graphs in minor-closed families proposed by Haslegrave, Kim and Liu (2020) is equivalent to a well studied open weakening of Hadwiger's conjecture.

preprint2022arXiv

Product structure of graph classes with bounded treewidth

We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the "underlying treewidth" of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$ , for every graph ${G \in \mathcal{G}}$ there is a graph $H$ with ${\text{tw}(H) \leq c}$ such that $G$ is isomorphic to a subgraph of ${H \boxtimes K_{f(\text{tw}(G))}}$ . We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 3; the class of $K_{s,t}$ -minor-free graphs has underlying treewidth $s$ (for ${t \geq \max\{s,3\}}$ ); and the class of $K_t$ -minor-free graphs has underlying treewidth ${t-2}$ . In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star.

preprint2021arXiv

A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $\ell$ , cycles of length $p$ modulo $q$ , cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $\mathbb{Z}_2$ -homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.

preprint2019arXiv

Covering radius in the Hamming permutation space

Let $\mathcal{S}_n$ denote the set of permutations of $\{1,2,\dots,n\}$ . The function $f(n,s)$ is defined to be the minimum size of a subset $S\subseteq \mathcal{S}_n$ with the property that for any $ρ\in \mathcal{S}_n$ there exists some $σ\in S$ such that the Hamming distance between $ρ$ and $σ$ is at most $n-s$ . The value of $f(n,2)$ is the subject of a conjecture by Kézdy and Snevily, which implies several famous conjectures about latin squares. We prove that the odd $n$ case of the Kézdy-Snevily Conjecture implies the whole conjecture. We also show that $f(n,2)>3n/4$ for all $n$ , that $s!< f(n,s)< 3s!(n-s)\log n$ for $1\leq s\leq n-2$ and that $f(n,s)>\left\lfloor \frac{2+\sqrt{2s-2}}{2}\right\rfloor \frac{n}{2}$ if $s\geq 3$ .

preprint2016arXiv

Sparse graphs of high gonality

By considering graphs as discrete analogues of Riemann surfaces, Baker and Norine (Adv. Math. 2007) developed a concept of linear systems of divisors for graphs. Building on this idea, a concept of gonality for graphs has been defined and has generated much recent interest. We show that there are connected graphs of treewidth 2 of arbitrarily high gonality. We also show that there exist pairs of connected graphs $\{G,H\}$ such that $H\subseteq G$ and $H$ has strictly lower gonality than $G$ . These results resolve three open problems posed in a recent survey by Norine (Surveys in Combinatorics 2015).

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.