June 19, 2026
A family of permutations of \([n]\) is called setwise distinguishable if for every permutation in the family there exists a subset of \([n]\) whose image under this permutation differs from its image under any other permutation in the family. We prove that there exists a setwise distinguishable family of \(2^{(2-o(1)) \cdot n}\) permutations of \([n]\). The result is optimal up to the \(o(1)\) term in the exponent and is achieved through an explicit construction. As an application, we obtain nearly tight conditional lower bounds on the kernelization complexity of graph coloring problems parameterized by the vertex-deletion distance to split graphs. This improves a result of Jansen and Kratsch (Inf. Comput., 2013).
Extremal combinatorics is the area that investigates the maximum and minimum possible sizes of families of discrete objects subject to prescribed constraints (see, e.g., [1]). Beyond their intrinsic interest, such problems naturally arise in diverse fields, including computer science, information theory, number theory, and geometry. A central branch of this area is extremal set theory, which focuses on collections of sets and of objects that involve sets in various ways. One cornerstone result, due to Erdős, Ko, and Rado [2], concerns the notion of intersecting set families, where any two sets share at least one element. It states that the largest size of an intersecting family of \(k\)-subsets of \([n] = \{1,\ldots,n\}\) is \(\binom{n-1}{k-1}\), attained by the family of all \(k\)-subsets that include a fixed element. Another landmark result, proved by Sperner [3] in 1928, deals with antichains — families of sets with no set containing another — and asserts that the largest size of an antichain over \([n]\) is \(\binom{n}{\lfloor n/2 \rfloor}\), realized by the family of all subsets of \([n]\) of size \(\lfloor n/2 \rfloor\). This result has seen various extensions and variations over the years. A notable example is the canonical theorem of Bollobás [4], showing that for all positive integers \(a\) and \(b\), the maximum size \(m\) of a collection \(\{(A_i,B_i)\}_{i \in [m]}\) of pairs of sets satisfying \(|A_i| = a\) and \(|B_i|=b\) for all \(i \in [m]\) and \(A_i \cap B_j = \emptyset\) if and only if \(i=j\) is \(\binom{a+b}{a}\). This maximum is achieved by the collection of all pairs \((A,B)\) of subsets of \([a+b]\) with \(|A| = a\) and \(B = [a+b] \setminus A\).
Significant attention has been devoted in the literature to extremal combinatorics questions concerning permutations. A family of permutations of \([n]\) is called intersecting if any two of its members agree on at least one element. Analogously to the result of [2], Frankl and Deza [5] proved in 1977 that the largest size of an intersecting family of permutations of \([n]\) is \((n-1)!\), attained by the collection of all permutations fixing a particular element. This notion naturally extends to that of \(t\)-intersecting families, for a positive integer \(t \leq n\), where any two permutations are required to agree on at least \(t\) elements. It was conjectured in [5] that for all integers \(t\) and \(n\) with \(n\) sufficiently greater than \(t\), the largest size of a \(t\)-intersecting family of permutations of \([n]\) is \((n-t)!\). The conjecture was proved more than three decades later independently by Ellis and by Friedgut and Pilpel [6], and the dependence of \(n\) on \(t\) has since been considerably sharpened (see, e.g., [7]). Another variant of this problem handles \(t\)-setwise intersecting families of permutations of \([n]\), in which any two permutations agree on some \(t\) elements as a set. Namely, for any two permutations \(\pi\) and \(\pi'\) in the family, there exists a \(t\)-subset \(A\) of \([n]\) such that \(\pi(A) = \pi'(A)\), where \(\pi(A)\) stands for the image of \(A\) under \(\pi\), that is, \(\pi(A) = \{\pi(x) \mid x \in A\}\). Ellis conjectured in [8] that for all positive integers \(t \leq n\), the largest size of a \(t\)-setwise intersecting family of permutations of \([n]\) is \(t! \cdot (n-t)!\), which is realized by the permutations of \([n]\) that map a fixed \(t\)-subset of \([n]\) to itself. He confirmed the conjecture for the case where \(n\) is sufficiently large as a function of \(t\). The conjecture was also verified for \(t=2\) and for \(t=3\) for all admissible values of \(n\) by Meagher et al. [9] and Behajaina et al. [10], respectively.
The results discussed above concern families of permutations that are forced to exhibit a prescribed amount of agreement. A natural complementary objective is to explore the opposite extremal behavior, namely, how large a family of permutations can be if its members are required to disagree in a structured way. One common instance of this requirement is that any two distinct permutations in the family disagree pointwise on at least some specified number of elements. This corresponds to the concept of permutation codes, which has been extensively studied in coding theory (see, e.g., [11]). The present paper investigates a setwise variant of disagreement among permutations, with applications to the parameterized complexity of graph coloring problems, as described below.
We study the maximum size of a family of permutations of \([n]\) in which each permutation is distinguished from all others by its image on some subset. We call such families setwise distinguishable and define them formally as follows.
Definition 1. For a positive integer \(n\), a family \({\cal F}\) of permutations of \([n]\) is called setwise distinguishable* if for every permutation \(\pi \in {\cal F}\) there exists a set \(A_\pi \subseteq [n]\), such that \(\pi(A_\pi) \neq \pi'(A_\pi)\) for all \(\pi' \in {\cal F}\setminus \{\pi\}\).*
For a positive integer \(n\), let \(m(n)\) denote the largest possible size of a setwise distinguishable family of permutations of \([n]\). It is easy to see that \(m(n) \leq 2^{2n}\). Indeed, given a setwise distinguishable family \({\cal F}\) of permutations of \([n]\), consider for each permutation \(\pi \in {\cal F}\) the pair \((A_\pi, \pi(A_\pi))\), where \(A_\pi\) is the subset of \([n]\) distinguishing \(\pi\) from all other permutations in \({\cal F}\). Since any two distinct permutations \(\pi,\pi' \in {\cal F}\) satisfy \(\pi(A_\pi) \neq \pi'(A_\pi)\), it follows that each permutation in \({\cal F}\) is associated with a distinct pair of subsets, implying that \(|{\cal F}| \leq 2^{2n}\) (see Lemma 2 for a slightly tighter bound). On the other hand, consider a maximal family of permutations of \([n]\) whose images on a fixed subset of size \(\lfloor n/2 \rfloor\) are pairwise distinct. Such a family yields that \(m(n) \geq \binom{n}{\lfloor n/2 \rfloor} = 2^{(1-o(1)) \cdot n}\), where the \(o(1)\) term tends to zero as \(n\) tends to infinity. Our main result establishes an exponential improvement over this lower bound, showing that there exists a setwise distinguishable family of permutations of \([n]\) of size \(2^{(2-o(1)) \cdot n}\). This yields the following asymptotic estimate for \(m(n)\), which is tight up to the \(o(1)\) term in the exponent.
Theorem 1. \[m(n) = 2^{(2-o(1)) \cdot n}.\]
The lower bound on \(m(n)\) is obtained through an explicit elementary construction. For refined upper and lower bounds on \(m(n)\), see Theorem 4.
Our motivation to study setwise distinguishable families of permutations stems from the area of parameterized complexity (see, e.g., [12]). This area investigates the computational complexity of decision problems in terms of a quantitative feature of their instances, referred to as a parameter. In the central theme of kernelization, the objective is to efficiently compress a given instance of a parameterized problem into an equivalent instance whose size is bounded by a function that depends only on the parameter. More concretely, a kernel takes as input a pair \((x,k)\), where \(x\) is the actual instance and \(k\) is the parameter, and produces in polynomial time an equivalent instance \((x',k')\) satisfying \(|x'|+k' \leq h(k)\) for some computable function \(h: \mathbb{N}\to \mathbb{R}\). Determining the minimal growth rate of the kernel size \(h\) for a given problem is a fundamental task in the field.
For a positive integer \(q\), the \(q\textrm{\mathrm{\small -Coloring}}\) problem asks to decide whether a given graph is \(q\)-colorable, that is, whether there exists a function from its vertex set to the color set \([q]\) assigning distinct colors to the endpoints of every edge. The \(q\textrm{\mathrm{\small -Coloring}}\) problem is well known to be \(\mathsf{NP}\)-hard when \(q \geq 3\), and as such, it has been extensively studied in the framework of parameterized complexity under diverse versions and parameterizations. In particular, Cai [13] introduced the study of the \(q\textrm{\mathrm{\small -Coloring}}\) problem parameterized by the vertex-deletion distance to a prescribed graph family \({\cal G}\). In this problem, called the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \({\cal G}+k\mathrm{v}\) graphs, the input consists of a graph \(G=(V,E)\) and a set \(X \subseteq V\) of \(k\) vertices whose removal from \(G\) gives a graph that belongs to \({\cal G}\), and the goal is to decide whether \(G\) is \(q\)-colorable, where the parameter is \(k\). For example, taking \({\cal G}\) as the graph family \(\mathrm{\small Empty}\) that consists of all edgeless graphs, the parameter expresses the size of a vertex cover in the graph. A series of papers by Jansen and Kratsch [14] and by Jansen and Pieterse [15], [16] has shown that for every integer \(q \geq 3\), the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \(\mathrm{\small Empty}+k\mathrm{v}\) graphs admits a kernel of size \(O(k^{q-1} \cdot \log k)\), whereas for any real \(\varepsilon>0\), it admits no kernel of size \(O(k^{q-1-\varepsilon})\) unless \(\mathsf{NP}\subseteq \mathsf{coNP/poly}\). Since this containment is known to imply the collapse of the polynomial-time hierarchy [17], these results essentially settle the kernel complexity of the \(q\textrm{\mathrm{\small -Coloring}}\) problems when parameterized by the vertex cover number. Further extensions are given in [18], [19].
The kernel complexity of the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \({\cal G}+k\mathrm{v}\) graphs was systematically studied by Jansen and Kratsch [14] for general graph families \({\cal G}\). Interestingly, their results reveal a strong connection between the kernel complexity of the problem and the behavior of graphs in \({\cal G}\) as instances of the so-called \(q\textrm{\mathrm{\small -List Coloring}}\) problem, which asks, given a graph \(G\) and a list of available colors from \([q]\) for each vertex, whether \(G\) admits a proper coloring respecting these lists. On the positive side, they proved that if a graph family \({\cal G}\) is closed under induced subgraphs and if every \(\mathsf{NO}\) instance of \(q\textrm{\mathrm{\small -List Coloring}}\) with a graph from \({\cal G}\) contains a \(\mathsf{NO}\) sub-instance on at most \(t(q)\) vertices, then the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \({\cal G}+k\mathrm{v}\) graphs admits a kernel with \(O(k^{q \cdot t(q)})\) vertices. On the negative side, they proved that if a graph family \({\cal G}\) is closed under disjoint union and if there exists an irreducible \(\mathsf{NO}\) instance of \((q-2)\textrm{\mathrm{\small -List Coloring}}\) with a graph in \({\cal G}\) on \(t(q) \geq 3\) vertices, that is, a \(\mathsf{NO}\) instance that becomes a \(\mathsf{YES}\) instance upon removing any vertex, then for any real \(\varepsilon>0\), the problem admits no kernel of size \(O(k^{t(q)-\varepsilon})\) unless \(\mathsf{NP}\subseteq \mathsf{coNP/poly}\). Therefore, for applicable graph families \({\cal G}\), estimating the degree of the polynomial kernel complexity of the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \({\cal G}+k\mathrm{v}\) graphs essentially reduces to analyzing the largest number of vertices in an irreducible \(\mathsf{NO}\) instance of \(q\textrm{\mathrm{\small -List Coloring}}\) with a graph from \({\cal G}\).
The authors of [14] demonstrated their results on the kernelizability of the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \({\cal G}+k\mathrm{v}\) graphs for several graph families \({\cal G}\). In particular, they considered the family \(\cup \mathrm{\small Split}\) of all graphs whose connected components are split graphs, that is, graphs whose vertex set can be partitioned into a clique and an independent set. They showed that every \(\mathsf{NO}\) instance of \(q\textrm{\mathrm{\small -List Coloring}}\) with a graph in \(\cup \mathrm{\small Split}\) contains a \(\mathsf{NO}\) sub-instance on at most \(2^{2q}+q\) vertices, and concluded that the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \(\cup \mathrm{\small Split}+ k\mathrm{v}\) graphs admits a kernel of size \(O(k^{f(q)})\) for a function \(f: \mathbb{N}\to \mathbb{N}\) satisfying \(f(q) = 2^{(2+o(1)) \cdot q}\). They also showed that there exists an irreducible \(\mathsf{NO}\) instance of \(q\textrm{\mathrm{\small -List Coloring}}\) with a split graph on \(\binom{q}{\lfloor q/2 \rfloor}+\lfloor q/2 \rfloor\) vertices, yielding that for every integer \(q \geq 4\) and any real \(\varepsilon>0\), the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \(\cup \mathrm{\small Split}+ k\mathrm{v}\) graphs admits no kernel of size \(O(k^{g(q)-\varepsilon})\) for some function \(g: \mathbb{N}\to \mathbb{N}\) satisfying \(g(q)=2^{(1-o(1)) \cdot q}\), unless \(\mathsf{NP}\subseteq \mathsf{coNP/poly}\). This result indicates that the degree of the polynomial kernel complexity of these problems grows exponentially with the number of colors \(q\), and yet retains a pronounced exponential multiplicative gap to the upper bound. As an application of our construction of setwise distinguishable families of permutations, we produce an irreducible \(\mathsf{NO}\) instance of the \(q\textrm{\mathrm{\small -List Coloring}}\) problem with a split graph on \(2^{(2-o(1)) \cdot q}\) vertices. Consequently, we nearly close the gap from [14] and obtain an asymptotically tight estimate for the degree of the polynomial kernel complexity of the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \(\cup \mathrm{\small Split}+ k\mathrm{v}\) graphs, as stated below.
Theorem 2. There exists a function \(g: \mathbb{N}\to \mathbb{N}\) satisfying \(g(q) = 2^{(2-o(1)) \cdot q}\), such that for every sufficiently large integer \(q\) and for any real \(\varepsilon>0\), the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \(\cup \mathrm{\small Split}+ k\mathrm{v}\) graphs does not admit a kernel of size \(O(k^{g(q)-\varepsilon})\) unless \(\mathsf{NP}\subseteq \mathsf{coNP/poly}\).
We note that the lower bound stated in Theorem 2 trivially extends to the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \({\cal G}+ k\mathrm{v}\) graphs for any family \({\cal G}\) containing \(\cup \mathrm{\small Split}\). This in particular applies to the family of cochordal graphs, namely, the edge-complements of graphs in which every cycle of length at least \(4\) has a chord, and to the family of cographs, namely, graphs with no induced path of length \(4\). Therefore, as a by-product of Theorem 2, we strengthen the lower bounds of [14] on the kernel complexity of the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \({\cal G}+ k\mathrm{v}\) graphs for these families \({\cal G}\).
The rest of this short paper is organized as follows. Section 2 presents our upper and lower bounds on \(m(n)\), thereby proving Theorem 1. Section 3 discusses the implications for graph coloring kernelization, confirming Theorem 2. Finally, Section 4 provides concluding remarks and potential avenues for further work.
In this section, we study the largest possible size \(m(n)\) of a setwise distinguishable family of permutations of \([n]\) (see Definition 1). Recall that for a function \(\pi: [n] \to [n]\) and a set \(A \subseteq [n]\), \(\pi(A)\) denotes the image of \(A\) under \(\pi\), that is, \(\pi(A) = \{\pi(x) \mid x \in A\}\). We also write \({\cal P}(A)\) for the power set of \(A\). We begin with the following simple lemma, which provides an alternative characterization of \(m(n)\).
Lemma 1. For every positive integer \(n\), \(m(n)\) is the largest integer \(m\) for which there exists a collection \(\{(A_i,B_i)\}_{i \in [m]}\) of \(m\) pairs of subsets of \([n]\) such that for every \(i \in [m]\), there exists a permutation \(\pi_i:[n] \to [n]\) such that for all \(j \in [m]\), it holds that \[\pi_i(A_j) = B_j ~~~if and only if~~~ i=j.\]
Let \(m\) and \(n\) be positive integers. Suppose first that there exists a collection \(\{(A_i,B_i)\}_{i \in [m]}\) of \(m\) pairs of subsets of \([n]\) as in the lemma. For each \(i \in [m]\), let \(\pi_i:[n] \to [n]\) denote the guaranteed permutation, which satisfies \(\pi_i(A_i) = B_i\) and \(\pi_i(A_j) \neq B_j\) for all \(j \in [m] \setminus \{i\}\). It then follows that the family \(\{\pi_j \mid j \in [m]\}\) is setwise distinguishable, with each \(A_j\) distinguishing \(\pi_j\) from all other permutations. Conversely, suppose that there exists a setwise distinguishable family \(\{\pi_j \mid j \in [m]\}\) of \(m\) permutations of \([n]\). It follows that for each \(j \in [m]\), there exists a set \(A_j \subseteq [n]\) with \(\pi_j(A_j) \neq \pi_i(A_j)\) for all \(i \in [m] \setminus \{j\}\). For each \(j \in [m]\), define \(B_j = \pi_j(A_j)\), and notice that the collection \(\{(A_i,B_i)\}_{i \in [m]}\) satisfies for all \(i,j \in [m]\) that \(\pi_i(A_j) = B_j\) if and only if \(i=j\). This establishes the lemma.
An immediate consequence of Lemma 1 is that \(m(n) \leq 2^{2n}\) for all positive integers \(n\). The following lemma slightly strengthens this bound.
Lemma 2. For every integer \(n \geq 2\), it holds that \[m(n) \leq \sum_{k=1}^{\lfloor n/2 \rfloor}{{\binom{n}{k}}^2}.\] Therefore, for every positive integer \(n\), it holds that \(m(n) < \binom{2n}{n}\).
For an integer \(n \geq 2\), let \(m = m(n) \geq 2\), and apply Lemma 1 to obtain a collection \(\{(A_i,B_i)\}_{i \in [m]}\) of pairs of subsets of \([n]\) such that for every \(i \in [m]\), there exists a permutation \(\pi_i:[n] \to [n]\) such that for all \(j \in [m]\), it holds that \(\pi_i(A_j) = B_j\) if and only if \(i=j\). In particular, for every \(i \in [m]\), we have \(\pi_i(A_i) = B_i\), which implies that \(|A_i| = |B_i|\). Since all permutations of \([n]\) share the same image on the empty set, and since \(m \geq 2\), it further follows that \(|A_i| \geq 1\) for all \(i \in [m]\). Additionally, for every permutation \(\pi:[n] \to [n]\) and for any two sets \(A,B \subseteq [n]\), it holds that \(\pi(A) = B\) if and only if their complements satisfy \(\pi(\overline{A}) = \overline{B}\). Hence, without loss of generality, we may assume that \(|A_i| \leq \lfloor n/2 \rfloor\) for all \(i \in [m]\), replacing the pair \((A_i,B_i)\) by \((\overline{A_i},\overline{B_i})\) if needed. Finally, for every \(k\)-subset \(A\) of \([n]\) with \(1 \leq k \leq \lfloor n/2 \rfloor\), consider all indices \(i \in [m]\) with \(A_i = A\). The sets \(B_i\) corresponding to these indices are pairwise distinct, because for distinct such indices \(i\) and \(j\), we have \(B_i = \pi_i(A_i) = \pi_i(A_j) \neq B_j\), hence their number does not exceed \(\binom{n}{k}\). We thus obtain that \(m \leq \sum_{k=1}^{\lfloor n/2 \rfloor}{{\binom{n}{k}}^2}\), as required. In particular, using the identity \(\sum_{k=0}^{n}{{\binom{n}{k}}^2} = \binom{2n}{n}\), it follows that \(m < \binom{2n}{n}\). By \(m(1)=1\), the inequality \(m(n) < \binom{2n}{n}\) holds for all positive integers \(n\), so the proof is complete.
We now turn to the core of this section. The following theorem provides an explicit construction of a collection of pairs of subsets of \([n]\) satisfying the property from Lemma 1. This will be used to establish a nearly tight lower bound on \(m(n)\). While the first item of the theorem is not required for this bound, it will play a crucial role in the application discussed in the next section.
Theorem 3. Let \(k\) and \(n\) be positive integers, such that \(2k\) divides \(n\). Then there exists a collection \(\{(A_i,B_i)\}_{i \in [m]}\) of \[m = {\binom{2k}{k}}^{n/k-1}\] pairs of subsets of \([n]\), each of size \(n/2\), such that
for every permutation \(\pi:[n] \to [n]\) there exists an \(i \in [m]\) such that \(\pi(A_i) = B_i\), and
for every \(i \in [m]\) there exists a permutation \(\pi_i:[n] \to [n]\) such that for all \(j \in [m]\), it holds that \[\pi_i(A_j) = B_j ~~ if and only if~~ i = j.\]
For positive integers \(k\) and \(n\) with \(2k\) dividing \(n\), denote \(t = n/(2k)\), partition \([n]\) into \(t\) pairwise disjoint sets \(C_1, \ldots, C_t\) of size \(2k\) each, and let \(C'_1\) be an arbitrary \(k\)-subset of \(C_1\). Define \[{\cal F}= \Big \{ (A,B) \in {\cal P}([n]) \times {\cal P}([n]) ~\Big |~ |A \cap C_i| = |B \cap C_i| = kfor all i \in [t]andA \cap C_1 =C'_1 \Big \}.\] In words, \({\cal F}\) is the collection of all pairs \((A,B)\) of subsets of \([n]\), such that each of \(A\) and \(B\) includes precisely \(k\) elements from each part \(C_i\), and the elements of \(A\) in \(C_1\) are fixed to those of \(C'_1\). Note that for every pair \((A,B) \in {\cal F}\), we have \(|A|=|B|=t \cdot k = n/2\). It further holds that \[|{\cal F}| = {\binom{2k}{k}}^{t-1} \cdot {\binom{2k}{k}}^{t} = {\binom{2k}{k}}^{2t-1} = {\binom{2k}{k}}^{n/k-1}.\] We show that the family \({\cal F}\) satisfies the properties asserted in the theorem.
For Item [itm:1], consider any permutation \(\pi: [n] \to [n]\), and define a bipartite multigraph \(G\) with \(t\) vertices \(x_1, \ldots, x_t\) on one side and \(t\) vertices \(y_1, \ldots, y_t\) on the other, as follows. For each \(r \in [n]\), add to \(G\) an edge, marked by \(r\), that connects the vertices \(x_i\) and \(y_j\) for the indices \(i\) and \(j\) satisfying \(r \in C_i\) and \(\pi(r) \in C_j\). Note that each vertex \(x_i\) is incident in \(G\) with exactly \(2k\) edges, marked by the elements of \(C_i\), connecting it to the vertices \(y_j\) associated with the parts \(C_j\) to which the elements of \(C_i\) are mapped by \(\pi\). Since \(\pi\) is a permutation of \([n]\), the multigraph \(G\) is \(2k\)-regular, hence Kőnig’s line-coloring theorem implies that it admits a proper edge-coloring with \(2k\) colors, and thus a partition of its edge set into \(2k\) perfect matchings. The \(k\) edges marked by the elements of \(C'_1\) belong to \(k\) distinct matchings, because they are all incident with the vertex \(x_1\). Let \(A \subseteq [n]\) denote the set of all marks of the edges in these \(k\) matchings, and let \(B = \pi(A)\). By construction, we have \(|A \cap C_i| = |B \cap C_i| = k\) for all \(i \in [t]\) and \(A \cap C_1 = C'_1\), implying that \((A,B) \in {\cal F}\). It follows that the permutation \(\pi\) admits a pair \((A,B) \in {\cal F}\) such that \(\pi(A) = B\), as required.
For Item [itm:2], consider a pair \((A,B) \in {\cal F}\), and define a function \(\pi : [n] \to [n]\) as follows. For each \(i \in [t]\), define \(\pi\) on the elements of \(C_i\) so that \[\pi(A \cap C_i) = B \cap C_i ~~and~~ \pi(C_i \setminus A) = C_{i+1} \setminus B,\] where the set \(C_{t+1}\) is identified with \(C_1\). Note that this is possible, because \(|A \cap C_i| = |B \cap C_i| = k\) and \(|C_i \setminus A| = |C_{i+1} \setminus B| = k\) for all \(i \in [t]\). The function \(\pi\) is a permutation of \([n]\), because the \(2t\) sets \(B \cap C_i\) and \(C_{i+1} \setminus B\) with \(i \in [t]\) form a partition of \([n]\). It further holds that \(\pi(A) = B\), because \(\pi(A \cap C_i) = B \cap C_i\) for all \(i \in [t]\).
It remains to show that for every pair \((A',B') \in {\cal F}\) with \((A',B') \neq (A,B)\), the permutation \(\pi\) satisfies \(\pi(A') \neq B'\). To this end, fix such a pair \((A',B')\). If \(A=A'\), then we have \(B \neq B'\), hence \(\pi(A') = \pi(A) = B \neq B'\), as desired. So suppose that \(A \neq A'\), and recall that we have \(A \cap C_1 = A' \cap C_1 = C'_1\). This implies that there exists some \(j \in [t-1]\) such that \[A \cap C_j = A' \cap C_j ~~and~~ A \cap C_{j+1} \neq A' \cap C_{j+1}.\] Using \(|A \cap C_{j+1}| = |A' \cap C_{j+1}| = k\), it follows that there exists an element \(r \in (A \cap C_{j+1}) \setminus A'\). By the definition of \(\pi\), the preimage of \(C_{j+1}\) under \(\pi\) consists of the \(k\) elements of \(A \cap C_{j+1}\), which are mapped to those of \(B \cap C_{j+1}\), and the \(k\) elements of \(C_j \setminus A\), which are mapped to those of \(C_{j+1} \setminus B\). Therefore, the fact that \(r \in (A \cap C_{j+1}) \setminus A'\) implies that \(\pi(r) \in (B \cap C_{j+1}) \setminus \pi(A')\). Further, since \(A \cap C_j = A' \cap C_j\), it follows that \(C_j \setminus A = C_j \setminus A'\), which by \(\pi(C_j \setminus A) = C_{j+1} \setminus B\) implies that the set \(\pi(A')\) includes no element of \(C_{j+1} \setminus B\), hence \((\pi(A') \cap C_{j+1}) \subseteq (B \cap C_{j+1})\). Consequently, we obtain that \((\pi(A') \cap C_{j+1}) \subseteq (B \cap C_{j+1}) \setminus \{\pi(r)\}\), implying that \(|\pi(A') \cap C_{j+1}| \leq k-1\). However, by \((A',B') \in {\cal F}\), we have \(|B' \cap C_{j+1}| = k\), yielding that \(\pi(A') \neq B'\), as claimed.
Equipped with Theorem 3, we obtain the following lower bound on \(m(n)\).
Corollary 1. For all positive integers \(k\) and \(n\) with \(n \geq 2k\), it holds that \[m(n) \geq {\binom{2k}{k}}^{2 \cdot \lfloor n/(2k) \rfloor -1}.\]
For integers \(k\) and \(n\) with \(n \geq 2k\), let \(n'\) denote the largest multiple of \(2k\) not exceeding \(n\). We clearly have \(m(n) \geq m(n')\), as any setwise distinguishable family of permutations of \([n']\) can be transformed into a setwise distinguishable family of permutations of \([n]\) with the same size, by fixing the elements of \([n] \setminus [n']\) under all permutations. Combining Theorem 3 with Lemma 1, we obtain that \[m(n) \geq m(n') \geq {\binom{2k}{k}}^{n'/k-1} = {\binom{2k}{k}}^{2 \cdot \lfloor n/(2k) \rfloor-1},\] so we are done.
The following statement summarizes our upper and lower bounds on \(m(n)\) and confirms Theorem 1. Here and throughout, all logarithms are in base \(2\).
Theorem 4. There exists a constant \(c > 0\) such that for all positive integers \(n\), it holds that \[2^{2n-c \cdot (n \log n)^{1/2}} \leq m(n) \leq 2^{2n-(\log n)/2}.\]
For the upper bound on \(m(n)\), apply Lemma 2 to obtain that \(m(n) < \binom{2n}{n} \leq \frac{2^{2n}}{\sqrt{n}}\). For the lower bound, let \(n\) be a positive integer, and let \(k = \lfloor (n \log n)^{1/2} \rfloor\). We may assume that \(n\) is sufficiently large, and thus \(k \geq 1\) and \(n \geq 2k\), as smaller values of \(n\) can be handled by an appropriate choice for the constant \(c\) using \(m(n) \geq 1\). By Corollary 1, we obtain that \[\begin{align} m(n) & \geq & {\binom{2k}{k}}^{2 \cdot \lfloor n/(2k) \rfloor -1} \geq {\binom{2k}{k}}^{2 \cdot (n/(2k) -1) -1} \geq \bigg ( \frac{2^{2k}}{2 \sqrt{k}} \bigg )^{n/k-3} \\ & = & 2^{(2k-(\log k)/2-1) \cdot (n/k-3)} \geq 2^{2n-6k-(n\log k)/(2k)-n/k} = 2^{2n - \Theta((n \log n)^{1/2})}. \end{align}\] This completes the proof.
We conclude this section by highlighting a limitation of a natural approach to constructing setwise distinguishable families of permutations of \([n]\). Such a family can be obtained from a collection \(\{(A_i,B_i)\}_{i \in [m]}\) of \(m\) pairs of subsets of \([n]\) with the property that for all \(i,j \in [m]\), it holds that \(|A_i \cap A_j| = |B_i \cap B_j|\) if and only if \(i=j\). Indeed, any permutation \(\pi_i\) of \([n]\) that maps \(A_i\) to \(B_i\) necessarily satisfies \(\pi_i(A_j) \neq B_j\) for every \(j \in [m] \setminus \{i\}\), as otherwise it would follow that \[|A_i \cap A_j| = |\pi_i(A_i \cap A_j)| = |\pi_i(A_i) \cap \pi_i(A_j)| = |B_i \cap B_j|,\] contradicting the prescribed intersection property. This yields, by Lemma 1, a setwise distinguishable family of size \(m\). For example, by fixing all sets \(A_i\) to the same subset of \([n]\) of size \(\lfloor n/2 \rfloor\) and varying \(B_i\) over all subsets of the same size, one obtains a collection of \(\binom{n}{\lfloor n/2 \rfloor}\) pairs with the desired property. The following result shows, however, that no larger such collection exists. Its proof is inspired by the classic probabilistic argument underlying Sperner’s theorem (see, e.g., [20]).
Proposition 5. For positive integers \(m\) and \(n\), let \(\{(A_i,B_i)\}_{i \in [m]}\) be a collection of \(m\) pairs of subsets of \([n]\) such that for all \(i,j \in [m]\), it holds that \[|A_i \cap A_j| = |B_i \cap B_j| ~~~if and only if~~~i=j.\] Then \[m \leq \binom{n}{\lfloor n/2 \rfloor}.\]
Let \(\{(A_i,B_i)\}_{i \in [m]}\) be a collection of \(m\) pairs of subsets of \([n]\) as in the statement. It follows that \(|A_i|=|B_i|\) for all \(i \in [m]\). Let \(\pi\) be a permutation of \([n]\) chosen uniformly at random. For each \(i \in [m]\), let \(E_i\) denote the event that \(\pi(A_i) = B_i\). Since \(\pi(A_i)\) is uniformly distributed over all subsets of \([n]\) of size \(|A_i|\), we have \({\Pr_{}\left[ {E_i} \right]} = 1/{\binom{n}{|A_i|}}\). We claim that the events \(E_i\) with \(i \in [m]\) are pairwise disjoint. Indeed, suppose that \(E_i\) and \(E_j\) both occur, so that \(\pi(A_i) = B_i\) and \(\pi(A_j)=B_j\). Since \(\pi\) is a permutation of \([n]\), this implies that \(\pi(A_i \cap A_j) = \pi(A_i) \cap \pi(A_j) = B_i \cap B_j\), which in turn implies that \(|A_i \cap A_j| = |B_i \cap B_j|\), and therefore \(i=j\). We conclude that \[\begin{align} \label{eq:E95i} 1 \geq {\Pr_{}\left[ {\bigvee_{i =1}^{m}{E_i}} \right]} = \sum_{i=1}^{m}{{\Pr_{}\left[ {E_i} \right]}} = \sum_{i=1}^{m}{\frac{1}{\binom{n}{|A_i|}}} \geq m \cdot \frac{1}{\binom{n}{\lfloor n/2 \rfloor}}, \end{align}\tag{1}\] where the first equality holds because the events \(E_i\) are pairwise disjoint, and the last inequality holds because \(\binom{n}{k} \leq \binom{n}{\lfloor n/2 \rfloor}\) for all \(0 \leq k \leq n\). Rearranging 1 yields that \(m \leq \binom{n}{\lfloor n/2 \rfloor}\), completing the proof.
In this section, we employ our construction of setwise distinguishable families of permutations to obtain improved lower bounds on the kernel complexity of coloring problems parameterized by the vertex-deletion distance to split graphs, thereby proving Theorem 2. We first collect a few related definitions and concepts.
A parameterized problem is a set \(Q \subseteq \Sigma^* \times \mathbb{N}\) for some finite alphabet \(\Sigma\). A kernelization (or simply a kernel) for \(Q\) is an algorithm that, given an instance \((x,k) \in \Sigma^* \times \mathbb{N}\), returns in time polynomial in \(|x|+k\) an instance \((x',k') \in \Sigma^* \times \mathbb{N}\), such that \((x,k) \in Q\) if and only if \((x',k') \in Q\), and such that \(|x'|+k' \leq h(k)\) for some computable function \(h:\mathbb{N}\to \mathbb{R}\). The function \(h\) is called the size of the kernel. For an in-depth introduction to the area of kernelization, the reader is referred to [12].
For a positive integer \(q\), a \(q\)-coloring of a graph \(G=(V,E)\) is a function \(c: V \to [q]\), which assigns a color \(c(v)\) to each vertex \(v \in V\). The coloring \(c\) of \(G\) is called proper if it satisfies \(c(u) \neq c(v)\) for every edge \(\{u,v\} \in E\). For a list function \(L: V \to {\cal P}([q])\), a proper list coloring of the pair \((G,L)\) is a proper \(q\)-coloring \(c: V \to [q]\) of \(G\) satisfying \(c(v) \in L(v)\) for all \(v \in V\). For a fixed integer \(q\), the \(q\textrm{\mathrm{\small -Coloring}}\) problem asks whether a given graph \(G\) is \(q\)-colorable, and the \(q\textrm{\mathrm{\small -List Coloring}}\) problem asks whether a given pair \((G,L)\), consisting of a graph \(G=(V,E)\) and a list function \(L:V \to {\cal P}([q])\), admits a proper list coloring. A sub-instance of \((G,L)\) is an instance obtained from \((G,L)\) by removing a subset of the vertex set of \(G\) and restricting \(L\) to the remaining vertices. A \(\mathsf{NO}\) instance of \(q\textrm{\mathrm{\small -List Coloring}}\) is called irreducible if removing any vertex results in a \(\mathsf{YES}\) sub-instance.
For a positive integer \(q\) and for a graph family \({\cal G}\), the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \({\cal G}+ k\mathrm{v}\) graphs is the parameterized problem with parameter \(k\) that, given a graph \(G=(V,E)\) and a set \(X \subseteq V\) of size \(k\) whose removal from \(G\) gives a graph in \({\cal G}\), asks to decide whether \(G\) is \(q\)-colorable. The following theorem, proved by Jansen and Kratsch [14] using machinery developed by Dell and van Melkebeek [21], shows that conditional lower bounds on the kernel complexity of this problem can be derived from irreducible \(\mathsf{NO}\) instances of the \((q-2)\textrm{\mathrm{\small -List Coloring}}\) problem with graphs from \({\cal G}\).
Theorem 6 ([14]). Let \({\cal G}\) be a graph family closed under disjoint union, and let \(q \geq 3\) be a positive integer such that there exists an irreducible \(\mathsf{NO}\) instance of \((q-2)\textrm{\mathrm{\small -List Coloring}}\) with a graph from \({\cal G}\) on \(t \geq 3\) vertices. Then, for any real \(\varepsilon>0\), the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \({\cal G}+ k\mathrm{v}\) graphs admits no kernel of size \(O(k^{t-\varepsilon})\), and thus no kernel with \(O(k^{(t-\varepsilon)/2})\) vertices, unless \(\mathsf{NP}\subseteq \mathsf{coNP/poly}\).
A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. Let \(\mathrm{\small Split}\) denote the family of all split graphs, and let \(\cup \mathrm{\small Split}\) denote the family of all graphs whose connected components are members of \(\mathrm{\small Split}\). The family \(\cup \mathrm{\small Split}\) is clearly closed under disjoint union.
The following theorem produces an irreducible \(\mathsf{NO}\) instance of the \(q\textrm{\mathrm{\small -List Coloring}}\) problem on split graphs, surpassing the number of vertices achieved in [14].
Theorem 7. For all positive integers \(k\) and \(q\) with \(q \geq 2k\), there exists an irreducible \(\mathsf{NO}\) instance \((G,L)\) of \(q\textrm{\mathrm{\small -List Coloring}}\), where \(G\) is a split graph on at least \[{\binom{2k}{k}}^{2 \cdot \lfloor q/(2k) \rfloor-1}\] vertices. Therefore, there exists a constant \(c>0\) such that for all positive integers \(q\), there exists such an instance on at least \(2^{2q-c \cdot (q \log q)^{1/2}}\) vertices.
For the first part of the theorem, let \(k\) and \(q\) be positive integers satisfying \(q \geq 2k\). We may assume without loss of generality that \(2k\) divides \(q\), since otherwise, one can apply the result with \(q\) replaced by the largest multiple of \(2k\) not exceeding it, yielding a valid instance of \(q\textrm{\mathrm{\small -List Coloring}}\) that satisfies the stated bound on the number of vertices. Under this assumption, let \(m = {\binom{2k}{k}}^{q/k-1}\), and apply Theorem 3 to obtain a collection \(\{(A_i,B_i)\}_{i \in [m]}\) of \(m\) pairs of subsets of \([q]\), each of size \(q/2\), such that
for every permutation \(\pi:[q] \to [q]\) there exists an \(i \in [m]\) such that \(\pi(A_i) = B_i\), and
for every \(i \in [m]\) there exists a permutation \(\pi_i:[q] \to [q]\) such that for all \(j \in [m]\), it holds that \(\pi_i(A_j) = B_j\) if and only if \(i = j\).
Let \(C = \cup_{i \in [m]}{A_i} \subseteq [q]\). We define a graph \(G=(V,E)\) on the vertex set \(V = C \cup \{v_1, \ldots, v_m\}\), where the vertices of \(C\) are pairwise adjacent, and for each \(i \in [m]\), the vertex \(v_i\) is adjacent to the vertices of \(A_i \subseteq C\). Clearly, \(G\) is a split graph, as \(C\) forms a clique, and \(\{v_1, \ldots, v_m\}\) forms an independent set. Furthermore, the number of vertices in \(G\) satisfies \(|V| \geq m = {\binom{2k}{k}}^{q/k-1}\), which matches the desired bound assuming that \(2k\) divides \(q\). We define a list function \(L:V \to {\cal P}([q])\) as follows. For each \(r \in C\), let \(L(r)=[q]\), and for each \(i \in [m]\), let \(L(v_i) = B_i \subseteq [q]\). It remains to show that \((G,L)\) is an irreducible \(\mathsf{NO}\) instance of the \(q\textrm{\mathrm{\small -List Coloring}}\) problem.
We first show that \((G,L)\) is a \(\mathsf{NO}\) instance of \(q\textrm{\mathrm{\small -List Coloring}}\). Let \(c:V \to [q]\) be a coloring of \(G\) satisfying \(c(v) \in L(v)\) for all \(v \in V\). We show that \(c\) is not proper. If \(c\) assigns the same color to two distinct vertices in the clique \(C\), then it is clearly not proper. Otherwise, there exists a permutation \(\pi:[q] \to [q]\) that agrees with \(c\) on the vertices of \(C\), meaning that \(\pi(r) = c(r)\) for all \(r \in C\). By Item [itm:195NO] above, there exists an \(i \in [m]\) such that \(\pi(A_i) = B_i\), and thus \(c(A_i)=B_i\). However, the vertex \(v_i\) is adjacent in \(G\) to all vertices of \(A_i \subseteq C\), and its color \(c(v_i)\) lies in \(L(v_i) = B_i\). Therefore, there exists a vertex \(r \in A_i\) with \(c(r)=c(v_i)\), showing that \(c\) is not proper, as desired.
We next show that removing any vertex from \(G\) yields a \(\mathsf{YES}\) sub-instance of \((G,L)\) for the \(q\textrm{\mathrm{\small -List Coloring}}\) problem. Consider first an instance obtained from \((G,L)\) by removing a vertex \(v_i\) for some \(i \in [m]\). By Item [itm:295NO] above, there exists a permutation \(\pi_i:[q] \to [q]\) such that for all \(j \in [m]\), it holds that \(\pi_i(A_j) = B_j\) if and only if \(i = j\). We define a coloring \(c\) of the vertices of \(V \setminus \{v_i\}\) as follows. For each vertex \(r \in C\), let \(c(r) = \pi_i(r)\). Since \(\pi_i\) is a permutation of \([q]\), the endpoints of every edge in the clique \(C\) are assigned distinct colors under \(c\). Next, for each \(j \in [m] \setminus \{i\}\), it holds that \(\pi_i(A_j) \neq B_j\), and thus \(c(A_j) \neq B_j\), which using \(|c(A_j)| = |A_j| = |B_j|\) implies that \(B_j \setminus c(A_j) \neq \emptyset\). This allows us to assign to the vertex \(v_j\) a color \(c(v_j)\) from its list \(L(v_j)=B_j\) that is not assigned by \(c\) to any vertex in its neighborhood \(A_j\). The obtained coloring \(c\) is proper and respects the list function \(L\), as required.
Finally, consider an instance obtained from \((G,L)\) by removing some vertex \(r \in C\). By the definition of \(C\), there exists an \(i \in [m]\) such that \(r \in A_i\). By the preceding paragraph, the instance obtained from \((G,L)\) by removing the vertex \(v_i\) admits a proper list coloring \(c\). Since \((G,L)\) is a \(\mathsf{NO}\) instance, this coloring must satisfy \(c(A_i) = B_i\), as otherwise, using \(|c(A_i)|= |A_i| = |B_i|\), it could be extended to a proper list coloring of the entire instance \((G,L)\). For the instance \((G,L)\) with the vertex \(r\) removed, we use the coloring \(c\) on the vertices of \(V \setminus \{r,v_i\}\) and assign the color \(c(r)\) to the vertex \(v_i\). Since \(r \in A_i\) and \(c(A_i) = B_i\), the color \(c(r)\) lies in \(L(v_i) = B_i\) and is absent from the neighborhood of \(v_i\) when \(r\) is removed, yielding a proper list coloring for the resulting sub-instance. This completes the proof of the first part of the theorem.
For the second part of the theorem, it may be assumed that \(q\) is sufficiently large, as for smaller values of \(q\) and for an appropriate choice of the constant \(c>0\), one may take a graph with a single vertex assigned an empty set of colors. Under this assumption, the result follows by applying the first part of the theorem with \(k = \lfloor (q \log q)^{1/2} \rfloor\). We omit the calculation, which is identical to the one in the proof of Theorem 4.
We complement Theorem 7 with the following simple upper bound on the size of any irreducible \(\mathsf{NO}\) instance of the \(q\textrm{\mathrm{\small -List Coloring}}\) problem on split graphs. It slightly improves the \(2^{2q}+q\) bound obtained in [14].
Proposition 8. For every positive integer \(q\), every \(\mathsf{NO}\) instance of the \(q\textrm{\mathrm{\small -List Coloring}}\) problem with a graph in \(\cup \mathrm{\small Split}\) has a \(\mathsf{NO}\) sub-instance on at most \(2^q \cdot \binom{q}{\lfloor q/2 \rfloor} + q\) vertices.
For a positive integer \(q\), let \((G,L)\) be a \(\mathsf{NO}\) instance of the \(q\textrm{\mathrm{\small -List Coloring}}\) problem, where \(G=(V,E)\) is a graph in the family \(\cup \mathrm{\small Split}\), and \(L:V \to {\cal P}([q])\) is a list function. We may assume that \(G\) belongs to \(\mathrm{\small Split}\), since otherwise, some connected component of \(G\) already induces a \(\mathsf{NO}\) sub-instance of \((G,L)\). It follows that there exists a partition \(V = C \cup I\) of the vertex set of \(G\) into a clique \(C\) and an independent set \(I\). If \(|C| \geq q+1\), then any \(q+1\) vertices of \(C\) induce a \(\mathsf{NO}\) sub-instance of \((G,L)\), so we are done. Otherwise, it holds that \(|C| \leq q\), and we associate with each vertex \(v \in I\) its neighborhood \(N(v) \subseteq C\). As long as there exist two distinct vertices \(v_1,v_2 \in I\) with \(N(v_1) = N(v_2)\) and \(L(v_1) \subseteq L(v_2)\), we remove the vertex \(v_2\) from the set \(I\) and from the graph \(G\). Such a removal results in a \(\mathsf{NO}\) sub-instance, because any color assignment to the vertex \(v_1\) also suits \(v_2\). At the end of this process, for each set \(A \subseteq C\), the collection of lists \(\{L(v) \mid v \in I,~N(v) = A\}\) forms an antichain, that is, it includes no two sets one containing the other, so by Sperner’s theorem [3], its size does not exceed \(\binom{q}{\lfloor q/2 \rfloor}\). Since the number of subsets of \(C\) is bounded by \(2^q\), we obtain that the total number of vertices in the produced \(\mathsf{NO}\) sub-instance of \((G,L)\) is at most \(2^q \cdot \binom{q}{\lfloor q/2 \rfloor} + |C| \leq 2^q \cdot \binom{q}{\lfloor q/2 \rfloor} + q\), so we are done.
We are now ready to prove Theorem 2, which asserts that there exists a function \(g: \mathbb{N}\to \mathbb{N}\) with \(g(q) = 2^{(2-o(1)) \cdot q}\), such that for every sufficiently large integer \(q\) and for any real \(\varepsilon>0\), the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \(\cup \mathrm{\small Split}+ k\mathrm{v}\) graphs does not admit a kernel of size \(O(k^{g(q)-\varepsilon})\) unless \(\mathsf{NP}\subseteq \mathsf{coNP/poly}\).
By Theorem 7, there exists a function \(g: \mathbb{N}\to \mathbb{N}\) with \(g(q) = 2^{(2-o(1)) \cdot q}\), such that for every integer \(q \geq 3\), there exists an irreducible \(\mathsf{NO}\) instance of \((q-2)\textrm{\mathrm{\small -List Coloring}}\) whose graph lies in the family \(\cup \mathrm{\small Split}\) and has at least \(g(q)\) vertices. Since \(\cup \mathrm{\small Split}\) is closed under disjoint union and \(g(q) \geq 3\) for every sufficiently large integer \(q\), we can apply Theorem 6 and obtain that for every such \(q\) and any real \(\varepsilon>0\), the \(q\textrm{\mathrm{\small -Coloring}}\) problem on \(\cup \mathrm{\small Split}+ k\mathrm{v}\) graphs does not admit a kernel of size \(O(k^{g(q)-\varepsilon})\) unless \(\mathsf{NP}\subseteq \mathsf{coNP/poly}\). The proof is now complete.
This paper investigates the maximum size \(m(n)\) of a setwise distinguishable family of permutations of \([n]\). Theorem 4 shows that for some constant \(c > 0\) and for all positive integers \(n\), it holds that \[2^{2n-c \cdot (n \log n)^{1/2}} \leq m(n) \leq 2^{2n-(\log n)/2}.\] These upper and lower bounds coincide up to the lower-order terms in the exponent. It would be intriguing to close the remaining gap.
Despite the purely combinatorial nature of the quantity \(m(n)\), our motivation for exploring it arose from parameterized complexity, specifically, in the study of the kernel complexity of graph coloring problems parameterized by the vertex-deletion distance to split graphs, addressed by Jansen and Kratsch [14]. Our construction of setwise distinguishable families of permutations allowed us to clarify the exponential growth rate of the degree of the polynomial kernel size of these problems as a function of the number of colors, assuming a standard complexity assumption. We also strengthened the conditional lower bounds on the kernel complexity of coloring problems parameterized by the vertex-deletion distance to other graph families considered in [14], namely, cochordal graphs and cographs. For these families, however, the gap to the best known upper bound remains substantial, and narrowing it constitutes a natural direction for further research.
We would like to thank Shoni Gilboa for fruitful discussions and the anonymous reviewers for useful feedback.
The Academic College of Tel Aviv-Yaffo, Tel Aviv, Israel.↩︎