An exact upper bound for the minimum size of a path system that weakly separates a clique

Let $G$ be a graph. A path system of $G$ is a set of paths in $G$. A path system $\mathcal{P}$ of $G$ is weakly separating, or simply, separating, if for every pair of edges of $G$ there exists a path in $\mathcal{P}$ that contains exactly one of them. Let $f:G\rightarrow\mathbb{N}$ be the minimum size of a path system that separates $G$. We are interested in the problem of determining $f$ for complete graphs.

The study of general separating set systems was initiated by Rényi in the 1960s [8]. Various versions concerning the separation of edges by subgraphs were introduced around the 2000s by computer scientists who were seeking efficient ways to detect faulty links in networks [4, 5, 9, 11]. The problem of determining a tight upper bound for the size of separating path systems of graphs on $n$ vertices (i.e. determining $\min\{f(G):G\text{ is an $n$-vertex graph}\}$) has become very popular in the combinatorics community during the last decade.

Among the first to consider this problem were Falgas-Ravry, Kittiparson, Korándi, Letzter and Narayanan [2], who proved a bound of $O(n\log n)$ and conjectured one of $O(n)$. Letzter [6] came very close by proving that $O(n\log^{*}n)$ is sufficient. The conjecture was eventually settled by Bonamy, Botler, Dross, Naia and Skokan [1], who proved an upper bound of $19n$. They further conjectured that $(1+o(1))n$ is optimal.

Restricting the question to the class of complete graphs is an appropriate direction to follow, not only because of the reduced complexity but also because of the fact that complete graphs have the highest known lower bound for $f$ among all graph classes. It is therefore natural to suspect that they are extremal for this problem. Specifically, the lower bound $f(K_{n})\geq n-1$ is tight and easy to obtain [2]. As for the upper bound, owing to work by Fernandes, Oliveira Mota and Sanhueza-Matamala [3], it is known that

The authors of [3] employ hypergraph matching theory in their proof which allows them to prove their bound for all dense regular graphs. Our approach to the problem is very different, and more alike to that of Wickes [10]. Her work relies on generating paths (for a definition see below). Namely, Wickes showed that every complete graph on a prime number of vertices has a generating path, and that the set of all the rotations of a generating path is a separating path system. Hence, $f(K_{n})\leq n$ when $n$ is prime. She also proved that $f(K_{n})\leq n$ when $n-1$ is prime or when $n\leq 20$.

We give a similar upper bound for $f(K_{n})$ for all $n\in\mathbb{N}$.

In combination with the lower bound of $n-1$, our result nearly resolves the problem of the size of minimum separating path systems for complete graphs. Moreover, our proof is both short and entirely constructive, providing concrete and relatively easy to describe examples of separating path systems for all complete graphs.

In brief, we decompose $n$ into appropriate prime numbers $p_{k}$ and a small rest, and then apply Wicke’s construction to each of the $K_{p_{k}}$’s. Then begins the main work of our proof, which is to carefully modify the resulting path system so that it becomes separating and has the required number of paths.

A labelled clique is a complete graph $K_{n}$ together with a labelling of $V(K_{n})$ with numbers from an interval of the naturals of length $n$. The latter naturally induces on $V(K_{n})$ a cyclic ordering and a rotation action. Given a labelled clique $K_{n}$, we partition $E(K_{n})$ in types as follows: the type of an edge $\{x_{1},x_{2}\}$ is defined to be $\min\{z_{1},z_{2}\}$, where $z_{i}:=(x_{i}-x_{3-i})(\text{mod $n$})\in[\frac{n-1}{2}]$ for $i=1,2$. Edges of the same type will be called homotypical. It is also useful to define the clockwise distance of two homotypical edges contained in a labelled clique as the minimum order of a rotation that maps one to the other.

For our immediate purposes, it suffices to define a generating path $P$ of $K_{p}$, where $p$ is a prime number, as one that exhibits the following properties:

1. (GP1)

   $P$ contains exactly one edge of type $1$;

2. (GP2)

   $P$ contains exactly two edges of each other type;

3. (GP3)

   any two pairs of homotypical edges in $P$ have distinct clockwise distances.

