Factoring complete graphs and hypergraphs into factors with few maximal cliques

Abstract

For integers $r,t\ge 2$ and $n\ge 1$ let $f_r(t,n)$ be the minimum, over all factorizations of the complete $r$-uniform hypergraph of order $n$ into $t$ factors $H_1,\dots ,H_t$, of ${\sum }_{i=1}^{t}c(H_i)$ where $c(H_i)$ is the number of maximal cliques in $H_i$. It is known that $f_2(2,n)=n+1$; in fact, if $G$ is a graph of order $n$, then $c(G)+c(\overline{G})\ge n+1$ with equality iff $\omega (G)+\alpha (G)=n+1$ where $\omega$ is the clique number and $\alpha$ the independence number. In this paper we investigate $f_r(t,n)$ when $r>2$ or $t>2$. We also characterize graphs $G$ of order $n$ with $c(G)+c(\overline{G})=n+2$.

22 pages