Vector clique decompositions

DOI10.1137/1.9781611975482.75MaRDI QIDQ5236259zbMATH OpenOpenAlexFDO

Authors Raphael Yuster

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.00682

zbMATH Keywords

induced subgraphspolynomial time algorithm

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Let $F_k$ be the set of graphs on $k$ vertices. For a graph $G$, a $k$-decomposition is a set of induced subgraphs of $G$, each isomorphic to an element of $F_k$, such that each pair of vertices of $G$ is in exactly one element of the set. A fundamental result of Wilson is that for all $n=|V(G)|$ sufficiently large, $G$ has a $k$-decomposition if and only if $G$ is $k$-divisible. Let $$ be indexed by $F_k$. For a $k$-decomposition $L$ of $G$, let $$ where $d_{L,F}$ is the fraction of elements of $L$ isomorphic to $F$. Let $$ and $$. It is not difficult to prove that the sequence $$ has a limit so let $$. Replacing $k$-decompositions with their fractional relaxations, one obtains the (polynomial time computable) fractional analogue $$ and corresponding fractional values $$ and $$. Our first main result is that for each $$ ${\displaystyle }$

u_{�f v} =

u^*_{�f v};. ${\displaystyle }$ Further, there is a polynomial time algorithm that produces a decomposition $L$ of a $k$-decomposable graph such that $$. A similar result holds when $F_k$ is the family of all tournaments on $k$ vertices and when $F_k$ is the family of all edge-colorings of $K_k$. We use these results to obtain new and improved bounds on several decomposition results. For example, we prove that every $n$-vertex tournament which is $3$-divisible has a triangle decomposition in which the number of directed triangles is less than $0.0222n^2(1+o(1))$ and that every $5$-decomposable $n$-vertex graph has a $5$-decomposition in which the fraction of cycles of length $5$ is $o_n(1)$.

Recommendations

• Fractional clique decompositions of dense graphs and hypergraphs
• Edge-decompositions of graphs with high minimum degree
• Fractional clique decompositions of dense graphs
• Fractional clique decompositions of dense partite graphs
• Edge-decompositions of graphs with high minimum degree

This page was built for publication: Vector clique decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236259)