From these properties it is also clear that in the path system generated by the rotations of $P$ each edge of type $1$ is contained in exactly one path, whereas every other edge is contained in exactly two paths.

In the following proof, we work under the convention that every path has a first and a last vertex (although which is which will often not be relevant). We denote $e(P,P^{\prime})$ the edge connecting the last vertex of $P$ to the first vertex of $P^{\prime}$.

Let $3\leq n=\sum_{k=1}^{m}p_{k}+b$ with $p_{k}$ primes. For brevity, let $s_{k}$ denote the partial sums of $\sum_{k=1}^{m}p_{k}$. It is a corollary of [7] that we can choose each $p_{k}$ so that $n-s_{k}\leq\frac{p_{k}-3}{2}$ and $b\in\{3,...,19\}$.

We define pairwise disjoint induced cliques of $K_{n}$ indexed by, and with sizes corresponding to, the terms of the above sum. We label the vertices of each clique $K_{p_{k}}$ using the interval $[s_{k-1}+1,s_{k}]$. We call these labelled cliques levels, and we say that an edge touches a level if its smaller end is contained in that level. Note that exactly the edges that are contained in a level have a type in it. Therefore, whenever we refer to the type of an edge, it will always be an edge contained in a level and we will always mean its type in that level.

Let

be a separating path system for $K_{b}$.

Let $P_{k}^{s_{k-1}+1}$ be a generating path for the clique $K_{p_{k}}$. Let

be the separating path system of $K_{p_{k}}$ generated by $P_{k}^{s_{k-1}+1}$. Let $s_{k-1}+i$ be the first vertex of $P_{k}^{s_{k-1}+i}$.

We construct a separating path system $\mathscr{Q}$ for $K_{n}$ as follows.

To begin, we note that each generating path $P_{k}^{s_{k-1}+1}$ defines a permutation $\sigma_{k}\in S_{\frac{p_{k}-1}{2}}$ that maps each number in $\{2,...,\frac{p_{k}-1}{2}\}$ to the clockwise distance in $K_{p_{k}}$ of the homotypical edges of $P_{k}^{s_{k-1}+1}$ that have it as their type, and maps $1$ to the unique number in $[\frac{p_{k}-1}{2}]$ that is not the clockwise distance in $K_{p_{k}}$ of any homotypical pair of edges in $P_{k}^{s_{k-1}+1}$. Based on this observation, for each $p_{k}$ we define an injection $\phi_{k}:\{s_{k}+1,...,n\}\rightarrow\{2,...,\frac{p_{k}-1}{2}\}$ in the following way. While there does not exist a cycle of $\sigma_{k}$ with at least as many elements distinct from $1$ as there are remaining undefined instances of $\phi_{k}$, we arbitrarily choose a cycle of $\sigma_{k}$ that does not contain $1$ and arbitrarily decide the preimages of all of its elements, avoiding $s_{k}+1$. Then, we choose a cycle of $\sigma_{k}$ with at least as many elements distinct from $1$ as there are remaining vertices in $\{s_{k}+1,...,n\}$ with undefined images under $\phi_{k}$, and we map all of these remaining vertices to consecutive elements of the chosen cycle distinct from $1$, starting with $s_{k}+1$. This concludes the definition of $\phi_{k}$.

For each path $P_{k}^{s_{k-1}+i}\in\mathcal{P}_{k}$ and each type $\phi_{k}(s_{k}+j)\in im(\phi_{k})$, we remove exactly one edge of type $\phi_{k}(s_{k}+j)$ in $P_{k}^{s_{k-1}+i}$, different for each $i$, and join the ends of that edge to $s_{k}+j$. For example, given an edge of type $\phi_{k}(s_{k}+j)$, say $\{s_{k-1}+x,s_{k-1}+(x+\phi_{k}(s_{k}+j)\text{(mod $p_{k}$))}\}$, that is contained in $P_{k}^{s_{k-1}+1}$, then in each $P_{k}^{s_{k-1}+i}$ we can apply the treatment described above to the edge $\{s_{k-1}+(x+i-1\text{(mod $p_{k}$)}),s_{k-1}+(x+i-1+\phi_{k}(s_{k}+j)\text{(mod $p_{k}$)})\}$. We name the resulting path $\mathbf{P_{k}^{s_{k-1}+i}}$, and define

