ﻻ يوجد ملخص باللغة العربية
Our main result is that every graph $G$ on $nge 10^4r^3$ vertices with minimum degree $delta(G) ge (1 - 1 / 10^4 r^{3/2} ) n$ has a fractional $K_r$-decomposition. Combining this result with recent work of Barber, Kuhn, Lo and Osthus leads to the best known minimum degree thresholds for exact (non-fractional) $F$-decompositions for a wide class of graphs~$F$ (including large cliques). For general $k$-uniform hypergraphs, we give a short argument which shows that there exists a constant $c_k>0$ such that every $k$-uniform hypergraph $G$ on $n$ vertices with minimum codegree at least $(1- c_k /r^{2k-1}) n $ has a fractional $K^{(k)}_r$-decomposition, where $K^{(k)}_r$ is the complete $k$-uniform hypergraph on $r$ vertices. (Related fractional decomposition results for triangles have been obtained by Dross and for hypergraph cliques by Dukes as well as Yuster.) All the above new results involve purely combinatorial arguments. In particular, this yields a combinatorial proof of Wilsons theorem that every large $F$-divisible complete graph has an $F$-decomposition.
Let $G$ be a graph whose edges are coloured with $k$ colours, and $mathcal H=(H_1,dots , H_k)$ be a $k$-tuple of graphs. A monochromatic $mathcal H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edg
We prove that for any integer $kgeq 2$ and $varepsilon>0$, there is an integer $ell_0geq 1$ such that any $k$-uniform hypergraph on $n$ vertices with minimum codegree at least $(1/2+varepsilon)n$ has a fractional decomposition into tight cycles of le
Our main result essentially reduces the problem of finding an edge-decomposition of a balanced r-partite graph of large minimum degree into r-cliques to the problem of finding a fractional r-clique decomposition or an approximate one. Together with v
We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on $n$ vertices can be decomposed into at most $leftlceil frac{n}{2}rightrceil$ paths, while
There is a remarkable connection between the clique number and the Lagrangian of a 2-graph proved by Motzkin and Straus in 1965. It is useful in practice if similar results hold for hypergraphs. However the obvious generalization of Motzkin and Strau