Source author record

Dennis Clemens

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

ResearcherUnclaimed source record

math.CO math.LO

Catalog footprint

Research overview

15works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Ramsey equivalence for asymmetric pairs of graphs

A graph $F$ is Ramsey for a pair of graphs $(G,H)$ if any red/blue-coloring of the edges of $F$ yields a copy of $G$ with all edges colored red or a copy of $H$ with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case $G=H$ , received considerable attention. This led to the open question whether there are connected graphs $G$ and $G'$ such that $(G,G)$ and $(G',G')$ are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several non-trivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form $(T,K_t)$ , where $T$ is a tree and $K_t$ is a complete graph. We show that, if $T$ belongs to a certain family of trees, including all non-trivial stars, then $(T,K_t)$ is Ramsey equivalent to a family of pairs of the form $(T,H)$ , where $H$ is obtained from $K_t$ by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for $(T,H)$ to be Ramsey equivalent to $(T,K_t)$ , $H$ must have roughly this form. On the other hand, we prove that for many other trees $T$ , including all odd-diameter trees, $(T,K_t)$ is not equivalent to any such pair, not even to the pair $(T, K_t\cdot K_2)$ , where $K_t\cdot K_2$ is a complete graph $K_t$ with a single edge attached.

preprint2022arXiv

The tree packing conjecture for trees of almost linear maximum degree

We prove that there is $c>0$ such that for all sufficiently large $n$ , if $T_1,\dots,T_n$ are any trees such that $T_i$ has $i$ vertices and maximum degree at most $cn/\log n$ , then $\{T_1,\dots,T_n\}$ packs into $K_n$ . Our main result actually allows to replace the host graph $K_n$ by an arbitrary quasirandom graph, and to generalize from trees to graphs of bounded degeneracy that are rich in bare paths, contain some odd degree vertices, and only satisfy much less stringent restrictions on their number of vertices.

preprint2020arXiv

Minimal Ramsey graphs with many vertices of small degree

Given any graph $H$ , a graph $G$ is said to be $q$ -Ramsey for $H$ if every coloring of the edges of $G$ with $q$ colors yields a monochromatic subgraph isomorphic to $H$ . Further, such a graph $G$ is said to be minimal $q$ -Ramsey for $H$ if additionally no proper subgraph $G'$ of $G$ is $q$ -Ramsey for $H$ . In 1976, Burr, Erdős, and Lovász initiated the study of the parameter $s_q(H)$ , defined as the smallest minimum degree among all minimal $q$ -Ramsey graphs for $H$ . In this paper, we consider the problem of determining how many vertices of degree $s_q(H)$ a minimal $q$ -Ramsey graph for $H$ can contain. Specifically, we seek to identify graphs for which a minimal $q$ -Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property $s_q$ -abundant. Among other results, we prove that every cycle is $s_q$ -abundant for any integer $q\geq 2$ . We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr et al. and Fox et al. To prove our results and construct suitable minimal Ramsey graphs, we develop certain new gadget graphs, called pattern gadgets, which generalize and extend earlier constructions that have proven useful in the study of minimal Ramsey graphs. These new gadgets might be of independent interest.

preprint2020arXiv

On minimal Ramsey graphs and Ramsey equivalence in multiple colours

For an integer $q\ge 2$ , a graph $G$ is called $q$ -Ramsey for a graph $H$ if every $q$ -colouring of the edges of $G$ contains a monochromatic copy of $H$ . If $G$ is $q$ -Ramsey for $H$ , yet no proper subgraph of $G$ has this property then $G$ is called $q$ -Ramsey-minimal for $H$ . Generalising a statement by Burr, Nešetřil and Rödl from 1977 we prove that, for $q\ge 3$ , if $G$ is a graph that is not $q$ -Ramsey for some graph $H$ then $G$ is contained as an induced subgraph in an infinite number of $q$ -Ramsey-minimal graphs for $H$ , as long as $H$ is $3$ -connected or isomorphic to the triangle. For such $H$ , the following are some consequences. (1) For $2\le r< q$ , every $r$ -Ramsey-minimal graph for $H$ is contained as an induced subgraph in an infinite number of $q$ -Ramsey-minimal graphs for $H$ . (2) For every $q\ge 3$ , there are $q$ -Ramsey-minimal graphs for $H$ of arbitrarily large maximum degree, genus, and chromatic number. (3) The collection $\{{\cal M}_q(H) : H \text{ is 3-connected or } K_3\}$ forms an antichain with respect to the subset relation, where ${\cal M}_q(H)$ denotes the set of all graphs that are $q$ -Ramsey-minimal for $H$ . We also address the question which pairs of graphs satisfy ${\cal M}_q(H_1)={\cal M}_q(H_2)$ , in which case $H_1$ and $H_2$ are called $q$ -equivalent. We show that two graphs $H_1$ and $H_2$ are $q$ -equivalent for even $q$ if they are $2$ -equivalent, and that in general $q$ -equivalence for some $q\ge 3$ does not necessarily imply $2$ -equivalence. Finally we indicate that for connected graphs this implication may hold: Results by Nešetřil and Rödl and by Fox, Grinshpun, Liebenau, Person and Szabó imply that the complete graph is not $2$ -equivalent to any other connected graph. We prove that this is the case for an arbitrary number of colours.