It is worth noting that every path $\mathbf{P_{k}^{s_{k-1}+i}}\in\mathscr{P}_{k}$:

• (P1)

  has exactly one edge in level $k$ of each type in $im(\phi_{k})\cup\{1\}$, which appears in no other path of $\mathscr{P}_{k}$ - in particular, this implies that each such edge is contained in exactly one path in $\mathscr{P}_{k}$;

• (P2)

  has exactly two edges in level $k$ of each other type, which it inherits from $P_{k}^{s_{k-1}+i}$ - in particular, this implies that every such edge is contained in exactly two paths of $\mathscr{P}_{k}$;

• (P3)

  has exactly two edges incident to each vertex $s_{k}+j$, one of which it shares with $\mathbf{P_{k}^{s_{k-1}+(i+\phi_{k}(s_{k}+j)\text{(mod $p$)})}}$ and the other with $\mathbf{P_{k}^{s_{k-1}+(i-\phi_{k}(s_{k}+j)\text{(mod $p$)})}}$.

We also observe that, for each vertex $s_{k}+j$, there do not exist homotypical edges in any path of $\mathscr{P}_{k}$ that have clockwise distance $\phi_{k}(s_{k}+j)$ in $K_{p_{k}}$, since in every such path one edge of each such type has been substituted by a path of length $2$ passing through another vertex in $\{s_{k}+1,...,n\}$ as described above - we denote this property (P4). The only possible exception to (P4) is for the vertex $s_{k}+1$, if the last cycle of $\sigma_{k}$ that we picked in the process of defining $\phi_{k}$ does not lie entirely in $im(\phi_{k})$ and does not map $1$ to $\phi_{k}(s_{k}+1)$. In that case, every path in $\mathscr{P}_{k}$ contains two homotypical edges, of type say $c_{k}\notin im(\phi_{k})\cup\{1\}$, that have clockwise distance $\phi_{k}(s_{k}+1)$ in $K_{p_{k}}$.

We continue by constructing sets of paths

where $R_{k}^{s_{k}+j}$ contains all the edges of $K_{p_{k}}$ of type $\phi_{k}(s_{k}+j)$ but one. We also define a path $S_{k}$ that contains all the edges of type $1$ but one, and a path $T_{k}$ that contains all the edges of type $c_{k}$ but one. Specifically, we pick the one edge excluded by each path in $\mathcal{R}_{k}\cup\{S_{k},T_{k}\}$ as follows:

• (P5)

  for $\mathcal{R}_{k}\cup\{S_{k}\}$, we pick them from pairwise distinct paths of $\mathscr{P}_{k}$;

• (P6)

  for $T_{k}$, we pick the one that is at the same two paths of $\mathscr{P}_{k}$ as $e(R_{k}^{s_{k}+1},P_{k+1}^{s_{k}+1})$ (or $e(R_{m}^{s_{m}+1},\mathbf{B_{m+1}^{s_{m}+1}})$, if $k=m$), if such exists - otherwise we choose arbitrarily.

We may impose (P5) because each path of $\mathscr{P}_{k}$ has exactly one edge of each type in $im(\phi)\cup\{1\}$ and it is different from those of all other paths in $\mathscr{P}_{k}$, due to (P1). We may impose (P6) because each edge incident to $s_{k}+1$ in a path of $\mathscr{P}_{k}$, including $e(R_{k}^{s_{k}+1},P_{k+1}^{s_{k}+1})$ (or $e(R_{m}^{s_{m}+1},\mathbf{B_{m+1}^{s_{m}+1}})$), is contained in the same two paths of $\mathscr{P}_{k}$ as a different unique edge of type $c_{k}$, if $s_{k}+1$ is an exception to (P4), or as none of the edges of type $c_{k}$, if (P4) applies to $s_{k}+1$.

