TILING DIRECTED GRAPHS WITH TOURNAMENTS
The Hajnal–Szemerédi theorem states that for any positive integer $r$ and any multiple $n$ of...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2018-01-01
|
| Series: | Forum of Mathematics, Sigma |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050509418000026/type/journal_article |
| _version_ | 1811156273538793472 |
|---|---|
| author | ANDRZEJ CZYGRINOW LOUIS DEBIASIO THEODORE MOLLA ANDREW TREGLOWN |
| author_facet | ANDRZEJ CZYGRINOW LOUIS DEBIASIO THEODORE MOLLA ANDREW TREGLOWN |
| author_sort | ANDRZEJ CZYGRINOW |
| collection | DOAJ |
| description | The Hajnal–Szemerédi theorem states that for any positive integer
$r$
and any multiple
$n$
of
$r$
, if
$G$
is a graph on
$n$
vertices and
$\unicode[STIX]{x1D6FF}(G)\geqslant (1-1/r)n$
, then
$G$
can be partitioned into
$n/r$
vertex-disjoint copies of the complete graph on
$r$
vertices. We prove a very general analogue of this result for directed graphs: for any positive integer
$r$
with
$r\neq 3$
and any sufficiently large multiple
$n$
of
$r$
, if
$G$
is a directed graph on
$n$
vertices and every vertex is incident to at least
$2(1-1/r)n-1$
directed edges, then
$G$
can be partitioned into
$n/r$
vertex-disjoint subgraphs of size
$r$
each of which contain every tournament on
$r$
vertices (the case
$r=3$
is different and was handled previously). In fact, this result is a consequence of a tiling result for standard multigraphs (that is multigraphs where there are at most two edges between any pair of vertices). A related Turán-type result is also proven. |
| first_indexed | 2024-04-10T04:47:43Z |
| format | Article |
| id | doaj.art-ea351964ad4748bba389c8268e3917cf |
| institution | Directory Open Access Journal |
| issn | 2050-5094 |
| language | English |
| last_indexed | 2024-04-10T04:47:43Z |
| publishDate | 2018-01-01 |
| publisher | Cambridge University Press |
| record_format | Article |
| series | Forum of Mathematics, Sigma |
| spelling | doaj.art-ea351964ad4748bba389c8268e3917cf2023-03-09T12:34:35ZengCambridge University PressForum of Mathematics, Sigma2050-50942018-01-01610.1017/fms.2018.2TILING DIRECTED GRAPHS WITH TOURNAMENTSANDRZEJ CZYGRINOW0LOUIS DEBIASIO1THEODORE MOLLA2ANDREW TREGLOWN3School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ 85281, USA;Department of Mathematics, Miami University, Oxford, OH 45056, USA;Department of Mathematics and Statistics, University of South Florida, Tampa, FL 33620, USA;School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK;The Hajnal–Szemerédi theorem states that for any positive integer $r$ and any multiple $n$ of $r$ , if $G$ is a graph on $n$ vertices and $\unicode[STIX]{x1D6FF}(G)\geqslant (1-1/r)n$ , then $G$ can be partitioned into $n/r$ vertex-disjoint copies of the complete graph on $r$ vertices. We prove a very general analogue of this result for directed graphs: for any positive integer $r$ with $r\neq 3$ and any sufficiently large multiple $n$ of $r$ , if $G$ is a directed graph on $n$ vertices and every vertex is incident to at least $2(1-1/r)n-1$ directed edges, then $G$ can be partitioned into $n/r$ vertex-disjoint subgraphs of size $r$ each of which contain every tournament on $r$ vertices (the case $r=3$ is different and was handled previously). In fact, this result is a consequence of a tiling result for standard multigraphs (that is multigraphs where there are at most two edges between any pair of vertices). A related Turán-type result is also proven.https://www.cambridge.org/core/product/identifier/S2050509418000026/type/journal_article5C35 (primary)5C205C70 (secondary) |
| spellingShingle | ANDRZEJ CZYGRINOW LOUIS DEBIASIO THEODORE MOLLA ANDREW TREGLOWN TILING DIRECTED GRAPHS WITH TOURNAMENTS Forum of Mathematics, Sigma 5C35 (primary) 5C20 5C70 (secondary) |
| title | TILING DIRECTED GRAPHS WITH TOURNAMENTS |
| title_full | TILING DIRECTED GRAPHS WITH TOURNAMENTS |
| title_fullStr | TILING DIRECTED GRAPHS WITH TOURNAMENTS |
| title_full_unstemmed | TILING DIRECTED GRAPHS WITH TOURNAMENTS |
| title_short | TILING DIRECTED GRAPHS WITH TOURNAMENTS |
| title_sort | tiling directed graphs with tournaments |
| topic | 5C35 (primary) 5C20 5C70 (secondary) |
| url | https://www.cambridge.org/core/product/identifier/S2050509418000026/type/journal_article |
| work_keys_str_mv | AT andrzejczygrinow tilingdirectedgraphswithtournaments AT louisdebiasio tilingdirectedgraphswithtournaments AT theodoremolla tilingdirectedgraphswithtournaments AT andrewtreglown tilingdirectedgraphswithtournaments |