% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
% Please remove all other commands that change parameters such as
% margins or pagesizes.
% only use standard LaTeX packages
% only include packages that you actually need
% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}
% we recommend the graphicx package for importing figures
\usepackage{graphicx}
% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins
% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% if needed include a line break (\\) at an appropriate place in the title
\title{\bf Improved Bounds for the Graham-Pollak Problem for Hypergraphs}
% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address
\author{Imre Leader\\
\small Department of Pure Mathematics\\[-0.8ex]
\small and Mathematical Statistics\\[-0.8ex]
\small University of Cambridge\\[-0.8ex]
\small Cambridge CB3 0WB, United Kingdom\\
\small\tt I.Leader@dpmms.cam.ac.uk\\
\and
Ta Sheng Tan\\
\small Institute of Mathematical Sciences\\[-0.8ex]
\small Faculty of Science\\[-0.8ex]
\small University of Malaya\\[-0.8ex]
\small 50603 Kuala Lumpur, Malaysia\\
\small\tt tstan@um.edu.my
}
% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}
\date{\dateline{Aug 7, 2017}{Dec 16, 2017}\\
\small Mathematics Subject Classifications: 05D05, 05C70}
\begin{document}
\maketitle
% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..." or "we show that...". Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.
\begin{abstract}
For a fixed $r$, let $f_r(n)$ denote the minimum number of complete $r$-partite $r$-graphs needed to partition the complete $r$-graph on $n$ vertices.
The Graham-Pollak theorem asserts that $f_2(n)=n-1$.
An easy construction shows that $f_r(n) \leq (1+o(1))\binom{n}{\lfloor r/2 \rfloor}$, and we write $c_r$ for the least number such that $f_r(n) \leq c_r (1+o(1))\binom{n}{\lfloor r/2 \rfloor}$.
It was known that $c_r < 1$ for each even $r \geq 4$, but this was not known for any odd value of $r$.
In this short note, we prove that $c_{295}<1$. Our method also shows that $c_r \rightarrow 0$, answering another open problem.
% keywords are optional
\bigskip\noindent \textbf{Keywords:} Hypergraph, Decomposition, Graham-Pollak
\end{abstract}
\section{Introduction}
The edge set of $K_n$, the complete graph on $n$ vertices, can be partitioned into $n-1$ complete bipartite subgraphs: this may be done in many ways, for example by taking $n-1$ stars centred at different vertices. Graham and Pollak~\cite{graham1,graham2} proved that the number $n-1$ cannot be decreased. Several other proofs of this result have been found, by Tverberg~\cite{tverberg}, Peck~\cite{peck}, and Vishwanathan~\cite{vishwanathan1,vishwanathan2}, among others.
Generalising this to hypergraphs, for $n\ge r\ge 1$, let $f_r(n)$ be the minimum number of complete $r$-partite $r$-graphs needed to partition the edge set of $K_n^{(r)}$, the complete $r$-uniform hypergraph on $n$ vertices
(i.e., the collection of all $r$-sets from an $n$-set).
Thus the Graham-Pollak theorem asserts that $f_2(n) = n-1$. For $r\ge 3$, an easy upper bound of $\binom{n-\lceil r/2\rceil}{\lfloor r/2\rfloor}$ may be obtained by generalising the star example above.
Indeed, for $r$ even, having ordered the vertices, consider the collection of $r$-sets whose $2nd, 4th, \ldots, rth$ vertices are fixed. This forms a complete $r$-partite $r$-graph, and the collection of all $\binom{n- r/2}{ r/2 }$ such is a partition of $K_n^{(r)}$.
For $r$ odd, we instead fix the $2nd, 4th, \ldots, (r-1)th$ vertices, yielding a partition into $\binom{n- (r+1)/2}{ (r-1)/2 }$ parts.
Alon~\cite{alon1} showed that $f_3(n) = n-2$. More generally, for each fixed $r\ge 1$, he showed that
\begin{equation*}
\frac{2}{\binom{2\lfloor r/2 \rfloor}{\lfloor r/2 \rfloor}}(1+o(1))\binom{n}{\lfloor r/2\rfloor}\le f_r(n)\le (1-o(1))\binom{n}{\lfloor r/2\rfloor},
\end{equation*}
where the upper bound follows from the construction above.
Writing $c_r$ for the least $c$ such that $f_r(n) \leq c (1+o(1))\binom{n}{\lfloor r/2 \rfloor}$, the above results assert that $c_2 = 1$, $c_3 = 1$, and $\frac{2}{\binom{2\lfloor r/2 \rfloor}{\lfloor r/2 \rfloor}} \le c_r \le 1$ for all $r$.
How do the $c_r$ behave?
Cioab\v{a}, K\"{u}ndgen and Verstra\"{e}te~\cite{cioaba1} gave an improvement (in a lower-order term) to Alon's lower bound, and Cioab\v{a} and Tait~\cite{cioaba2} showed that the construction above is not sharp in general, but Alon's asymptotic bounds (i.e., the above bounds on $c_r$) remained unchanged.
Recently, Leader, Mili\'{c}evi\'{c} and Tan~\cite{leader} showed that $c_r \leq \frac{14}{15}$ for each even $r \geq 4$.
However, they could not improve the bound of $c_r\le1$ for any odd $r$ -- the point being that the construction above is better for $r$ odd than for $r$ even (the exponent of $n$ is $(r-1)/2$ for $r$ odd versus $r/2$ for $r$ even), and so is harder to improve.
In this note, we give a simple argument to show that $c_{295}<1$. Our method also shows that $c_r \rightarrow 0$, answering another question from \cite{leader}.
It would be interesting to know what happens for smaller odd values of $r$: for example, is $c_5<1$?
Determining the precise value of $c_4$ (i.e., the asymptotic behaviour of $f_4(n)$) would also be of great interest, as would determining the decay rate of the $c_r$. See ~\cite{leader} for several related questions and conjectures.
\section{Main Result}
The motivation for our proof is as follows.
The key to the approach used in $\cite{leader}$ in proving $c_r<1$ for each even $r\ge 4$ was to investigate the minimum number of products of complete bipartite graphs, that is, sets of the form $E(K_{a,b})\times E(K_{c,d})$, needed to partition the set $E(K_n)\times E(K_n)$.
Writing $g(n)$ for this minimum value, it is trivial that $g(n)\le (n-1)^2$, by taking the products of the complete bipartite graphs appearing in a decomposition of $K_n$ into $n-1$ complete bipartite graphs.
It was shown in \cite{leader} that
\begin{equation}\label{eq:main}
g(n)\le \left(\frac{14}{15}+o(1)\right)n^2.
\end{equation}
It turned out that this upper bound on $g(n)$ was enough (via an iterative construction) to bound $c_r$ below 1 for each even $r\ge 4$.
Now, as remarked above, for $r$ odd the construction in the Introduction is much better than for $r$ even. In fact, while there are many iterative ways to redo the construction when $r$ is even, passing from $n/2$ to $n$, these fail when $r$ is odd: it turns out that an extra factor is introduced at each stage.
However, rather unexpectedly, we will see that (at least if $r$ is large) if we partition into \emph{many} pieces, instead of just two pieces, then the gain we obtain from the $14/15$ improvement in $g(n)$ outweighs the loss arising from this extra factor -- even though this extra factor grows as the number of pieces grows.
A \emph{minimal decomposition} of a complete $r$-partite $r$-graph $K_n^{(r)}$ is a partition of the edge set into $f_r(n)$ complete $r$-partite $r$-graphs.
A \emph{block} is a product of the edge sets of two complete bipartite graphs.
Similarly, a \emph{minimal decomposition} of $E(K_n)\times E(K_n)$ is a partition of $E(K_n)\times E(K_n)$ into $g(n)$ blocks.
Finally, for a set $V$, we may write $E(V)$ to denote the edge set of the complete graph on $V$, that is, the set of all 2-subsets of $V$.
\begin{theorem}\label{theorem_main}
Let $r=2d+1$ be fixed. Then for each $k$ there exists $\epsilon_k$, with $\epsilon_k \rightarrow 0$ as $k\rightarrow \infty$, such that for all $n$ we have
\begin{equation*}
f_r(kn) \le \left(\left(\frac{14}{15}\right)^{\left\lfloor\frac{d}{2}\right\rfloor}+d\left(\frac{14}{15}\right)^{\left\lfloor\frac{d-1}{2}\right\rfloor}+\epsilon_k\right)(1+o(1))\binom{kn}{d}.
\end{equation*}
(Here the $o(1)$ term is as $n\rightarrow \infty$, with $k$ and $d$ fixed.)
\end{theorem}
\begin{proof}
In order to decompose the edge set of $K_{kn}^{(r)}$, we start by splitting the $kn$ vertices into $k$ equal parts, say $V\left(K_{kn}^{(r)}\right) = V_1\cup V_2\cup \cdots \cup V_k$, where $|V_i|= n$ for each $i$.
We consider the $r$-edges based on their intersection sizes with the $k$ vertex classes.
For each partition of $r$ into positive integers $r_1+r_2+\cdots+r_l$ with $r_1\le r_2\le \cdots \le r_l$ and for each collection of $l$ vertex classes $V_{i_1}, V_{i_2}, \ldots, V_{i_l}$, the set of $r$-edges $e$ with $|e\cap V_{i_j}| = r_j$ for all $j$ can be decomposed into $f_{r_1}(n)f_{r_2}(n)\cdots f_{r_l}(n)$ complete $r$-partite $r$-graphs: take a complete $r_j$-partite $r_j$-graph from a minimal decomposition of $K_n^{(r_j)}$ for each $j$, and form a complete $r$-partite $r$-graph by taking the product of them.
Note that if at least three values of the $r_j$ are odd, then $f_{r_1}(n)f_{r_2}(n)\cdots f_{r_l}(n) = O(n^{d-1})$, as $f_{s}(n)\le \binom{n}{\lfloor s/2\rfloor}$ for any $s$.
So the set of $r$-edges $e$ with $|e\cap V_i|$ is odd for at least three distinct $V_i$ can be decomposed into $Cn^{d-1}$ complete $r$-partite $r$-graphs, for some constant $C$ depending on $d$ and $k$.
Let $C'$ be the number of partitions of $r$ into at most $d-1$ positive integers where exactly one of them is odd. Then we observe that the set of $r$-edges $e$ such that $e$ intersects with at most $d-1$ vertex classes and $|e\cap V_i|$ is odd for exactly one $V_i$ can be decomposed into at most $C'k^{d-1}n^{d}$ complete $r$-partite $r$-graphs.
We are now only left with two partitions of $r$: $r=1+2+2+\cdots+2$ and $r=2+2+\cdots+2+3$.
The first case corresponds to the set of $r$-edges with $r_1=1, r_2=\cdots=r_{d+1}=2$.
For each of the $\binom{k}{d}$ collections of $d$ vertex classes $V_{i_1},V_{i_2},\ldots,V_{i_d}$, we claim that the set of $r$-edges $\{e:|e\cap V_{i_j}|=2, j=1,2,\ldots,d\}$ can be decomposed into $g(n)^{ d/2 }$ or $ng(n)^{(d-1)/2}$ complete $r$-partite $r$-graphs, depending on whether $d$ is even or odd.
This is done by pairing up the $V_{i_j}$s (or all but one of the $V_{i_j}$s if $d$ is odd), and forming complete $r$-partite $r$-graphs using products of blocks in a minimal decomposition of $E(K_n)\times E(K_n)$.
[For example, for $d=4$, we would take a decomposition of $E(V_{i_1})\times E(V_{i_2})$ into blocks $E_x \times F_x, 1\le x\le g(n)$, and similarly a decomposition of $E(V_{i_3})\times E(V_{i_4})$ into blocks $G_x \times H_x, 1\le x\le g(n)$, and now the set of all $9$-edges $e$ with $|e\cap V_{i_j}| = 2$ for all $1\le j\le 4$ may be decomposed into $g(n)^2$ complete 9-partite 9-graphs by taking the $E_x\times F_x \times G_y\times H_y \times (V_{i_1}\cup V_{i_2}\cup V_{i_3}\cup V_{i_4})^c$ for $1\le x,y\le g(n)$.]
Finally, the second case corresponds to the set of $r$-edges with $r_1=r_2=\cdots=r_{d-1} = 2, r_{d} = 3$. These can be decomposed in a similar fashion. Indeed, for each collection of $d$ vertex classes $V_{i_1},V_{i_2},\ldots,V_{i_d}$, the set of $r$-edges $\{e:|e\cap V_{i_d}|=3\mbox{ and } |e\cap V_{i_j}|=2, j=1,2,\ldots,d-1\}$ can be decomposed into $n^2g(n)^{(d-2)/2}$ or $ng(n)^{(d-1)/2}$ complete $r$-partite $r$-graphs, depending on whether $d$ is even or odd. There are $d\binom{k}{d}$ such sets of $r$-edges.
Combining the above and the bound on $g(n)$ given in inequality \eqref{eq:main}, we have
\begin{align*}
f_r(kn) &\le
\begin{cases}
\binom{k}{d}g(n)^{\frac{d}{2}} + d\binom{k}{d}n^2g(n)^{\frac{d-2}{2}} +C'k^{d-1}n^{d} +Cn^{d-1} &\quad\mbox{(if $d$ even)}\\
\binom{k}{d}ng(n)^{\frac{d-1}{2}} + d\binom{k}{d}ng(n)^{\frac{d-1}{2}} +C'k^{d-1}n^{d} +Cn^{d-1} &\quad\mbox{(if $d$ odd)}
\end{cases}\\
&\le \binom{k}{d}\left(\frac{14}{15}\right)^{\left\lfloor\frac{d}{2}\right\rfloor}n^d + d\binom{k}{d}\left(\frac{14}{15}\right)^{\left\lfloor\frac{d-1}{2}\right\rfloor}n^d + C'k^{d-1}n^d + o(n^d)\\
&\le \left(\left(\frac{14}{15}\right)^{\left\lfloor\frac{d}{2}\right\rfloor} + d\left(\frac{14}{15}\right)^{\left\lfloor\frac{d-1}{2}\right\rfloor} + \frac{d!C'}{k}\right)\binom{k}{d}n^d + o(n^d)\\
& \le \left(\left(\frac{14}{15}\right)^{\left\lfloor\frac{d}{2}\right\rfloor}+d\left(\frac{14}{15}\right)^{\left\lfloor\frac{d-1}{2}\right\rfloor}+\epsilon_k\right)(1+o(1))\binom{kn}{d}.
\end{align*}
\end{proof}
\begin{corollary}
Let $r \ge 295$ be a fixed odd number. Then there exists $c< 1$ such that $$f_r(n) \le c(1+o(1))\binom{n}{\lfloor r/2 \rfloor}.$$
\end{corollary}
\begin{proof}
As above, write $r=2d+1$. It is straightforward to check that for $d\ge 147$ we have $\left(\frac{14}{15}\right)^{\left\lfloor\frac{d}{2}\right\rfloor}+d\left(\frac{14}{15}\right)^{\left\lfloor\frac{d-1}{2}\right\rfloor} <1$.
Choosing $k$ such that $$c = \left(\frac{14}{15}\right)^{\left\lfloor\frac{d}{2}\right\rfloor}+d\left(\frac{14}{15}\right)^{\left\lfloor\frac{d-1}{2}\right\rfloor} + \epsilon_k < 1,$$
we have $f_r(kn) \le c(1+o(1))\binom{kn}{d}$ for all $n$.
However since the function $f_r(n)$ is monotone in $n$, and $k$ is constant as $n$ varies, it follows that $f_r(n) \le c(1+o(1))\binom{n}{d}$ for all $n$.
\end{proof}
From Theorem~\ref{theorem_main}, we have $$c_{2d+1} \le \left(\frac{14}{15}\right)^{\left\lfloor\frac{d}{2}\right\rfloor}+d\left(\frac{14}{15}\right)^{\left\lfloor\frac{d-1}{2}\right\rfloor}$$ for every $d$.
Also, it is easy to see that $c_{2d}\le c_{2d+1}$. Indeed, by excluding a vertex in the complete $(2d+1)$-graph on $n+1$ vertices, the complete $(2d)$-partite $(2d)$-graphs induced from the complete $(2d+1)$-partite $(2d+1)$-graphs in a minimal decomposition of $K_{n+1}^{(2d+1)}$ form a decomposition of $K_{n}^{(2d)}$, implying that $f_{2d}(n)\le f_{2d+1}(n+1)$. Hence we have the following.
\begin{corollary}\label{cor_cr}
The numbers $c_r$ satisfy
$$ c_r \le \frac{r}{2}\left(\frac{14}{15}\right)^{r/4}+o(1).$$
(Here the $o(1)$ term is as $r\rightarrow \infty$.)
\end{corollary}
Corollary~\ref{cor_cr} implies that $c_r\rightarrow 0$ as $r\rightarrow \infty$, proving Conjecture 16 in \cite{leader}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file
\begin{thebibliography}{10}
\bibitem{alon1} N. Alon. \newblock Decomposition of the complete $r$-graph into complete $r$-partite $r$-graphs. \newblock {\em Graphs and Combin.}, 2:95--100, 1986.
\bibitem{cioaba1} S. M. Cioab\v{a}, A. K\"{u}ndgen, and J. Verstra\"{e}te. \newblock On decompositions of complete hypergraphs. \newblock {\em J. Combin. Theory Ser. A}, 116:1232--1234, 2009.
\bibitem{cioaba2} S. M. Cioab\v{a} and M. Tait. \newblock Variations on a theme of Graham and Pollak. \newblock {\em Discrete Math.}, 313:665--676, 2013.
\bibitem{graham1} R. L. Graham and H. O. Pollak. \newblock On the addressing problem for loop switching. \newblock {\em Bell System Tech. J.}, 50(8):2495--2519, 1971.
\bibitem{graham2} R. L. Graham and H. O. Pollak. \newblock On embedding graphs in squashed cubes. \newblock In {\em Graph Theory and Applications}, volume 303 of {\em Lecture Notes in Math.}, pages 99--110. Springer, 1972.
\bibitem{leader} I. Leader, L. Mili\'{c}evi\'{c}, and T. S. Tan. \newblock Decomposing the complete $r$-graph. \newblock {\em J. Combin. Theory Ser. A}, 154:21--31, 2018.
\bibitem{peck} G. Peck. \newblock A new proof of a theorem of Graham and Pollak. \newblock {\em Discrete Math.}, 49:327--328, 1984.
\bibitem{tverberg} H. Tverberg. \newblock On the decomposition of $K_n$ into complete bipartite graphs. \newblock {\em J. Graph Theory}, 6:493--494, 1982.
\bibitem{vishwanathan1} S. Vishwanathan. \newblock A polynomial space proof of the Graham-Pollak theorem. \newblock {\em J. Combin. Theory Ser. A}, 115:674--676, 2008.
\bibitem{vishwanathan2} S. Vishwanathan. \newblock A counting proof of the Graham-Pollak theorem. \newblock {\em Discrete Math.}, 313(6):765--766, 2013.
\end{thebibliography}
\end{document}