We then extend each path $R_{k}^{s_{k}+j}$ by the edge $e(R_{k}^{s_{k}+j},P_{k+1}^{s_{k}+j})$ if $k\leq m-1$ and $j\leq p_{k+1}$, or by the edge $e(R_{k}^{s_{k}+j},R_{k+1}^{s_{k}+j})$ if $k\leq m-1$ and $j\geq p_{k+1}+1$, or by the edge $e(R_{m}^{s_{m}+j},\mathbf{B_{m+1}^{s_{m}+j})}$ if $k=m$, to obtain a path $\mathbf{R_{k}^{s_{k}+j}}$. We define

For $k\leq m-1$ we also extend $S_{k}$ by $e(S_{k},S_{k+1})$ and $T_{k}$ by $e(T_{k},T_{k+1})$ to obtain paths $\mathbf{S_{k}}$ and $\mathbf{T_{k}}$, respectively. Exploiting the fact that each path has two ends, we impose that the starting vertex of $T_{k+1}$ be not $s_{k}+1$, i.e. $e(T_{k},T_{k+1})$ is not incident to $s_{k}+1$ (P7).

Finally, we define

where:

• •

  $\mathbf{S}$ is the union of all the paths $\mathbf{S_{k}}$;

• •

  $\mathbf{T}$ is the union of all the paths $\mathbf{T_{k}}$;

• •

  $\mathbf{Q^{\ell}}$ is the union of all the boldface paths of exponent $\ell$, i.e. $\mathbf{Q^{\ell}}$ is the union of all paths $\mathbf{R^{\ell}_{i}}$ that were defined, and of $\mathbf{P^{\ell}_{k}}$ or $\mathbf{B^{\ell}_{m+1}}$ if these were defined, where $k$ is the appropriate index.

The reader can check that $\mathscr{Q}$ is indeed a path system, as its elements are concatenations of pairwise internally disjoint paths. It remains to show that it is separating.

We begin by noting that $\mathbf{Q^{1}}\cup...\cup\mathbf{Q^{\ell}}$, where $\ell=s_{k}$, contains exactly the edges that touch one of the first $k$ levels. Therefore, edges that touch distinct levels are separated. Moreover, edges in level $m+1$ are separated by $\mathscr{B}$. On the other hand, all the edges that touch a level $k\leq m$ are contained in the paths of $\mathscr{Q}_{k}:=\mathscr{P}_{k}\cup\mathscr{R}_{k}\cup\{\mathbf{S_{k}},\mathbf{T_{k}}\}$. Moreover, any path $P\in\mathscr{Q}_{k}$ extends to a path $P\in\mathscr{Q}$ such that $P^{\prime}\cap\mathscr{Q}_{k}=P$. It is therefore sufficient to show that $\mathscr{Q}_{k}$ separates the edges that touch level $k$.

Let $e,e^{\prime}$ be two distinct edges that touch level $k$ but are not contained in it. Then the only paths that may contain them both are those of $\mathscr{P}_{k}$, since every other path of $\mathscr{Q}_{k}$ contains at most one such edge. So, suppose that $\mathbf{P_{k}^{s_{k-1}+i}}$ is a path containing both $e$ and $e^{\prime}$.

If $e$ and $e^{\prime}$ have a common greater end, say $s_{k}+j$, then by (P3) the only other path of $\mathscr{P}_{k}$ that contains, say, $e$ is $\mathbf{P_{k}^{s_{k-1}+(i-\phi_{k}(s_{k}+j)\text{(mod $p_{k}$)})}}$, and the only other path of $\mathscr{P}_{k}$ that contains $e^{\prime}$ is $\mathbf{P_{k}^{s_{k-1}+(i+\phi_{k}(s_{k}+j)\text{(mod $p_{k}$)})}}$. But these are distinct paths, since $2\phi_{k}(s_{k}+j)\neq 0\text{(mod $p_{k}$)}$. So $e$ and $e^{\prime}$ are separated.

If $e$ and $e^{\prime}$ have distinct greater ends, say $s_{k}+j_{1}$ and $s_{k}+j_{2}$, then again by (P3) the only other path of $\mathscr{P}_{k}$ that contains $e$ is $\mathbf{P_{k}^{s_{k-1}+(i\pm\phi_{k}(s_{k}+j_{1})\text{(mod $p_{k}$)})}}$, and the only other path of $\mathscr{P}_{k}$ that contains $e^{\prime}$ is $\mathbf{P_{k}^{s_{k-1}+(i\pm\phi_{k}(s_{k}+j_{2})\text{(mod $p_{k}$)})}}$. Again, since $\phi_{k}(s_{k}+j_{1})$ and $\phi_{k}(s_{k}+j_{2})$ are distinct elements of $\{2,...,\frac{p_{k}-1}{2}\}$, these two paths are distinct, separating $e$ and $e^{\prime}$.

