We discovered a new form of vertex colors of graphs (inherited directly form edge-colorings of perfect matchings) in the study of quantum physics questions.
Several new pure graph theoretical questions emerged, and I believe that their answer could lead to exciting insights on the potential of resources of quantum interference.
I have described the question in detail in a youtube video, mathoverflow question, and a contribution to the proceedings of 2nd Croatian Combinatorial Days (arXiv version), and was described in detail by Dustin Mixon.
1) 3.000 Euro Reward
We offer a 3.000 Euro reward for the first solution of our conjecture (either proof or counterexample) (mathoverflow question, Dustin Mixon’s blog, youtube (see Clarification below video), Question1 here):
Update January 2021: Not only solutions to Question2, but also counter-examples to the conjecture will be awarded the reward.
The solution has to appear in a respected, peer-reviewed journal (or for counterexamples, there needs to be a way to confirm them, for instance via software). The problem can be concisely formulated in the language of graph theory and combinatorial equation systems.
2) 1.000 Euro Best-Paper Award
We offer a 1.000 Euro award for the best paper which investigates inherited vertex colors of graphs, derives new results or connections. The deadline will be March 2023.
- Best-Paper Award 2022:
L. Sunil Chandran, Rishikesh Gajjala: Perfect Matchings and Quantum Physics: Progress on Krenn’s Conjecture [youtube]
for the confirmation of the conjecture for large classes of simple graphs, as well as the introduction and disprove of a natural generalisation.
Rules: The paper needs to be correct (peer-reviewed in a serious journal or proceedings, and/or I need to able to understand the results) and the results should be non-trivial/obvious. At the deadline, i will ask for recommendations by experts. In case of two interesting papers, the award could be splitted.
Known special cases
- [April 2017]: For real, positive weights, it follows from Bogdanov’s lemma that monochromatic weighted graphs cannot exist for (n=4,d>3) and (n>=6,d>2).
- [September 2021]: For monochromatic edges, we proved using SAT solvers that (n=6,d>=3) and (n=8, d>=4) monochromatic weighted graphs don’t exist.
- [February 2022]: For monochromatic edges, without multi-edges, a monochromatic graph cannot exist for d=n-2 (even n>=6), due to Chandran & Gajjala.
References
- Dustin Mixon’s blog post reformulated and generalized the question in a beautiful way.
- Questions on the Structure of Perfect Matchings inspired by Quantum Physics – here, together with my colleages Xuemei Gu and Daniel Soltesz, we formalize the ideas of bi-chromatic, edge-colored weighted graph, and the concept of inherited vertex coloring, together with several examples, and a number of noteworthy open question on the topic.
- My mathoverflow question Vertex Coloring inherited from Perfect Matchings (motivated by Quantum Physics) where I explain the idea of inherited vertex coloring and particularily the question for the reward more compactly.
- My mathoverflow question Has this notion of vertex-coloring of graphs been studied? where I explain the concept of bi-chromatic edge-colored graphs and inherited vertex coloring more compactly.
- A post by Ilya Bogdanov, which answeres the question of the reward for the special case of graphs with all weights being real and positive.
- How we use related graph-theoretical techniques in artificial intelligence algorithms.
- Using SAT solvers, we proof a few special cases of the conjecture (specifically for graphs with only monochromatic edges).
Questions and Comments
For any questions and clarifications, please send me an e-Mail.
Mario Krenn 