Spelling suggestions: "subject:"particiones monocromática"" "subject:"particiones monoaromáticos""
1 |
Hypergraph cycle partitionsBustamante Franco, Sebastián Felipe January 2018 (has links)
Tesis para optar al grado de Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / The main focus of this thesis is the study of monochromatic cycle partitions in uniform hypergraphs.
The first part deals with Berge-cycles. Extending a result of Rado to hypergraphs, we prove that for all $r,k \in \N$ with $k \geq 2$, the vertices of every $r(k-1)$-edge-coloured countably infinite complete $k$-uniform hypergraph can be core-partitioned into at most $r$ monochromatic Berge-cycles of different colours. We further describe a construction showing that this result is best possible.
The second part deals with $\ell$-cycles. We show that for all $\ell, k, n \in \N$ with $\ell \leq k/2$ the following hypergraph-variant of Lehel's conjecture is true. Every $2$-edge-colouring of the $k$-uniform complete graph on $n$ vertices has at most two disjoint monochromatic $\ell$-cycles in different colours that together cover all but a constant number of vertices, where the constant depends on $k$ and $\ell$. Furthermore, we can cover all vertices with at most $4$ ($3$ if $\ell \leq k/3$) disjoint monochromatic $\ell$-cycles.
The third part deals with tight-cycles in $2$-edge-colourings of complete $3$-uniform hypergraphs.
We show that for every $\eta > 0$ there exists an integer $n_0$ such that every $2$-edge-colouring of the $3$-uniform complete hypergraph on $n \geq n_0$ vertices contains two disjoint monochromatic tight cycles of distinct colours that together cover all but at most $\eta n$ vertices.
Finally, the fourth part deals with tight-cycles in a more general setting.
We prove that for every $k,r \in \N$, the vertices of every $r$-edge-coloured complete $k$-uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles, confirming a conjecture of Gy\'arf\'as.
We further prove that for every $r,p \in \N$, the vertices of every $r$-edge-coloured complete graph can be partitioned into a bounded number of $p$-th powers of cycles, settling a problem of Elekes, D. Soukup, L. Soukup and Szentmikl\'ossy.
In fact we prove a common generalisation of both theorems which further extends these results to all host hypergraphs with bounded independence number. / CONICYT/Doctorado Nacional/2014-21141116, CMM-Conicyt PIA AFB170001
|
Page generated in 0.1232 seconds