pith. sign in

arxiv: 1805.01699 · v1 · pith:NQX3DQMHnew · submitted 2018-05-04 · 🧮 math.CO

Partitioning Edge-Coloured Complete Symmetric Digraphs into Monochromatic Complete Subgraphs

classification 🧮 math.CO
keywords completemonochromaticcoloursymmetricpathsdensitydigraphdigraphs
0
0 comments X
read the original abstract

Let $K_{\mathbb{N}}$ be the complete symmetric digraph on the positive integers. Answering a question of DeBiasio and McKenney, we construct a $2$-colouring of the edges of $K_{\mathbb{N}}$ in which every monochromatic path has density~$0$. However, if we restrict the length of monochromatic paths in one colour, then no example as above can exist: We show that every $(r+1)$-edge-coloured complete symmetric digraph (of arbitrary infinite cardinality) containing no directed paths of edge-length $\ell_i$ for any colour $i\leq r$ can be covered by $\prod_{i\leq r} \ell_i$ pairwise disjoint monochromatic complete symmetric digraphs in colour $r+1$. Furthermore, we present a stability version for the countable case of the latter result: We prove that the edge-colouring is uniquely determined on a large subgraph, as soon as the upper density of monochromatic paths in colour $r+1$ is bounded by $\prod_{i\in [r]}\frac{1}{\ell_i}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.