% 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}
