Dominik Leitner, who’s generous contribution made these annoucements possible.
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.
Now, due to a very generous contribution from my friend Dominik Leitner, I am able to announce the following:
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 January 2022.
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.
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.
Questions and Comments
For any questions and clarifications, please send me an e-Mail.
