Return to Answer

The answer to Question 1 is negative. Let $G=\{\{1, \dots, N+1\}\}$ and $H$ consist of all subsets of $\{1, \dots, N+1\}$ of size $N$. If $K$ is a distinguisher for $G$ and $H$, then for each $i \in \{1, \dots, N+1\}$ there must be a set $A \in K$ such that $A \cap \{1, \dots, N+1\}=\{i\}$. Thus, $|K| \geq N+1$.

Here is a simple proof that the answer to Question 2 is also negative, even if all sets in $G$ and $H$ have size $3$. Colour the edges of $K_{m}^{(3)}$ (the complete 3-uniform hypergraph on $m$ vertices) red and blue such that there is no monochromatic $K_{N}^{(3)}$. By classic results on lower bounds of Ramsey numbers, we may take $m >2^{cN^2}$, where $c$ is a positive constant. Let $G$ be the set of red edges, and $H$ be the set of blue edges. Suppose there is a distinguisher $K$ of $G$ and $H$ with $|K| \leq N$. Since the atoms of $K$ also distinguish $G$ and $H$, there is a distinguisher $K'$ of $G$ and $H$ which is a partition of $[m]$ and $|K'| \leq 2^N$. By averaging, some set $A \in K'$ has at least $\frac{m}{2^N} > N$ vertices. Since there is no monochromatic $K_{N}^{(3)}$, there must be some red edge $R$ and some blue edge $B$ with $R \subseteq A$ and $B \subseteq R$. Since $K'$ is a partition of $[m]$, it follows that $K'$ does not distinguish $R$ and $B$, which is a contradiction.

The answer to Question 1 is negative. Let $G=\{\{1, \dots, N+1\}\}$ and $H$ consist of all subsets of $\{1, \dots, N+1\}$ of size $N$. If $K$ is a distinguisher for $G$ and $H$, then for each $i \in \{1, \dots, N+1\}$ there must be a set $A \in K$ such that $A \cap \{1, \dots, N+1\}=\{i\}$. Thus, $|K| \geq N+1$.

Here is a simple proof that the answer to Question 2 is also negative, even if all sets in $G$ and $H$ have size $3$. Colour the edges of $K_{m}^{(3)}$ (the complete 3-uniform hypergraph on $m$ vertices) red and blue such that there is no monochromatic $K_{N}^{(3)}$. By classic results on lower bounds of Ramsey numbers, we may take $m >2^{cN^2}$, where $c$ is a positive constant. Let $G$ be the set of red edges, and $H$ be the set of blue edges. Suppose there is a distinguisher $K$ of $G$ and $H$ with $|K| \leq N$. Since the atoms of $K$ also distinguish $G$ and $H$, there is a distinguisher $K'$ of $G$ and $H$ which is a partition of $[m]$ and $|K'| \leq 2^N$. By averaging, some set $A \in K'$ has at least $\frac{m}{2^N} > N$ vertices. Since there is no monochromatic $K_{N}^{(3)}$, there must be some red edge $R$ and some blue edge $B$ with $R \subseteq A$ and $B \subseteq A$. Since $K'$ is a partition of $[m]$, it follows that $K'$ does not distinguish $R$ and $B$, which is a contradiction.

The answer to Question 1 is negative. Let $G=\{\{1, \dots, N+1\}\}$ and $H$ consist of all subsets of $\{1, \dots, N+1\}$ of size $N$. If $K$ is a distinguisher for $G$ and $H$, then for each $i \in \{1, \dots, N+1\}$ there must be a set $A \in K$ such that $A \cap \{1, \dots, N+1\}=\{i\}$. Thus, $|K| \geq N+1$.

Here is a simple proof that the answer to Question 2 is also negative, even if all sets in $G$ and $H$ have size $3$. Colour the edges of $K_{m}^{(3)}$ (the complete 3-uniform hypergraph on $m$ vertices) red and blue such that there is no monochromatic $K_{N}^{(3)}$. Let $G$ be the set of red edges, and $H$ be the set of blue edges. By classic results on lower bounds of Ramsey numbers, we may take $m >2^{cN^2}$, where $c$ is a positive constant. Suppose there is a distinguisher $K$ of $G$ and $H$ with $|K| \leq N$. Since the atoms of $K$ also distinguish $G$ and $H$, there is a distinguisher $K'$ of $G$ and $H$ which is a partition of $[m]$ and $|K'| \leq 2^N$. By averaging, some set $A \in K'$ has at least $\frac{m}{2^N} > N$ vertices. Since there is no monochromatic $K_{N}^{(3)}$, there must be some red edge $R$ and some blue edge $B$ with $R \subseteq A$ and $B \subseteq R$. Since $K'$ is a partition of $[m]$, it follows that $K'$ does not distinguish $R$ and $B$, which is a contradiction.