Hence, every two edges that touch level $k$ but are not contained in it are separated.

Subsequently, let $e$ and $e^{\prime}$ both be contained in level $k$. If one of them is contained in one of the paths in $\mathscr{R}_{k}\cup\{\mathbf{S_{k}}\}$ and the other is not contained in the same path, then of course they are separated. For this to not happen, one of the following must occur.

It may be that $e$ and $e^{\prime}$ are both contained in the same path of $\mathscr{R}_{k}\cup\{\mathbf{S_{k}}\}$. But then they are homotypical, and their type is in $im(\phi_{k})\cup\{1\}$. By (P1), that means that each of $e$ and $e^{\prime}$ belongs to a different path of $\mathscr{P}_{k}$, so they are separated.

It may be that $e$ and $e^{\prime}$ are not contained in any of the paths in $\mathscr{R}_{k}\cup\{\mathbf{S_{k}}\}$ because their types are not in $im(\phi_{k})\cup\{1\}$. But then by (P2) each of them appears in exactly two paths of $\mathscr{P}_{k}$, corresponding to the two paths in which it appears in $\mathcal{P}_{k}$, therefore they are separated.

It may be that $e$ is the unique edge of some type in $im(\phi_{k})\cup\{1\}$ that is not contained in any paths in $\mathscr{R}_{k}\cup\{\mathbf{S_{k}}\}$. If the same holds for $e^{\prime}$, then, by (P5), $e$ and $e^{\prime}$ are still separated by a path in $\mathscr{P}_{k}$. If instead $e^{\prime}$ is of a type not in $im(\phi_{k})\cup\{1\}$, then by (P2) $e^{\prime}$ appears in two paths in $\mathscr{P}_{k}$ and by (P1) $e$ appears only in one, so again they are separated.

Therefore, every two edges contained in level $k$ are separated.

Finally, let $e$ be contained in level $k$ and let $e^{\prime}$ touch level $k$ but not be contained in it. Let $s_{k}+j$ be the greater end of $e^{\prime}$. Let $\mathbf{P_{k}^{s_{k-1}+i}}$ be a path of $\mathscr{P}_{k}$ containing $e^{\prime}$, and suppose that it also contains $e$. Then by (P3) and without loss of generality $e^{\prime}$ is also contained in $\mathbf{P_{k}^{s_{k-1}+(i+\phi_{k}(s_{k}+j)\text{(mod $p_{k}$)})}}$. If $j\neq 1$, then by (P4) there do not exist homotypical edges in any path of $\mathscr{P}_{k}$ that have clockwise distance $\phi_{k}(s_{k}+j)$ in $K_{p_{k}}$, so $e\notin\mathbf{P_{k}^{s_{k-1}+(i+\phi_{k}(s_{k}+j)\text{(mod $p_{k}$)})}}$ and the two edges are separated. The same holds if $j=1$ and either $s_{k}+1$ is not an exception to $\mathbf{(P4)}$ or $e$ is not of type $c_{k}$. If $j=1$, $e$ is of type $c_{k}$ and $e\in\mathbf{T_{k}}$, then again $e$ and $e^{\prime}$ are separated by $T_{k}$, since $e^{\prime}\notin\mathbf{T_{k}}$ due to (P7). Finally, if $j=1$, $s_{k}+1$ is an exception to $\mathbf{(P4)}$ and $e$ is the unique edge of type $c_{k}$ not in $\mathbf{T_{k}}$, then by (P6) either $e$ and $e^{\prime}$ are separated by a path in $\mathscr{P}_{k}$, or else $e^{\prime}\in\mathbf{R_{k}^{s_{k}+1}}$, so $e$ and $e^{\prime}$ are again separated.

This concludes the case analysis, and the proof.