2
$\begingroup$

A new mathematical approach to quantum physics via graphs was found recently, see this paper for more details. It particular, it refers to papers by Anton Zeilinger, a Nobel laureate in physics of 2022. The paper contains several related mathematical questions. The first of them was posted at MathOverflow by Mario Krenn, who has also announced a 3000 Euro award on its solution. Unfortunately, as far as I know, the question resists all known mathematical approaches.

Even a degenerated case of this question remains open. But it has a combinatorial relaxation, which looks as a puzzle. So I decided to ask Puzzling.SE community for help.

For which even number $n\ge 4$ and natural number $m\ge 2$ does there exist the following configuration?

(Now I am especially interesting in the case of any $n\ge 14$ and $m=3$, see below.)

There is a set $V$ of size $|V|=n$ and $m$ distinct colors. For each of the colors we have a family of nonempty subsets $U$ of $V$ of even size $|U|$, colored in this color. Note that some subsets $U$ of $V$ can belong to several families.

It is required that there is no partition of $V$ into at least two its subsets of distinct colors.

Moreover, each family $\mathcal S$ of all monochromatic sets satisfies the following conditions:

  • Condition 0. $V\in\mathcal S$.

  • Condition 1. For any set $U\in\mathcal S$ with $|U|\ge 4$ and any element $v\in U$ there exists an element $u\in U$ such that both sets $\{v,u\}$ and $U\setminus\{v,u\}$ belong to $\mathcal S$.

  • Condition 2. A subset $U$ of $V$ belongs to $\mathcal S$ provided for some element $v\in U$ there exists a unique element $u\in U$ such that both sets $\{v,u\}$ and $U\setminus\{v,u\}$ belong to $\mathcal S$.

Examples:

  • The configuration exists for $n=4$ and $m=3$. Indeed, let $V=\{1,2,3,4\}$, the red sets be $\{1,2\}$, $\{3,4\}$, and $\{1,2,3,4\}$, the blue sets be $\{1,3\}$, $\{2,4\}$, and $\{1,2,3,4\}$, and the green sets be $\{1,4\}$, $\{2,3\}$, and $\{1,2,3,4\}$.

  • The configuration exists for any even $n\ge 4$ and $m=2$. Indeed, let $V=\{1,\dots,n\}$, the red sets be nonempty unions of some sets among $\{1,2\},\{3,4\},\dots \{n-1,n\}$, and the blue sets be nonempty unions of some sets of the family $\{2,3\},\{4,5\},\dots \{n-2,n-1\},\{n,1\}$.

Our try. It is easy to show that if the configuration exists then $m\le n-1$. On the other hand, initially I thought that the configuration can exist for some small $n>4$ and $m=3$. I convinced Alexander Wolff to give related project to his student Aaron Neugebauer. Surprisingly, after a few years of SAT-solver cluster calculations (if correct) we showed that for $6\le n\le 12$ the configuration exists only for $m=2$. The ideal case would be to prove that there exists no configuration with $m=3$ for any $n\ge 4$, but it looks too good to be true.

$\endgroup$
3
  • $\begingroup$ Does condition 2 also require $|U|\ge 4$? Otherwise, the two-element sets in your example with n=4 and m=3 don’t satisfy condition 2. Or perhaps I misunderstood. $\endgroup$ Commented Sep 1 at 10:52
  • $\begingroup$ @Pranay Condition 2 is sufficient for $U$ to belong to $\mathcal S$. But the case $|U|=2$ is degenerated, because for it if $\{v,u\}\subset U$ then $\mathcal S\ni\{v,u\}=U$ (although $\mathcal S\not\ni\varnothing=U\setminus \{v,u\}$). $\endgroup$ Commented Sep 1 at 11:06
  • $\begingroup$ It’s the empty set that’s bugging me. Can you simply add the empty set to S (like V in condition 0) to avoid this issue? Or maybe it’s the wording of the condition that makes me feel like you are talking about a necessary condition, not sufficient. But thanks for clarifying that it’s the latter. $\endgroup$ Commented Sep 1 at 11:09

0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.