preprint2019arXiv

Connector-Breaker games on random boards

By now, the Maker-Breaker connectivity game on a complete graph $K_n$ or on a random graph $G\sim G_{n,p}$ is well studied. Recently, London and Pluhár suggested a variant in which Maker always needs to choose her edges in such a way that her graph stays connected. By their results it follows that for this connected version of the game, the threshold bias on $K_n$ and the threshold probability on $G\sim G_{n,p}$ for winning the game drastically differ from the corresponding values for the usual Maker-Breaker version, assuming Maker's bias to be $1$ . However, they observed that the threshold biases of both versions played on $K_n$ are still of the same order if instead Maker is allowed to claim two edges in every round. Naturally, this made London and Pluhár ask whether a similar phenomenon can be observed when a $(2:2)$ game is played on $G_{n,p}$ . We prove that this is not the case, and determine the threshold probability for winning this game to be of size $n^{-2/3+o(1)}$ .

preprint2016arXiv

A non-trivial upper bound on the threshold bias of the Oriented-cycle game

In the Oriented-cycle game, introduced by Bollobás and Szabó, two players, called OMaker and OBreaker, alternately direct edges of $K_n$ . OMaker directs exactly one edge, whereas OBreaker is allowed to direct between one and $b$ edges. OMaker wins if the final tournament contains a directed cycle, otherwise OBreaker wins. Bollobás and Szabó conjectured that for a bias as large as $n-3$ OMaker has a winning strategy if OBreaker must take exactly $b$ edges in each round. It was shown recently by Ben-Eliezer, Krivelevich and Sudakov, that OMaker has a winning strategy for this game whenever $b\leq \frac{n}{2}-2$ . In this paper, we show that OBreaker has a winning strategy whenever $b\geq \frac{5n}{6}+2$ . Moreover, in case OBreaker is required to direct exactly $b$ edges in each move, we show that OBreaker wins for $b\geq \frac{19n}{20}$ , provided that $n$ is large enough. This refutes the conjecture by Bollobás and Szabó.

preprint2016arXiv

Creating cycles in Walker-Breaker games

We consider biased $(1:b)$ Walker-Breaker games: Walker and Breaker alternately claim edges of the complete graph $K_n$ , Walker taking one edge and Breaker claiming $b$ edges in each round, with the constraint that Walker needs to choose her edges according to a walk. As questioned in a paper by Espig, Frieze, Krivelevich and Pegden, we study how long a cycle Walker is able to create and for which biases $b$ Walker has a chance to create a cycle of given constant length.

preprint2016arXiv

How fast can Maker win in fair biased games?

We study (a:a) Maker-Breaker games played on the edge set of the complete graph on n vertices. In the following four games - perfect matching game, Hamilton cycle game, star factor game and path factor game, our goal is to determine the least number of moves which Maker needs in order to win these games. Moreover, for all games except for the star factor game, we show how Red can win in the strong version of these games.

preprint2015arXiv

A remark on the Tournament game

We study the Maker-Breaker tournament game played on the edge set of a given graph $G$ . Two players, Maker and Breaker claim unclaimed edges of $G$ in turns, and Maker wins if by the end of the game she claims all the edges of a pre-defined goal tournament. Given a tournament $T_k$ on $k$ vertices, we determine the threshold bias for the $(1:b)$ $T_k$ -tournament game on $K_n$ . We also look at the $(1:1)$ $T_k$ -tournament game played on the edge set of a random graph ${\mathcal{G}_{n,p}}$ and determine the threshold probability for Maker's win. We compare these games with the clique game and discuss whether a random graph intuition is satisfied.

preprint2015arXiv

An improved bound on the sizes of matchings guaranteeing a rainbow matching

A conjecture by Aharoni and Berger states that every family of $n$ matchings of size $n+1$ in a bipartite multigraph contains a rainbow matching of size $n$ . In this paper we prove that matching sizes of $(3/2 + o(1)) n$ suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best known one in case we only aim to find a rainbow matching of size $n-1$ . This improves previous results by Aharoni, Charbit and Howard, and Kotlar and Ziv.

