Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFractional Clique Decompositions of Dense Graphs and Hypergraphs
122
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 edge or forms a monochromatic copy of $H_i$ in colour $i$, for some $1le ile k$. Let $phi_{k}(n,mathcal H)$ be the smallest number $phi$, such that, for every order-$n$ graph and every $k$-edge-colouring, there is a monochromatic $mathcal H$-decomposition with at most $phi$ elements. Extending the previous results of Liu and Sousa [Monochromatic $K_r$-decompositions of graphs, Journal of Graph Theory}, 76:89--100, 2014], we solve this problem when each graph in $mathcal H$ is a clique and $nge n_0(mathcal H)$ is sufficiently large.
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 length $ell$ ($ell$-cycles for short) whenever $ellgeq ell_0$ and $n$ is large in terms of $ell$. This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into $ell$-cycles. Moreover, for graphs this even guarantees integral decompositions into $ell$-cycles and solves a problem posed by Glock, Kuhn and Osthus. For our proof, we introduce a new method for finding a set of $ell$-cycles such that every edge is contained in roughly the same number of $ell$-cycles from this set by exploiting that certain Markov chains are rapidly mixing.
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 very recent results of Bowditch and Dukes as well as Montgomery on fractional decompositions into triangles and cliques respectively, this gives the best known bounds on the minimum degree which ensures an edge-decomposition of an r-partite graph into r-cliques (subject to trivially necessary divisibility conditions). The case of triangles translates into the setting of partially completed Latin squares and more generally the case of r-cliques translates into the setting of partially completed mutually orthogonal Latin squares.
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 a conjecture of Haj{o}s states that any Eulerian graph on $n$ vertices can be decomposed into at most $leftlfloor frac{n-1}{2}rightrfloor$ cycles. The ErdH{o}s-Gallai conjecture states that any graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. We show that if $G$ is a sufficiently large graph on $n$ vertices with linear minimum degree, then the following hold. (i) $G$ can be decomposed into at most $frac{n}{2}+o(n)$ paths. (ii) If $G$ is Eulerian, then it can be decomposed into at most $frac{n}{2}+o(n)$ cycles. (iii) $G$ can be decomposed into at most $frac{3 n}{2}+o(n)$ cycles and edges. If in addition $G$ satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such $G$. (iv) $G$ can be decomposed into $max left{frac{odd(G)}{2},frac{Delta(G)}{2}right}+o(n)$ paths, where $odd(G)$ is the number of odd-degree vertices of $G$. (v) If $G$ is Eulerian, then it can be decomposed into $frac{Delta(G)}{2}+o(n)$ cycles. All bounds in (i)-(v) are asymptotically best possible.
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 Straus result to hypergraphs is false. Frankl and F{u}redi conjectured that the $r$-uniform hypergraph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${mathbb N}^{(r)}$ has the largest Lagrangian of all $r$-uniform hypergraphs with $m$ edges. For $r=2$, Motzkin and Straus theorem confirms this conjecture. For $r=3$, it is shown by Talbot that this conjecture is true when $m$ is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for $3$-uniform hypergraphs. As an application of this connection, we confirm that Frankl and F{u}redis conjecture holds for bigger ranges of $m$ when $r$=3. We also obtain two weak
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
