Jean-Christophe Godin^a , Remi Grisot ´ b , Olivier Togni^c

godinjeanchri@yahoo.fr, grisot.remi@gmail.com, olivier.togni@ube.fr

We consider the following list coloring with separation problem: Given a graph G and integers a, b, find the largest integer c such that for any list assignment L of G with |L(v)| = a for any vertex v and |L(u) ∩ L(v)| ≤ c for any edge uv of G, there exists an assignment φ of sets of integers to the vertices of G such that φ(u) ⊂ L(u) and |φ(v)| = b for any vertex u and φ(u) ∩ φ(v) = ∅ for any edge uv. Such a value of c is called the separation number of (G, a, b). Using a special partition of a set of lists for which we obtain an improved version of Poincare's crible, we determine the ´ separation number of the complete graph Kⁿ for some values of a, b and n, and prove bounds for the remaining values.

Keywords: graph, coloring, choosability, separation, set system

Mathematics Subject Classification : 05C15

DOI: 10.5614/ejgta.2025.13.1.5

1. Introduction

Let a, b, c be integers and let G be a graph. A a-list assignment L of G is a function which associates to each vertex a set of a integers. The list assignment L is c-separating if for any uv ∈ E(G), |L(u) ∩ L(v)| ≤ c. The graph G is (a, b, c)-choosable if for any c-separating a-list assignment L, there exists an (L, b)-coloring of G, i.e. a coloring function φ on the vertices of G

Received: 20 July 2020, Revised: 2 February 2025, Accepted: 19 February 2025.

a Institut de Mathematiques de Toulon, Universit ´ e de Toulon, France ´

^bLEAT, Universite C´ ote d'Azur ˆ

^cLIB, Universite Bourgogne Europe, France ´

that assigns to each vertex v a subset of b elements from L(v) in such a way that φ(u) ∩ φ(v) = ∅ for any uv ∈ E(G).

The list coloring problem with restrictions on the list intersections has been introduced by Kratochv´ıl, Tuza and Voigt [14]. Notice that Kratochv´ıl et al. [14, 15] defined (a, b, c)-choosability a bit differently, requiring for a c-separating a-list assignment L that the lists of two adjacent vertices u and v satisfy |L(u) ∩ L(v)| ≤ a − c. Among the first results on the topic, a complexity dichotomy was presented [14] and general properties given [15]. These first papers were followed by a series of papers considering choosability with separation of planar graphs, mainly for the case b = 1 [3, 4, 5, 6, 7, 13, 18]. While the fact that planar graphs are (4, 1, 2)-choosable was proved very recently [19], a still open question is whether all planar graphs are (3, 1, 1)-choosable or not. Other recent papers concern balanced complete multipartite graphs and k-uniform hypergraphs (for the case b = 1) [11]; bipartite graphs (for the case b = c = 1) [10]; a study with an extended separation condition [16], and cycles and outerplanar graphs for arbitrary b [12]. Many other variations of list coloring have been introduced, for instance flexibility [9] and total weight choosability [17].

In this paper, we concentrate on choosability with separation of complete graphs. As a (a, b, c) choosable graph is also (a, b, c′ )-choosable for any c ′ < c, our aim is to determine, for given a, b, a ≥ b, the largest c such that G is (a, b, c)-choosable. Following our previous work on cycles [12], we define the (list) separation number sep(G, a, b) of G as

\[sep(G, a, b) = max\{c : G \text{ is } (a, b, c)\text{-choosable}\}.\]

Notice that we have 0 ≤ sep(G, a, b) ≤ a for any graph G and a ≥ b, hence this parameter is well defined.