The answer to Question 1 is negative. Let $G=\{\{1, \dots, N+1\}\}$ and $H$ consist of all subsets of $\{1, \dots, N+1\}$ of size $N$. If $K$ is a distinguisher for $G$ and $H$, then for each $i \in \{1, \dots, N+1\}$ there must be a set $A \in K$ such that $A \cap \{1, \dots, N+1\}=\{i\}$. Thus, $|K| \geq N+1$.

Here is a simple proof that the answer to Question 2 is also negative, even if all sets in $G$ and $H$ have size $3$. Colour the edges of $K_{m}^{(3)}$ (the complete 3-uniform hypergraph on $m$ vertices) red and blue such that there is no monochromatic $K_{N}^{(3)}$. By classic results on lower bounds of Ramsey numbers, we may take $m >2^{cN^2}$, where $c$ is a positive constant. Let $G$ be the set of red edges, and $H$ be the set of blue edges. Suppose there is a distinguisher $K$ of $G$ and $H$ with $|K| \leq N$. Since the atoms of $K$ also distinguish $G$ and $H$, there is a distinguisher $K'$ of $G$ and $H$ which is a partition of $[m]$ and $|K'| \leq 2^N$. By averaging, some set $A \in K'$ has at least $\frac{m}{2^N} > N$ vertices. Since there is no monochromatic $K_{N}^{(3)}$, there must be some red edge $R$ and some blue edge $B$ with $R \subseteq A$ and $B \subseteq R$. Since $K'$ is a partition of $[m]$, it follows that $K'$ does not distinguish $R$ and $B$, which is a contradiction.

The answer to Question 1 is negative. Let $G=\{\{1, \dots, N+1\}\}$ and $H$ consist of all subsets of $\{1, \dots, N+1\}$ of size $N$. If $K$ is a distinguisher for $G$ and $H$, then for each $i \in \{1, \dots, N+1\}$ there must be a set $A \in K$ such that $A \cap \{1, \dots, N+1\}=\{i\}$. Thus, $|K| \geq N+1$.

Here is a simple proof that the answer to Question 2 is also negative, even if all sets in $G$ and $H$ have size $3$. Colour the edges of $K_{m}^{(3)}$ (the complete 3-uniform hypergraph on $m$ vertices) red and blue such that there is no monochromatic $K_{N}^{(3)}$. Let $G$ be the set of red edges, and $H$ be the set of blue edges. By classic results on lower bounds of Ramsey numbers, we may take $m >2^{cN^2}$, where $c$ is a positive constant. Suppose there is a distinguisher $K$ of $G$ and $H$ with $|K| \leq N$. Since the atoms of $K$ also distinguish $G$ and $H$, there is a distinguisher $K'$ of $G$ and $H$ which is a partition of $[m]$ and $|K'| \leq 2^N$. By averaging, some set $A \in K'$ has at least $\frac{m}{2^N} > N$ elements. Thus, $A$ contains both a red edge $R$ and a blue edge $B$. It follows that $K'$ does not distinguish $R$ and $B$, which is a contradiction.

The answer to Question 1 is negative. Let $G=\{\{1, \dots, N+1\}\}$ and $H$ consist of all subsets of $\{1, \dots, N+1\}$ of size $N$. If $K$ is a distinguisher for $G$ and $H$, then for each $i \in \{1, \dots, N+1\}$ there must be a set $A \in K$ such that $A \cap \{1, \dots, N+1\}=\{i\}$. Thus, $|K| \geq N+1$.

Here is a simple proof that the answer to Question 2 is also negative, even if all sets in $G$ and $H$ have size $3$. Colour the edges of $K_{m}^{(3)}$ (the complete 3-uniform hypergraph on $m$ vertices) red and blue such that there is no monochromatic $K_{N}^{(3)}$. Let $G$ be the set of red edges, and $H$ be the set of blue edges. By classic results on lower bounds of Ramsey numbers, we may take $m >2^{cN^2}$, where $c$ is a positive constant. Suppose there is a distinguisher $K$ of $G$ and $H$ with $|K| \leq N$. Since the atoms of $K$ also distinguish $G$ and $H$, there is a distinguisher $K'$ of $G$ and $H$ which is a partition of $[m]$ and $|K'| \leq 2^N$. By averaging, some set $A \in K'$ has at least $\frac{m}{2^N} > N$ vertices. Since there is no monochromatic $K_{N}^{(3)}$, there must be some red edge $R$ and some blue edge $B$ with $R \subseteq A$ and $B \subseteq R$. Since $K'$ is a partition of $[m]$, it follows that $K'$ does not distinguish $R$ and $B$, which is a contradiction.