Tiling transitive tournaments and their blow-ups
| dc.creator | Yuster, Raphael | |
| dc.date | 2002-10-22 | |
| dc.date.accessioned | 2026-07-07T04:52:13Z | |
| dc.date.available | 2026-07-07T04:52:13Z | |
| dc.description | Let $TT_k$ denote the transitive tournament on $k$ vertices. Let $TT(h,k)$ denote the graph obtained from $TT_k$ by replacing each vertex with an independent set of size $h \geq 1$. The following result is proved: Let $c_2=1/2$, $c_3=5/6$ and $c_k=1-2^{-k-\log k}$ for $k \geq 4$. For every $ε> 0$ there exists $N=N(ε,h,k)$ such that for every undirected graph $G$ with $n > N$ vertices and with $δ(G) \geq c_kn$, every orientation of $G$ contains vertex disjoint copies of $TT(h,k)$ that cover all but at most $εn$ vertices. In the cases $k=2$ and $k=3$ the result is asymptotically tight. For $k \geq 4$, $c_k$ cannot be improved to less than $1-2^{-0.5k(1+o(1))}$. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/math/0210338 | |
| dc.identifier | http://arxiv.org/abs/math/0210338 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/65388 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C20 | |
| dc.title | Tiling transitive tournaments and their blow-ups | |
| dc.type | text |