In our setting, we know that any planar graph G satisfies sep(G, 5, 1) = 5 (Thomassen's Theorem), sep(G, 4, 1) ≥ 2 [19] ; but we do not know if sep(G, 3, 1) ≥ 1 holds for all planar graphs G. For the complete graph, Kratochv´ıl et al. [15] proved that sep(Kn, ⌊ p n − 11/4 + 3/2⌋, 1) ≥ 1. Moreover, the separation number of the cycle is determined and bounds are given for catuses and outerplanar graphs [12].

The following Hall-type condition that we call the amplitude condition is necessary for a graph G to be (L, b)-colorable:

\[\forall H \subset G, \sum_{k \in C} \alpha(H, L, k) \ge b|V(H)|,\]

where C = S ^v∈^V (H) L(v) and α(H, L, k) is the independence number of the subgraph of H induced by the vertices containing k in their color list. Notice that H can be restricted to be a connected induced subgraph of G. As shown by Cropper et al. [8] (in the more general context of weighted list coloring), this condition is also sufficient when the graph is a complete graph or a path (or some other specific graphs).

For a list assignment L on a graph G of order n with vertex set V (G) = {v1, v2, . . . , vn} and for S ⊂ [1, n], we write ΣS(L) = P ^k∈^C α(H, L, k), where H is the subgraph of G induced by {vⁱ , i ∈ S}.

Remark that if G is a complete graph, then α(H, L, k) = 1 for any k. Hence the amplitude

condition for Kⁿ becomes

\[\forall S \subset [1, n], \Sigma_S(L) = |\cup_{i \in S} L(x_i)| \ge b|S| \tag{1}\]

Example 1. For the complete graph K⁴ with vertex set {v1, v2, v3, v4}, let L be the 3-separating 5-list assignment defined by:

\[L(v_1) = \{1, 2, 3, 4, 5\}, L(v_2) = \{1, 2, 3, 6, 7\}, L(v_3) = \{3, 4, 6, 7, 8\}, \text{ and } L(v_4) = \{4, 6, 8, 9, 10\}.\] We have \(L(v_1) \cup L(v_2) \cup L(v_3) = \{1, 2, 3, 4, 5, 6, 7, 8\}, \text{ hence } \Sigma_{\{1,2,3\}}(L) = |\{1, 2, 3, 4, 5, 6, 7, 8\}| = 8.\) Therefore \(K_4\) is not \((L, 3)\)-colorable since \(\Sigma_{\{1,2,3\}}(L) = 8 < 3b = 9\). (Note that we also have \(\Sigma_{[1,4]}(L) = 10 < 4b = 12\) in this case.)

For the separation number of the complete graph, the following properties are easy to prove: Property 1. Let a, b, n be integers. Then

• for fixed b, n, the function sep(Kn, a, b) is increasing with a;
• for fixed a, b, the function sep(Kn, a, b) is decreasing with n.

Moreover, we observed (and will prove it in the case b ≤ a < 2b and (n − 1)b ≤ a < nb) that for any a, b, n, sep(Kn, a + 1, b) ≤ sep(Kn, a, b) + 2.

In Section 2, we introduce proper intersections of set systems and show some of their properties and use them to partition the lists of colors of the vertices of Kn, allowing to simplify the computations. In Section 3, we propose a general coloring algorithm and two special types of list assignments with nice properties that will be used mainly for finding good counter-examples. Then in Section 4, we determine bounds and exact values for the separation number of the complete graph Kn, depending on a, b and n, and finish with a conjecture. The algebra that allowed us to find the counter examples of Section 4 is given in Appendix Appendix A.

2. Algebraic preliminaries on set systems intersections

2.1. Proper intersections and Poincare's crible improvement ´

Let n ≥ 1 be an integer and [n] = [1, n]. For sets of elements A1, A2, . . . , An, we define the following: For any i ≥ 1 and Sⁱ = {α1, α2, . . . , αi} ⊂ [n], the proper intersection Ip(Si) of A^α1 , A^α2 , . . . , A^αi is given by

\[I_{\mathsf{p}}(S_i) = \left(\bigcap_{k=1}^i A_{\alpha_k}\right) \setminus \left(\bigcup_{\beta \in [n] \setminus S_i} A_{\beta}\right).\]

Notice that for any set S ∈ [n], the whole n sets Aⁱ are present in the formulae of the proper intersection of S. For example, for n = 5, Ip({1}) = A¹ \ (A² ∪ A³ ∪ A⁴ ∪ A5) ; Ip({2, 3}) = (A² ∩ A3) \ (A¹ ∪ A⁴ ∪ A5); Ip({1, 2, 5}) = (A¹ ∩ A² ∩ A5) \ (A³ ∪ A4); Ip({2, 3, 4, 5}) = (A² ∩ A³ ∩ A⁴ ∩ A5) \ A¹ and Ip({1, 2, 3, 4, 5}) = A¹ ∩ A² ∩ A³ ∩ A⁴ ∩ A5.

Then the classical intersection can be described in terms of proper intersections:

List coloring with separation of the complete graph | J.-C. Godin, R. Grisot and O. Togni.

Property 2. For any \(S \subset [n]\),

\[\bigcap_{i \in S} A_i = \bigcup_{S \subset S' \subset [n]} I_p(S').\]

Proof. The proof is by double inclusion. First, by construction, For any \(S'\supset S\), any x in \(I_p(S')\) is also an element of \(\cap_{i\in S}A_i\). Next, if \(x\in \cap_{i\in S}A_i\), then either \(x\in I_p(S)\) and we are done or \(x\not\in I_p(S)\). In this latter case, let \(\overline{S}\) be the set of indices j of \([n]\setminus S\) for which \(x\in A_j\). Then, by construction, we have \(x\in I_p(S')\), for \(S'=S\cup \overline{S}\).

Thanks to this property, we obtain the fact that the proper intersections form a partition of \(\bigcup_{i=1}^{n} A_i\).

Property 3. For any \(S, S' \subset [n]\) such that \(S \neq S'\), we have

\[I_p(S) \cap I_p(S') = \emptyset.\]

Proof. At least one of S-S' or S'-S is non empty. Let us say S-S' is not empty and let \(s \in S-S'\). Let \(x \in I_p(S) \cap I_p(S')\). Then \(x \in A_s\), but \(x \in I_p(S')\) and \(s \notin S'\). Hence \(x \notin A_s\), a contradiction and therefore the intersection is empty.

We thus have the following à-la-Poincaré result:

Theorem 2.1.

\[\bigcup_{i=1}^{n} A_i = \bigcup_{S \subset [n]. S \neq \emptyset} I_p(S).\]

Proof. By Property 2 for |S|=1, we have \(A_i=\bigcup_{S'\subset [n]\setminus\{i\}}I_p(\{i\}\cup S')\). Therefore \(\bigcup_{i=1}^nA_i=\bigcup_{i=1}^n\bigcup_{S'\subset [1,n]\setminus\{i\}}I_p(\{i\}\cup S')=\bigcup_{S\subset [n],S\neq\emptyset}I_p(S)\).

By Property 3 and Theorem 2.1, we obtain the following crible which can be seen as an improvment of Poincaré's crible as we only do additions (compared to Poincaré's crible where additions and substractions alternate):

Corollary 2.1.

\[\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{S \subset [n], S \neq \emptyset} |I_p(S)|.\]

2.2. List assignments of \(K_n\) and proper intersections

We will use proper intersections on list assignments of \(K_n\). Let \(V(K_n) = [n]\). For a list assignment L of \(K_n\), we let \(A_i = L(i)\), for \(1 \le i \le n\).

In a basic way, L is a set of n lists of size a. Using proper intersection tools from the previous subsection, the list assignment L can now be represented by the vector of proper intersections cardinals \(\mathbf{V}(L)\) of dimension \(2^n - 1\) (ordered by set inclusion and alphanumeric order).

Then we have

\[\forall i \in [n] \sum_{S \subset [n], i \in S} |I_{\mathsf{p}}(S)| = |L(i)|. \tag{2}\]

List coloring with separation of the complete graph | J.-C. Godin, R. Grisot and O. Togni.

And the cardinality of the intersection between two lists is given by

\[\forall i, j \in [n], i \neq j, \sum_{S \subset [n], i, j \in S} |I_p(S)| = |L(i) \cap L(j)|.\] (3)

Moreover, thanks to Corollary 2.1, the total amplitude of L is given by

\[\Sigma_{[n]}(L) = \sum_{S \subset [n]} |I_{\mathsf{p}}(S)|. \tag{4}\]

Example 2. For the complete graph K⁴ and the list assignment L defined in Example 1, we have: Ip({1}) = {5}, Ip({4}) = {9, 10}, Ip({1, 2}) = {1, 2}, Ip({2, 3}) = {7}, Ip({3, 4}) = {8}, Ip({1, 2, 3}) = {3}, Ip({1, 3, 4}) = {4}, and Ip({2, 3, 4}) = {6}. Hence the vector V(L) = (1, 0, 0, 2, 2, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0).

Consequently, from these equations, we obtain an ILP-formulation of the problem of finding smallest counter examples (c-separating a-list assignments L of Kⁿ for which no (L, b)-coloring exists): For S ⊂ [n], we consider the variable x^S = |Ip(S)|. Then the goal is to minimize c subject to the constraints:

\[\forall i \in [n], \sum_{S \subset [n], i \in S} x_S = a, \tag{5}\]

\[\forall i, j \in [n], i \neq j, \sum_{S \subset [n], i, j \in S} x_S \le c, \tag{6}\]

and

\[\sum_{S \subset [n]} x_S < nb.\]

This formulation allows to use ILP-solvers to help us finding counter-examples.

Remark 2.1. Assuming that the colors are taken from the set {1, . . . , na} (this is always possible, up to a color renumbering), we can count the number of different list assignments associated to the same vector of proper intersections V(L): Considering any ordering S1, S2, . . . , S2n−¹ of the non-empty subsets of [n], this number of list assignments is given by

\[\prod_{i=1}^{2^n-1} \binom{na - \sum_{j < i} |I_{\mathsf{p}}(S_j)|}{|I_{\mathsf{p}}(S_j)|} = \frac{(na)!}{(na - \sum_i |I_{\mathsf{p}}(S_i)|)! (\prod_i |I_{\mathsf{p}}(S_i)|!)}.\]

For instance, if all proper intersections are equal to zero except Ip([n]) = a, then we obtain na a lists.

2.3. Counting list assignments up to proper intersection equivalence

In order to compute the gain of working with proper intersections instead of list assignments, we are now going to count the total number of a-list assignments up to proper intersection equivalence. Let L(n, a) be the set of all a-list assignments on n vertices up to proper intersection.

The cardinal of \(\mathcal{L}(n, a)\) can be compared with the total number of a-list assignments on na colors, which is \(\binom{na}{a}^n\).

For n=2, it is easy to see that there are only a+1 different lists up to proper intersections, hence \(|\mathcal{L}(2,a)|=a+1\). We define \(\mathcal{L}(n,a,[n]=0)\) as the subset of \(\mathcal{L}(n,a)\) for which \(I_{\mathsf{p}}([n])=\emptyset\) and \(\mathcal{L}(n,a,[n]>0)\) as the subset of \(\mathcal{L}(n,a)\) for which \(|I_{\mathsf{p}}([n])|>0\).

Lemma 2.1. For integers \(a \ge 1\), \(n \ge 1\), we have:

\[|\mathcal{L}(n,a)| = |\mathcal{L}(n,a-1)| + |\mathcal{L}(n,a,[n]=0)|.\]

Proof. It is easily seen that \(\mathcal{L}(n,a) = \mathcal{L}(n,a,[n]>0) \cup \mathcal{L}(n,a,[n]=0)\). Now, note that there is a trivial isomorphism between lists of \(\mathcal{L}(n,a,[n]>0)\) and that of \(\mathcal{L}(n,a-1)\). To see this, represent each list by the vector of the cardinals of their proper intersections, ordered by the size. Then since the last element of each vector is positive, its value can be decreased by one, obtaining a vector corresponding with a list assignment of \(\mathcal{L}(n,a-1)\).

Remark that any element of \(\mathcal{L}(n, a)\) must satisfy Equation 5 for each vertex and reciprocally any solution of this set of n equations gives a list assignment \(\mathcal{L}(n, a)\). Hence the set of all solutions is a subspace of dimension \(2^n - 1 - n\) of a vectorial space of this equation set.

Lemma 2.2. For all \(S = \{a_1, a_2, \dots, a_i\} \subset [n], |S| \geq 2\), the vectors \(\mathbf{v}_S = \mathbf{e}_S - \sum_{j=1}^i \mathbf{e}_{a_j}\) form a canonical base of \(\mathcal{L}(n, a)\).

Proof. As we have \(2^n-1\) proper intersections, then the space is of dimension \(2^n-1\). But we have n linear equations (Equation 5) and since they are linearly independent, thus \(\mathcal{L}(n,a)\) is of dimension \(2^n-1-n\). It then suffices to prove that the family of \(\mathbf{v}_S\) is free. For any \(S\subset [n], |S|\geq 2\), let \(\alpha_S\), such that \(\sum \alpha_S \mathbf{v}_S = \mathbf{0}\). We have \(\sum \alpha_S \mathbf{v}_S = \sum_{i=1}^n \beta_i \mathbf{e}_i + \sum_{|S|\geq 2} \alpha_S \mathbf{e}_S = \mathbf{0}\). As the \(\mathbf{e}_S\) are vectors of the canonical base, then \(\alpha_S = 0\) for every S. Hence the family is free.

There exists a trivial solution to the set of equations, it is the list assignment with vector \(\mathbf{T} = (a, a, \ldots, a, 0, \ldots, 0)\) with n values equal to a. Then any list assignment solution can be written as the trivial solution plus a linear combination of these base vectors \(\mathbf{e}_S\). Hence a list assignment solution can be identified by a linear sum of base vectors. We therefore only have to work on linear sums of base vectors. But, as the entries of a solution have to be non negative, we only have a finite number of solutions. We define the set of list assignments \(\mathcal{L}(n,=a)\) as the set of list assignments such that there exists some \(i \in [n]\) for which the sum of coefficients \(\alpha_S\) over all S containing i in the linear combination is equal to a in the vectorial representation (i.e., such that \(I_p(\{i\}) = \emptyset\)) and for which \(I_p([n]) = \emptyset\).

Lemma 2.3.

\[|\mathcal{L}(n, a, [n] = 0)| = |\mathcal{L}(n, a - 1, [n] = 0)| + |\mathcal{L}(n, = a)|.\]

Proof. The set \(\mathcal{L}(n, a, [n] = 0)\) trivially decomposes into the set \(\mathcal{A}\) of list assignments for which all the first n entries of the vector are strictly positive and the set of which there is at least a zero in the first n entries of the vector, i.e., \(\mathcal{L}(n, = a)\). But there is a natural bijection between \(\mathcal{A}\) and \(\mathcal{L}(n, a - 1, [n] = 0)\), hence the recursion formulae.

Lemma 2.4.

\[|\mathcal{L}(3,=a)| = \begin{cases} 3/4a^2 + 3/2a + 1, & a \text{ even,} \\ 3/4a^2 + 3/2a + 3/4, & a \text{ odd.} \end{cases}\]

Proof. For n = 3, we have only 3 vectors: S = (1, 2),(1, 3), and (2, 3). Hence any solution can be represented by a triplet of vectors (α1, α2, α3). Starting from (a, 0, 0), we count the triplets by equivalence classes such that the first coefficient is maximum, the second one is greater than or equal to the third one and then we count the number of elements in the class of equivalence. We then have three cases: if the three numbers are different then there are 3! = 6 different combinations; if exactly two numbers are different then we have 3 combinations and only one if the three numbers are all identical. Hence each solution is of the form (a − x, x, y) with 0 ≤ x ≤ a/2 and y ≤ x. Therefore, we obtain the following formulae:

\[|\mathcal{L}(3,=a)| = \begin{cases} 1 + 3a/2 + \sum_{i=a/2+1}^{a} (3 + 6(a-i)), & a \text{ even,} \\ \sum_{i=(a+1)/2}^{a} (3 + 6(a-i)), & a \text{ odd.} \end{cases}\]

Hence, using simple calculations, we obtain the formulae of the lemma.

Proposition 2.1. For n = 3, we have

\[|\mathcal{L}(n,a)| = \frac{1}{16}(a^4 + 8a^3 + 24a^2 + 32a + 16 - \epsilon(a)),\]

where ϵ(a) = 1 if a is odd and ϵ(a) = 0 otherwise.

Proof. Combining the two recursion formulas of Lemmas 2.1 and 2.3, we obtain the formulae for the residue, allowing to find the general polynomial.

Conjecture 1. |L(n, a)| is a polynomial in a of degree n + 1, with coefficients being functions of Bernouilli's numbers.

Proposition 2.1 (and Conjecture 1, if true) says that using proper intersections allows to go from an exponential number of list assignments to treat to a polynomial number.

3. (a, b, c)-choosability of Kⁿ

3.1. General coloring algorithm

We provide an algorithm that, given a list assignment L of Kn, produces a multi-coloring. We conjecture that this algorithm is optimal (i.e., produces an (L, b)-coloring if Kⁿ is (L, b)-colorable).

Algorithm ColorSym:. Taking an arbitrary list-assignment L as input, we consider at each step the vector w = (w1, . . . , wn), with wⁱ = being the number of colors given to vⁱ so far.

Step 1. Color every proper intersections of sets of size 1 : vⁱ gets |Ip({i})| colors. Thus wⁱ = |Ip({i})|.

Step i ≥ 2. If wⁱ ≥ b for each i or i = n+ 1, then Stop. Otherwise, for each set S with |S| = i, consider |Ip(S)| and let j ∈ S be the index for which w(j) is minimum (if more than one j with minimum w, then take the smallest index). Remove a color from Ip(S) and assign it to v^j . Goto Step i until Ip(S) is empty.

3.2. Symetrical list assignments on \(K_n\)

Let L be a a-list assignment on \(K_n\). We say that L is symetrical if for any \(i, 1 \le i \le n\), and any \(S, S' \subset [n]\) such that |S| = |S'|, we have \(|I_p(S)| = |I_p(S')|\). For such a list assignment, we let \(x_i = |I_p(S)|\) for \(S \subset [n], |S| = i\) and \(\mathbf{x}(L) = (x_1, x_2, \dots, x_n)\).

Considering symetrical list assignments allows to reduce the number of variables in the linear program from \(2^n - 1\) to n and to simplify Equation 5 into

\[\sum_{i=1}^{n} \binom{n-1}{i-1} x_i = a,\tag{7}\]

and Equation 6 into

\[\sum_{i=2}^{n} \binom{n-2}{i-2} x_i \le c,\tag{8}\]

and for the total amplitude:

\[\sum_{i=1}^{n} \binom{n}{i} x_i \ge nb. \tag{9}\]

As we will see, symetrical list assignments have the nice property that Equation 9 is sufficient to guarantee an (L, b)-coloring of \(K_n\). We will first prove how to find a balanced coloring of a set of subsets of [n]. We define \(\mathcal{P}(i, n)\) as the set of all subsets of cardinality i of the set \(\{1, \ldots, n\}\). Observe that \(|\mathcal{P}(i, n)| = \binom{n}{i}\). Let also \(\mathcal{P}(n) = \bigcup_{i=1}^{n} \mathcal{P}(i, n)\). For a weight vector \(\mathbf{w} = (w_1, \ldots, w_n)\), with \(w_i \geq 0\) for all \(i, 1 \leq i \leq n\), let \(\mathcal{P}(n)^{\mathbf{w}}\) be the multiset obtained from the empty set by adding to it \(w_i\) times the set \(\mathcal{P}(i, n)\) for any \(i, 1 \leq i \leq n\).

A partition (or coloring) \(P_1, \ldots, P_n\) of a subset S of \(\mathcal{P}(n)^{\mathbf{w}}\) is balanced if for any \(i, j, 1 \leq i \neq j \leq n\), \(||P_i|| - |P_j|| \leq 1\) and for any \(X \in P_j\), \(j \in X\).

Lemma 3.1. For any integer \(n \geq 3\) and any weight vector \(\mathbf{w}\) of size n, there exists a balanced partition of \(\mathcal{P}(n)^{\mathbf{w}}\).

Proof. Observe that \(\mathcal{P}(n)^{\mathbf{w}}\) is the union of sets \(\mathcal{P}(i,n)\). Let \(S_n\) be the group of permutations of n elements. Remark that \(S_n\) acts on \(\mathcal{P}(i,n)\). Let g be the n-elements cycle. Hence \(\mathcal{P}(i,n)\) can be viewed as the set of its orbits by g and \(\mathcal{P}(n)^{\mathbf{w}}\) as a multiset of orbits.

The general idea to prove the lemma is to color \(\mathcal{P}(n)^{\mathbf{w}}\) by coloring each orbit of each set \(\mathcal{P}(i,n)\) one after the other in any order while ensuring that at each step, the partial coloring is balanced. The key idea for showing this is possible is the following observation:

Claim 1. For any integers i and j, \(1 \le i, j \le n\), any orbit O of \(\mathcal{P}(i, n)\) can be colored with colors \(j, j+1, \ldots, j+|O|\) (with n+1=1).

proof. Observe first that all elements of [n] are present at least once in O. Hence, there exists \(o_j \in O\) such that \(o_j\) contains j. Color \(o_j\) by color j and color each remaining element \(g^k(o_j)\) of O with color j + k for \(k \in \{1, ..., n-1\}\) (j + k - n) if j + k > n.

The algorithm for obtaining a balanced coloring \(\varphi\) consists in coloring the orbits of \(\mathcal{P}(n)^{\mathbf{w}}\) in any order and, when coloring the elements of a new orbit, to start with the color j such that \(|\varphi^{-1}(j)| < |\varphi^{-1}(j-1)|\) if such a j exists and j = 1 otherwise and use Claim 1. After each such

step, we can observe that the (partial) coloring \(\varphi\) remains balanced. Therefore, after having colored the last element of the last orbit, \(\varphi\) is a balanced coloring of \(\mathcal{P}(n)^{\mathbf{w}}\).

Corollary 3.1. Let L be a symetrical list assignment of \(K_n\). If \(K_n\) is (L,b)-colorable, then Algorithm ColorSym produces an (L,b)-coloring.

Proof. To any symetrical list assignment L, we can make correspond a set \(S \subset \mathcal{P}(n)^{\mathbf{x}}\) (each set \(S \subset [n], |S| = i\), is present \(x_i\) times in S). Hence by Lemma 3.1, there exists a balanced coloring of S, and thus a coloring \(\varphi\) from L which is balanced, i.e., for any \(i, j \in [n], ||\varphi(v_i)| - |\varphi(v_j)|| \leq 1\). Therefore the amplitude condition has only to be verified globally, i.e., it suffices to show that Equation 9 is satisfied in order \(K_n\) to be (L, b)-colorable. As Equation 9 is a necessary condition, if an (L, b)-coloring of \(K_n\) exists then Algorithm ColorSym ends up with such a coloring. \(\square\)

3.3. Quasi-symetrical list assignments

Let L be a a-list assignment on \(K_n\). We say that L is quasi-symetrical if for any \(i, 1 \le i \le n\), and any \(S, S' \subset [n]\) such that |S| = |S'|, we have \(-1 \le |I_p(S)| - |I_p(S')| \le 1\).

The vector of cardinality-support \(\mathbf{cs}(S)\) of a set \(S = \{S_1, S_2, \dots, S_k\}\) of subsets of [n] is defined by \(\mathbf{cs}(S) = (\beta_1, \dots, \beta_n)\), with \(\beta_i = |\{i \in S_j, j \in \{1, \dots, k\}\}|\).

Lemma 3.2. For any n, k with \(n \ge 4\), \(k \ge 2\) and \(n \ge (2k - 1 + \sqrt{8k + 1})/2\), there exist a set of k + 1 k-subsets \(\{S'_1, S'_2, \ldots, S'_{k+1}\}\) of [n] and a set of k (k + 1)-subsets \(\{S_1, S_2, \ldots, S_k\}\) of [n] having the same cardinality-support vector.

Proof. Let n, k be as in the statement of the Lemma. We consider two cases : \(2 \le k \le n/2\) and \(n/2 < k \le n-2\).

Case 1. \[2 \le k \le n/2\]. For \(1 \le i \le k\), set \(S'_i = \{1, ..., k, k+i\}\) For \(1 \le j \le k\), set \(S_j = S'_i \setminus \{j\}\) and \(S_{k+1} = \{1, ..., k\}\).

By construction, they have the same cardinality support vector that starts with k times the entry k and k times the entry 1, i.e., \(\mathbf{cs}(S) = (k, k, ..., k, 1, ..., 1, 0, ..., 0)\).

Case 2. \(k \ge n/2\). For \(1 \le i \le k\), set \(S_i' = \{1, \dots, k-1, x_i, y_i\}\), with \(\{x_i, y_i\} \subset [k, n]\) and \(x_i \ne y_i\). We choose for each \(S_i'\) a different couple. This is always possible since there are \(\binom{n-k+1}{2}\) such couples and we have \(\binom{n-k+1}{2} \ge k\) since \(n \ge (2k-1+\sqrt{8k+1})/2\).

For \(1 \le j \le k-1\), \(S_j = S_j' \setminus \{j\}\) and \(S_k = S_k' \setminus \{x_k\}\) and \(S_{k+1} = \{1, \dots, k-1, x_k\}\). Again, by construction, both families of sets have the same cardinality support vector.

Proposition 3.1. Let a, b, n, x be integers such that \(x \le n\) and a = xb is a multiple of \(\binom{n-1}{x-1}\). Then \(K_n\) is not \((a, b, a \frac{x-1}{n-1} + 1)\)-colorable.

Proof. Let \(a = p\binom{n-1}{x-1}\) for some \(p \ge 1\). We first construct a symetrical list assignment L by setting \(|I_p(S_x)| = p\) for every set \(S_x \subset [n]\) with \(|S_x| = x\) and \(|I_p(S)| = 0\) for \(|S| \ne x\).

We check that for every \(j \in [n]\), |L(j)| = a and that \(\sum (L) = nb\). In fact, there are \(\binom{n}{x}\)

x-subsets of [n] and \(\binom{n-1}{x-1}\) of them containing some \(j \in [n]\). Hence \(|L(j)| = p \binom{n-1}{x-1} = a\)

and \[\Sigma(L)=p\binom{n}{x}=p\binom{n-1}{x-1}\frac{n}{x}=\frac{an}{x}=bn.\] Moreover, observe that for any \(i,j\in[n]\), we have \(|L(i)\cap L(j)|=p\binom{n-2}{x-2}=p\binom{n-1}{x-1}\frac{x-1}{n-1}=a\frac{x-1}{n-1}.\)

Now, by Lemma 3.2, there exists a set of x + 1 x-subsets of [n] and a set of x (x + 1)-subsets of [n] with the same cardinality support vector cs. Let S and S', respectively, be such sets as defined in the proof of Lemma 3.2. Hence, we can decrease \(|I_p(S)|\) by one for every \(S \in \mathcal{S}\) (hence \(|I_p(S)| = p - 1\) for such set) and increase \(|I_p(S')|\) by one for every \(S' \in \mathcal{S}'\) (hence \(|I_p(S')| = 1\) for such set). Let L' be the quasi-symetrical resulting list assignment. Since the cardinality support vector is the same for S and S', L' is a a-list assignment. We now prove that the amplitude of L' is \(\sum (L') = nb - 1\) and that L' is c'-separating, with \(c' = a \frac{x-1}{n-1} + 1\). For the amplitude, we have \(\Sigma(L') = p\binom{n}{x} - (x+1) + x = p\binom{n}{x} - 1 = \Sigma(L) - 1 = nb - 1\). For the separation condition, if \(i \in [n]\) such that \(\mathbf{cs}(i) = 0\), then we have, for any \(j \in [n]\), \(|L'(i) \cap L'(j)| = |L(i) \cap L(j)| \le c\). Otherwise, if \(i, j \in [n]\) are such that cs(i) > 0 and cs(j) > 0, then we are going to prove that \(|L'(i) \cap L'(j)| \le |L(i) \cap L(j)| + 1 \le c + 1\). First, consider the case \(2 \le x \le n/2\). If \(1 \le i, j, \le x\), then, by the construction of the proof of Lemma 3.2, there are x-2+1=x-1 sets in S and x sets in S' containing i, j, hence \(|L'(i) \cap L'(j)| = |L(i) \cap L(j)| - (x-1) + x = |L(i) \cap L(j)| + 1 = c'\). Otherwise (i > x or j > x), then \(|L'(i) \cap L'(j)| = |L(i) \cap L(j)|\). Second, consider the case x > n/2. If \(1 \le i, j, \le x-1\), then, by the construction of the proof of Lemma 3.2, there are x-2+1=x-1sets in S and x sets in S' containing i, j, hence \(|L'(i) \cap L'(j)| = |L(i) \cap L(j)| - (x-1) + x =\)\(|L(i) \cap L(j)| + 1 = c'\). Otherwise, if \(1 \le i \le x - 1\) and \(j \ge x\), then there is one more set in S'than in S containing both i and j, hence \(|L'(i) \cap L'(j)| = |L(i) \cap L(j)| + 1 = c'\). Otherwise \((i \ge x)\)and \(j \ge x\)), we have \(|L'(i) \cap L'(j)| = |L(i) \cap L(j)|\).

In conclusion, we have built a c'-separating a-list assignment L' for which the amplitude condition is not fulfilled and thus \(sep(K_n, a, b) < c'\).

Proposition 3.2. For integers a, b, n such that \(a \ge 2b\) and a is a multiple of \(\lfloor \frac{a^2}{2b(n-1)} \rfloor\), \(K_n\) is \((a, b, \lfloor \frac{a^2}{2b(n-1)} \rfloor)\)-choosable.

Proof. Let \(c = \lfloor \frac{a^2}{2b(n-1)} \rfloor\) and L be a c-separating a-list assignment with \(a = \lambda c\) for some \(\lambda \geq 1\). Let S be an i-subset of [n]. We are going to show that the amplitude condition is satisfied for S. We consider two cases.

If \(i \leq \lambda\), then since L is c-separating, the amplitude satisfies

\[\Sigma_S(L) \ge a + (a-c) + \ldots + (a-(i-1)c) = ia - \frac{1}{2}i(i-1)c.\]

Since \(ic \le \lambda c \le a\) and \(a \ge 2b\), we obtain \(\Sigma_S(L) \ge ia - \frac{1}{2}(i-1)a = \frac{1}{2}(i+1)a \ge ib\). If \(i > \lambda\), then the amplitude satisfies

\[\Sigma_S(L) \geq a + (a-c) + \ldots + (a-\lambda c) = (\lambda+1)a - \frac{1}{2}\lambda(\lambda+1)c = (\lambda+1)a - \frac{1}{2}\lambda a = \frac{1}{2}(\lambda+1)a.\] Since \(c = \lfloor \frac{a^2}{2b(n-1)} \rfloor \leq \frac{a^2}{2b(n-1)}\), then \(\lambda = \frac{a}{c} \geq \frac{2b(n-1)}{a}\).

List coloring with separation of the complete graph | J.-C. Godin, R. Grisot and O. Togni.

The above inequality with \(a \ge 2b\) induces

\[\Sigma_S(L) \ge \frac{1}{2}(\lambda + 1)a \ge \frac{2b(n-1) + a}{2a}a = bn + \frac{a-2b}{2} \ge bn.\]

Therefore the amplitude condition is satisfied and thus \(K_n\) is (L, b)-colorable.

4. Separation number of \(K_n\)

For \(K_2\), it is easily seen that \(sep(K_2, a, b) = a - b\) if \(a \le 2b\) and \(sep(K_2, a, b) = a\) if \(a \ge 2b\). For \(K_3 = C_3\), the separation number follows from results about the cycle from [12]:

Theorem 4.1 ([12]). For any \(p \ge 1\) and any a, b such that \(a \ge b \ge 1\),

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Hence for \(K_3 = C_3\) we have:

Corollary 4.1.

\[sep(K_3, a, b) = \begin{cases} a - b, & b \le a < 2b, \\ 2a - 3b, & 2b \le a < 3b, \\ a, & a \ge 3b. \end{cases}\]

For arbitrary values of n, we are (only) able to prove some bounds and two exact results for the remaining cases.

First, combining Propositions 3.1 and 3.2 allows to obtain the following bounds for the separation number when \(2b \le a \le nb\) (note the (roughly) factor two between the lower and upper bound):

Proposition 4.1. For integers a, b, n, x such that a = xb is a multiple of both \(\binom{n-1}{x-1}\) and \(\lfloor \frac{a^2}{2b(n-1)} \rfloor\), we have

\[\left| a \frac{x}{2(n-1)} \right| \le \operatorname{sep}(K_n, a, b) \le a \frac{x-1}{n-1}.\]

Proof. Proposition 3.1 gives \(sep(K_n, a, b) \le a \frac{x-1}{n-1}\) and Proposition 3.2 with x = a/b gives the lower bound.

Proposition 4.2. For any \(n \geq 3\) and , a, b such that \(b \leq a \leq 2b\), we have \(sep(K_n, a, b) = \lfloor \frac{2(a-b)}{n-1} \rfloor\).

Proof. Let a, b such that \(b \le a \le 2b\) and let \(c = \lfloor \frac{2(a-b)}{n-1} \rfloor\). Consider a c-separating a-list assignment L of \(K_n\), for \(n \ge 3\).

From the hypothesis, we have \((n-1)c \le 2(a-b) < a\).

By the separation condition, the amplitude of L on vertices from \(S \subset [n], |S| = i\), satisfies

\[\Sigma_S(L) \ge a + (a-c) + \ldots + (a-(i-1)c) = ia - \frac{1}{2}i(i-1)c.\]

Therefore, as c ≤ 2(a − b)/(n − 1), we obtain

\[\Sigma_S(L) \ge ia - \frac{1}{2}i(i-1)\frac{2(a-b)}{n-1} = ia\frac{n-i}{n-1} + ib\frac{i-1}{n-1} \ge ib.\]

Hence the amplitude condition is satisfied for any i, 1 ≤ i ≤ n and thus Kⁿ is (L, b)-colorable.

For proving the upper bound, we construct counter-examples to show that, for c ′ = c + 1, there exists c ′ -separating a a-list assignment L ′ that do not satisfy the amplitude condition, hence for which no (L ′ , b)-coloring exists.

First, if a ≥ (n − 1)c ′ , then L ′ is the quasi-symetrical list assignment constructed by setting for any i ∈ [n], |Ip({i})| = a − (n − 1)c ′ and for any i, j ∈ [n], i ̸= j, |Ip({i, j})| = c ′ , the other proper intersections being empty.

Then, by Equation 1 and Corollary 2.1, we have

\[\Sigma_{[n]}(L') = \sum_{i \in [n]} |I_{\mathsf{p}}(\{i\})| + \sum_{i,j \in [n], i < j} |I_{\mathsf{p}}(\{i,j\})| = na - n(n-1)c' + n\frac{n-1}{2}c' = na - n\frac{n-1}{2}c'.\]

As c ′ = c + 1 > 2(a − b)/(n − 1), we obtain

\[\Sigma_{[n]}(L') < na - n\frac{n-1}{2}\frac{2(a-b)}{n-1} = nb.\]

Hence the amplitude condition is not satisfied and Kⁿ is not (L ′ , b)-colorable.

Now, if (n − 1)c ≤ a < (n − 1)c ′ , then let α such that a = (n − 1)c ′ − α, with 1 ≤ α ≤ n − 1. Then L ′ is the quasi-symetrical list assignment constructed by setting for any i ∈ [n], |Ip({i})| = a − (n − 1)c + α and for any i, j ∈ [n], i ̸= j, |Ip({i, j})| = c ′ if i < j ≤ i + α and |Ip({i, j})| = c ′ − 1 otherwise, the other proper intersections being empty.

It is easy to observe that each vertex has a list of a−(n−1)c ′+α+α(c ′−1)+(n−1−α)c ′ = a colors and that the list assignment is c ′ -separating. But, the amplitude of the full list is

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

\[= na - \frac{n}{2}(n-1)c' - \frac{n}{2}\alpha.\]

As c ′ = c + 1 > 2(a − b)/(n − 1), we obtain

\[\Sigma_{[n]}(L') < na - \frac{n}{2}(n-1)\frac{2(a-b)}{n-1} - \frac{n}{2}\alpha = nb - \frac{n}{2}\alpha.\]

Hence the amplitude condition is not satisfied and Kⁿ is not (L ′ , b)-colorable.

Proposition 4.3. For any n ≥ 3 and , a, b such that (n − 1)b ≤ a ≤ nb, we have sep(Kn, a, b) = 2a − nb.

Proof. Let a, b such that (n − 1)b ≤ a ≤ nb and c = 2a − nb. Consider a c-separating a-list assignment L of Kn, for n ≥ 3.

By the separation condition, the amplitude of L on vertices from S ⊂ [n], |S| = 2, satisfies

\[\Sigma_S(L) \ge a + (a - c) = 2a - c = 2a - 2a + nb = nb.\]

Hence, for any S ⊂ [n], |S| ≥ 1, ΣS(L) ≥ |S|b and the amplitude condition is satisfied.

Now, we construct a counter example for c ′ = c + 1 = 2a − nb + 1 of a c ′ -separating a-list assignment L ′ for which no (L, b)-coloring exists. Let L ′ be constructed by setting for any i ∈ [n], |Ip([n] \ {i})| = a − c ′ and |Ip([n])| = (n − 1)c ′ − (n − 2)a, the other proper intersections being empty. Note that (n − 1)c ′ − (n − 2)a = (n − 1)(2a − nb + 1) − (n − 2)a = a(2n − 2 − n + 2) − (n − 1)(nb − 1) = n(a − (n − 1)b) + n − 1 ≥ 0 since a ≥ (n − 1)b by the hypothesis. Then, by Equation 1 and Corollary 2.1, we have

\[\Sigma_{[n]}(L') = n(a-c') + (n-1)c' - (n-2)a = 2a - c' = 2a - 2a + nb - 1 = nb - 1 < nb.\]

Thus the amplitude condition is not satisfied and Kⁿ is not (L ′ , b)-colorable.

Remark that Corollary 4.1 can also be deduced from Propositions 4.2 and 4.3.

Putting all the partial results together and the computations made, we propose the following conjecture:

Conjecture 2. for any n ≥ 4, a, b, p with 2 ≤ p ≤ n − 2 and pb ≤ a < (p + 1)b, we have

\[\operatorname{sep}(K_n, a, b) = \left\lceil \frac{2pa - p(p+1)b}{n-1} \right\rceil + \epsilon,\]

with ϵ ∈ {−1, 0}.

Let us explain how we arrive to this conjecture: First, as the degree of every vertex in Kⁿ is n−1, then, for a balanced distribution of colors among vertices, they should be grouped by packets of n − 1. Hence the separation number must be (the ceiling of) a certain function of a, b, p divided by n − 1. By Property 1, this function must also be close to an affine function. Second, supported by Proposition 3.1, we conjecture that when a = pb, then sep(Kn, a, b) = a(p − 1)/(n − 1). All this together lead us to propose the above conjecture, with ϵ being the correcting term depending on a, b, n.

In particular, for n = 4, the following refinement is conjectured, where only the case 2b ≤ a < 3b remains to be verified:

Conjecture 3.

\[\operatorname{sep}(K_4, a, b) = \begin{cases} \lfloor \frac{2(a-b)}{3} \rfloor, & b \le a < 2b, \\ \lceil \frac{4a-6b-1}{3} \rceil, & 2b \le a < 3b, \\ 2a-4b, & 3b \le a < 4b, \\ a, & a \ge 4b. \end{cases}\]

References

• [1] Y. Aubry, J.C. Godin, and O. Togni, Every triangle-free induced subgraph of the triangular lattice is (5m, 2m)-choosable, Discrete Applied Mathematics 166 (2014), 51–58.
• [2] Y. Aubry, J.C. Godin, and O. Togni, Free choosability of outerplanar graphs, Graphs and Combinatorics, 32(3) (2016), 851–859.
• [3] Z. Berikkyzy, C. Cox, M. Dairyko, K. Hogenson, M.M. Kumbhat, B. Lidicky, K. Messer- ´ schmidt, K. Moss, K. Nowak, K.F. Palmowski, and D. Stolee, (4, 2)-Choosability of Planar Graphs with Forbidden Structures, Graphs and Combinatorics 33 (2017),751–787.
• [4] M. Chen, K.W. Lih, and W. Wang, On choosability with separation of planar graphs without adjacent short cycles, Bulletin of the Malaysian Mathematical Sciences Society, 41 (2018), 1507–1518.
• [5] M. Chen, Y. Fan, A. Raspaud, W.C. Shiu, and W. Wang, Choosability with separation of planar graphs without prescribed cycles, Applied Mathematics and Computation, 367 (2020).
• [6] I. Choi, B. Lidicky, and D. Stolee, ´ On choosability with separation of planar graphs with forbidden cycles, Journal of Graph Theory, 81 (2016), 283–306.
• [7] M. Chen, Y. Fan, Y. Wang, and W. Wang, A sufficient condition for planar graphs to be (3,1)-choosable, Journal of Combinatorial Optimization, 34 (2017), 987–1011.
• [8] M.M. Cropper, J.L. Goldwasser, A.J.W. Hilton, D.G. Hoffman, and P.D. Johnson, Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs, Journal of Graph Theory 33(4) (2000), 199–219.
• [9] Z. Dvoˇrak, S. Norin, and L. Postle, ´ List coloring with requests, Journal of Graph Theory, 92 (2019), 191–206.
• [10] L. Esperet, R.J. Kang, and S. Thomasse´ Separation Choosability and Dense Bipartite Induced Subgraphs, Combinatorics, Probability and Computing, 28 (2019), 720–732.
• [11] Z. Furedi, A. Kostochka, and M. Kumbhat ¨ Choosability with separation of complete multipartite graphs and hypergraphs, Journal of Graph Theory, 76 (2014), 129–137.
• [12] J.C. Godin and O. Togni Choosability with Separation of cycles and outerplanar graphs, Discussiones Mathathematicae - Graph Theory, 43(3) (2023).
• [13] H.A. Kierstead and B. Lidicky, ´ On choosability with separation of planar graphs with lists of different sizes, Discrete Mathematics 338(10) (2015), 1779–1783.
• [14] J. Kratochv´ıl, Z. Tuza, and M. Voigt, Complexity of choosing subsets from color sets, Discrete Mathematics, 191(1-3) (1998), 139–148.

• [15] J. Kratochv´ıl, Z. Tuza, and M. Voigt Brooks-type theorems for choosability with separation, Journal of Graph Theory, 27 (1998), 43–49.
• [16] M. Kumbhat, K. Moss, and D. Stolee, Choosability with union separation, Discrete Mathematics 341(3) (2018), 600–605.
• [17] Y-C. Liang, T-L. Wong, and X. Zhu, Total weight choosability for Halin graphs, Electronic Journal of Graph Theory and Applications, 9(1) (2021).
• [18] R. Skrekovski, ˇ A note on choosability with separation for planar graphs, Ars Combinatoria, 58 (2001), 169–174.
• [19] X. Zhu, List 4-colouring of planar graphs, Journal of Combinatorial Theory, Series B 162 (2023), 1–12.

Appendix A. Vectorial solution of the ILP problem for symetrical list assignments

In this section, we show how the counter examples can be found using an algebraic formulation. Let \(e_1, \ldots, e_n\) be a canonical base of the vectorial space of dimension n.

We define the vector

\[\mathbf{a} = \sum_{i=1}^{n} \binom{n-1}{i-1} \mathbf{e}_i.\]

We can remark that \(\mathbf{a}\) is symmetrical. For a vector \(\mathbf{x} \in \mathbb{R}^n\), we define the linear application \(\varphi_a(\mathbf{x}) = \mathbf{a} \times \mathbf{x}\).

We also define the antisymetrical vectors \(\forall i \in [1, \lfloor \frac{n}{2} \rfloor]\),

\(as(i) = e_i - e_{n+1-i}\) and, \(\forall i \in [3, \lceil \frac{n}{2} \rceil]\), the Pascal's triangle vectors

\(\mathbf{tp}(i) = \mathbf{e}_i + \mathbf{e}_{i-1} - \binom{n}{i-1} \mathbf{e}_1.\)

Lastly, we define the binomial vector \(\mathbf{bn} = \sum_{i=1}^{n} \mathbf{e}_i - 2^{n-1} \mathbf{e}_1\).

Lemma 1. The kernel \(\ker (\varphi_a)\) has \(\{\{as(i)\}, \{tp(i)\}, bn\}\) as basis and is thus of dimension n-1.

Proof. By construction, it is easy to observe that \(F_a = \{\{as(i)\}, \{tp_i\}, bn\} \subset \ker(\varphi_a)\). As the number of elements of \(F_a\) is equal to the dimension of \(\ker(\varphi_a)\), it suffices to show that \(F_a\) is a family of free vectors. We consider two cases depending on the parity of n.

Case 1. n even. Let \(\alpha_i\), \(1 \le i \le \frac{n}{2}\) and \(\beta_j\), \(3 \le j \le \frac{n}{2}\) and \(\gamma \in \mathbb{R}\) such that

\[\sum_{i=1}^{n/2} \alpha_i \mathbf{as}(i) + \sum_{j=3}^{n/2} \beta_j \mathbf{tp}(j) + \gamma \mathbf{bn} = \mathbf{0}.\]

For the k-th coordinate of the left side of the above equality, with \(k \in [\frac{n}{2} + 1, n]\), we have \(-\alpha_{n+1-k} + \gamma = 0\), thus \(\gamma = \alpha_1 = \alpha_2 = \ldots = \alpha_{n/2}\).

For k = 2, \(\alpha_2 + \beta_3 + \gamma = 0 \Rightarrow \beta_3 = -2\gamma\).

For \(k \in [3, \frac{n}{2} - 1]\), \(\alpha_k + \beta_k + \beta_{k+1} + \gamma = 0 \Rightarrow \beta_4 = \ldots = \beta_{n/2} = 0\).

For k = n/2, \(\alpha_k + \beta_k + \gamma = 0 \Rightarrow \alpha_{n/2} = -\gamma\). But we have seen that \(\alpha_{n/2} = \gamma\), hence \(\gamma = 0\).

Consequently, we obtain that all coefficients are equal to zero.

Case 2. n odd. Let \(\alpha_i\), \(1 \le i \le \frac{n-1}{2}\) and \(\beta_j\), \(3 \le j \le \frac{n+1}{2}\) and \(\gamma \in \mathbb{R}\) such that

\[\sum_{i=2}^{(n-1)/2} \alpha_i \mathbf{as}(i) + \sum_{j=3}^{(n+1)/2} \beta_j \mathbf{tp}(j) + \gamma \mathbf{bn} = \mathbf{0}.\]

For the k-th coordinate of the left side of the above equality, \(k \in [\frac{n+3}{2}, n-1]\), we have \(-\alpha_{n+1-k} + \gamma = 0\). Thus \(\gamma = \alpha_1 = \ldots = \alpha_{(n-1)/2}\).

For k = (n+1)/2, \(\beta_k + \gamma = 0 \Rightarrow \beta_{(n+1)/2} = -\gamma\).

For \(k \in [3, \frac{n-1}{2} - 1]\), \(\alpha_k + \beta_k + \beta_{k+1} + \gamma = 0\). Hence \(\beta_k = -\alpha_k = -\gamma\).

Finally, for k = 2, \(\alpha_2 + \beta_3 + \gamma = 0 \Rightarrow \gamma = 0\).

Similarly, for the separation condition, we define the vector

\[\mathbf{c} = \sum_{i=2}^{n} \binom{n-2}{i-2} \mathbf{e}_i\]

and the linear application φc(x) = c × x.

We also define the vectors

• ∀i ∈ [2, ⌊ n 2 ⌋], asc(i) = ∆(i, n)as(1) + as(i), with ∆(i, n) = n−2 i−2 − n−2 n−1−i = n−2 i−2 − n−2 i−1 .
• ∀i ∈ [3, ⌈ n 2 ⌉], tpc(i) = n−1 i−2 as(1) + tp(i).
• bnc = 2ⁿ−²as(1) + bn.

Lemma 2. The intersection of kernels ker (φa) ∩ ker (φc) has {{asc(i)}, {tpc(i)}, bnc} as a basis and is thus of dimension n − 2.

Proof. It is easy to see that Fac = {{asc(i)}, {tpc(i)}, bnc} ⊂ ker (φa) ∩ ker (φc) and has n − 2 vectors. Since the dimension of ker (φa) ∩ ker (φc) is equal to n − 2 too, it suffices to show that Fac is a free family. We consider two cases depending on the parity of n.

• Case n even. Let αⁱ , 2 ≤ i ≤ n 2 and β^j , 3 ≤ j ≤ n 2 and γ ∈ R such that

\[\sum_{i=2}^{n/2} \alpha_i \mathbf{asc}(i) + \sum_{j=3}^{n/2} \beta_j \mathbf{tpc}(j) + \gamma \mathbf{bnc} = \mathbf{0}.\]

For k ∈ [ n ² + 1, n − 1], −αn+1−^k + γ = 0 ⇒ γ = α² = α³ = . . . = αn/2−¹ = αn/2.

For k = n/2, α^k + β^k + γ = 0 ⇒ βn/² = −2γ.

For k ∈ [3, n ² − 1], α^k + β^k + βk+1 + γ = 0 ⇒ β³ = . . . = βn/2−¹ = 0.

Finally, for k = 2, α² + β³ + γ = 0 ⇒ 2γ = 0 ⇒ γ = 0.

• Case n odd. Let αⁱ , 2 ≤ i ≤ n+1 2 and β^j , 3 ≤ j ≤ n+1 2 and γ ∈ R such that

\[\sum_{i=2}^{(n+1)/2} \alpha_i \mathbf{asc}(i) + \sum_{j=3}^{(n+1)/2} \beta_j \mathbf{tpc}(j) + \gamma \mathbf{bnc} = \mathbf{0}.\]

For k ∈ [ n+3 2 , n − 1], −αn+1−^k + γ = 0 ⇒ γ = α² = α³ = . . . = α(n−1)/2.

For k = (n + 1)/2, −α(n−1)/² + β^k + γ = 0 ⇒ β(n+1)/² = 0.

For k ∈ [3, n−1 ² −1], αk+βk+βk+1γ = 0 ⇒ β(n−1)/² = 2γ, β(n−3)/² = 0, β(n−5)/² = 2γ, . . ..

Finally, for k = 2, α² + β³ + γ = 0 ⇒ β³ = −2γ. If (n + 1)/2 ≡ 3 mod 4 then γ = 0. Otherwise ((n + 1)/2 ̸≡ 3 mod 4), then 2γ = −2γ and thus γ = 0.

In both cases, we have shown that all coefficients are equal to zero, proving that the set of vectors forms a free family.

We define ψ = P^{n i}=1 n i eⁱ which is the measure of the amplitude and E(a, c) = {x such that φa(x) = a and φc(x) = c}.

Now, using the maximum principle, we define the two optimal solution vectors xⁱ , i = 1, 2.

• If a ≥ (n − 1)c, we define x¹ = (a − (n − 1)c)e¹ + ce2. We can observe that x¹ ∈ E(a, c). In fact E(a, c) = x¹ + ker(φa) ∩ ker(φc). This solution corresponds to the counter-example used in proof of Proposition 4.2.
• If a ≤ n−1 n−2 c, x² = (a − c)en−¹ + ((n − 1)c − (n − 2)a)en. We can observe that x² ∈ E(a, c). In fact E(a, c) = x² + ker(φa) ∩ ker(φc). This solution corresponds to the counter-example used in proof of Proposition 4.3.