TILING DIRECTED GRAPHS WITH TOURNAMENTS
Forum of Mathematics, Sigma, Tome 6 (2018)
Voir la notice de l'article provenant de la source Cambridge University Press
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.
@article{10_1017_fms_2018_2,
author = {ANDRZEJ CZYGRINOW and LOUIS DEBIASIO and THEODORE MOLLA and ANDREW TREGLOWN},
title = {TILING {DIRECTED} {GRAPHS} {WITH} {TOURNAMENTS}},
journal = {Forum of Mathematics, Sigma},
publisher = {mathdoc},
volume = {6},
year = {2018},
doi = {10.1017/fms.2018.2},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2018.2/}
}
TY - JOUR AU - ANDRZEJ CZYGRINOW AU - LOUIS DEBIASIO AU - THEODORE MOLLA AU - ANDREW TREGLOWN TI - TILING DIRECTED GRAPHS WITH TOURNAMENTS JO - Forum of Mathematics, Sigma PY - 2018 VL - 6 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.1017/fms.2018.2/ DO - 10.1017/fms.2018.2 LA - en ID - 10_1017_fms_2018_2 ER -
%0 Journal Article %A ANDRZEJ CZYGRINOW %A LOUIS DEBIASIO %A THEODORE MOLLA %A ANDREW TREGLOWN %T TILING DIRECTED GRAPHS WITH TOURNAMENTS %J Forum of Mathematics, Sigma %D 2018 %V 6 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.1017/fms.2018.2/ %R 10.1017/fms.2018.2 %G en %F 10_1017_fms_2018_2
ANDRZEJ CZYGRINOW; LOUIS DEBIASIO; THEODORE MOLLA; ANDREW TREGLOWN. TILING DIRECTED GRAPHS WITH TOURNAMENTS. Forum of Mathematics, Sigma, Tome 6 (2018). doi: 10.1017/fms.2018.2
Cité par Sources :