Back to Search
Start Over
All feedback arc sets of a random Tur\'an tournament have n/k-k+1 disjoint k-cliques (and this is tight)
- Source :
- SIAM J. Discrete Math. Vol. 35, No. 2, pp. 1460--1477, 2021
- Publication Year :
- 2021
-
Abstract
- We look at structures that must be removed (or reversed) in order to make acyclic a given oriented graph. For a directed acyclic graph $H$ and an oriented graph $G$, let $f_H(G)$ be the maximum number of pairwise disjoint copies of $H$ that can be found in {\em all} feedback arc sets of $G$. In particular, to make $G$ acyclic, one must remove (or reverse) $f_H(G)$ pairwise disjoint copies of $H$. Most intriguing is the case where $H$ is a $k$-clique, where the parameter is denoted by $f_k(G)$. Determining $f_k(G)$ for arbitrary $G$ seems challenging. Here we determine $f_k(G)$ precisely for almost all $k$-partite tournaments. Let $s(G)$ denote the size of the smallest vertex class of a $k$-partite tournament $G$. We prove that for all sufficiently large $s=s(G)$, a random $k$-partite tournament $G$ satisfies $f_k(G) = s(G)-k+1$ almost surely. In particular, as the title states, $f_k(G) = \lfloor n/k\rfloor-k+1$ almost surely, where $G$ is a random orientation of the Tur\'an graph $T(n,k)$.<br />Comment: 23 pages
- Subjects :
- Mathematics - Combinatorics
05C20, 05C35, 05C80
Subjects
Details
- Database :
- arXiv
- Journal :
- SIAM J. Discrete Math. Vol. 35, No. 2, pp. 1460--1477, 2021
- Publication Type :
- Report
- Accession number :
- edsarx.2106.15470
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1137/20M1356506