Source author record

Matthew Wales

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Graphs of low average degree without independent transversals

An independent transversal of a graph $G$ with a vertex partition $\mathcal P$ is an independent set of $G$ intersecting each block of $\mathcal P$ in a single vertex. Wanless and Wood proved that if each block of $\mathcal P$ has size at least $t$ and the average degree of vertices in each block is at most $t/4$ , then an independent transversal of $\mathcal P$ exists. We present a construction showing that this result is optimal: for any $\varepsilon > 0$ and sufficiently large $t$ , there is a family of forests with vertex partitions whose block size is at least $t$ , average degree of vertices in each block is at most $(\frac14+\varepsilon)t$ , and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld-Wanless-Wood scheme or the Local Cut Lemma are tight for this problem. Further constructions are given for variants of the problem, including the hypergraph version.

preprint2022arXiv

On the extremal function for graph minors

For a graph $H$ , let $c(H)=\inf\{c\,:\,e(G)\geq c|G| \mbox{ implies } G\succ H\,\}$, where $G\succ H$ means that $H$ is a minor of $G$ . We show that if $H$ has average degree $d$ , then $c(H)\le (0.319\ldots+o_d(1))|H|\sqrt{\log d}$ where $0.319\ldots$ is an explicitly defined constant. This bound matches a corresponding lower bound shown to hold for almost all such $H$ by Norin, Reed, Wood and the first author.

preprint2019arXiv

Distribution of colors in Gallai colorings

A Gallai coloring is an edge coloring that avoids triangles colored with three different colors. Given integers $e_1\ge e_2 \ge \dots \ge e_k$ with $\sum_{i=1}^ke_i={n \choose 2}$ for some $n$ , does there exist a Gallai $k$ -coloring of $K_n$ with $e_i$ edges in color $i$ ? In this paper, we give several sufficient conditions and one necessary condition to guarantee a positive answer to the above question. In particular, we prove the existence of a Gallai-coloring if $e_1-e_k\le 1$ and $k \le \lfloor n/2\rfloor$ . We prove that for any integer $k\ge 3$ there is a (unique) integer $g(k)$ with the following property: there exists a Gallai $k$ -coloring of $K_n$ with $e_i$ edges in color $i$ for every $e_1\le\dots \le e_k$ satisfying $\sum_{i=1}^ke_i={n\choose 2}$ , if and only if $n\ge g(k)$ . We show that $g(3)=5$ , $g(4)=8$ , and $2k-2\le g(k)\le 8k^2+1$ for every $k\ge 3$ .

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.