preprint2015arXiv

Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs

A uniform hypergraph $H$ is called $k$ -Ramsey for a hypergraph $F$ , if no matter how one colors the edges of $H$ with $k$ colors, there is always a monochromatic copy of $F$ . We say that $H$ is minimal $k$ -Ramsey for $F$ , if $H$ is $k$ -Ramsey for $F$ but every proper subhypergraph of $H$ is not. Burr, Erdős and Lovasz studied various parameters of minimal Ramsey graphs. In this paper we initiate the study of minimum degrees and codegrees of minimal Ramsey $3$ -uniform hypergraphs. We show that the smallest minimum vertex degree over all minimal $k$ -Ramsey $3$ -uniform hypergraphs for $K_t^{(3)}$ is exponential in some polynomial in $k$ and $t$ . We also study the smallest possible minimum codegrees over minimal $2$ -Ramsey $3$ -uniform hypergraphs.

preprint2015arXiv

On sets not belonging to algebras and rainbow matchings in graphs

Motivated by a question of Grinblat, we study the minimal number $\mathfrak{v}(n)$ that satisfies the following. If $A_1,\ldots, A_n$ are equivalence relations on a set $X$ such that for every $i\in[n]$ there are at least $\mathfrak{v}(n)$ elements whose equivalence classes with respect to $A_i$ are nontrivial, then $A_1, \ldots, A_n$ contain a rainbow matching, i.e. there exist $2n$ distinct elements $x_1,y_1,\ldots,x_n,y_n\in X$ with $x_i\sim_{A_i} y_i$ for each $i\in [n]$ . Grinblat asked whether $\mathfrak{v}(n) = 3n-2$ for every $n\geq 4$ . The best-known upper bound was $\mathfrak{v}(n) \leq 16n/5 + \mathcal{O}(1)$ due to Nivash and Omri. Transferring the problem into the setting of edge-coloured multigraphs, we affirm Grinblat's question asymptotically, i.e. we show that $\mathfrak{v}(n) = 3n+o(n)$ .

preprint2014arXiv

Keeping Avoider's graph almost acyclic

We consider biased $(1:b)$ Avoider-Enforcer games in the monotone and strict versions. In particular, we show that Avoider can keep his graph being a forest for every but maybe the last round of the game if $b \geq 200 n \ln n$ . By this we obtain essentially optimal upper bounds on the threshold biases for the non-planarity game, the non- $k$ -colorability game, and the $K_t$ -minor game thus addressing a question and improving the results of Hefetz, Krivelevich, Stojaković, and Szabó. Moreover, we give a slight improvement for the lower bound in the non-planarity game.

preprint2013arXiv

Building spanning trees quickly in Maker-Breaker games

For a tree T on n vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on n vertices, which Maker wins as soon as the graph she builds contains a copy of T. We prove that if T has bounded maximum degree, then Maker can win this game within n+1 moves. Moreover, we prove that Maker can build almost every tree on n vertices in n-1 moves and provide non-trivial examples of families of trees which Maker cannot build in n-1 moves.

preprint2012arXiv

Fast strategies in Maker-Breaker games played on random boards

In this paper we analyze classical Maker-Breaker games played on the edge set of a sparse random board $G\sim \gnp$. We consider the Hamiltonicity game, the perfect matching game and the $k$ -connectivity game. We prove that for $p(n)\geq \text{polylog}(n)/n$ , the board $G\sim \gnp$ is typically such that Maker can win these games asymptotically as fast as possible, i.e. within $n+o(n)$ , $n/2+o(n)$ and $kn/2+o(n)$ moves respectively.

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.

Dennis Clemens

Research overview

Is this your work?

15 publications

Ramsey equivalence for asymmetric pairs of graphs

The tree packing conjecture for trees of almost linear maximum degree

Minimal Ramsey graphs with many vertices of small degree

On minimal Ramsey graphs and Ramsey equivalence in multiple colours

Connector-Breaker games on random boards

A non-trivial upper bound on the threshold bias of the Oriented-cycle game

Creating cycles in Walker-Breaker games

How fast can Maker win in fair biased games?

A remark on the Tournament game

An improved bound on the sizes of matchings guaranteeing a rainbow matching

Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs

On sets not belonging to algebras and rainbow matchings in graphs

Keeping Avoider's graph almost acyclic

Building spanning trees quickly in Maker-Breaker games

Fast strategies in Maker-Breaker games played on random boards

See the researcher in context

Building this map preview