Timeline for Perfect matching in a vertex-transitive hypergraph
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 3, 2012 at 18:04 | comment | added | domotorp | Now you caught me! I guess I meant that picking any 2 vertices from any 2 classes, you can map them into any 2 other vertices of the respective classes with an automorphism, but your construction is a good counterexample even for this, so just forget my comment... | |
| Apr 2, 2012 at 20:07 | comment | added | Seva | Sorry for my illiteracy, but what is "$2$-vertex-transitivity"? | |
| Apr 2, 2012 at 13:37 | comment | added | domotorp | Indeed. I think instead of inefficient you wanted to write insufficient. Now I wonder if 2-vertex-transitivity, or in general r-1-vertex-transitivity is sufficient. | |
| Apr 2, 2012 at 12:40 | comment | added | Seva | I appended an answer at the end of my original post. | |
| Apr 2, 2012 at 7:12 | comment | added | domotorp | Oh, I have no noticed you ask for vertex transitive... I don't know anything about that for hypergraphs. For non-empty graphs with an even number of vertices you must have a perfect matching in this case, this follows from the Gallai-Edmonds Decomposition. Do you have a counterexample for hypergraphs? | |
| Apr 2, 2012 at 7:09 | history | edited | domotorp | CC BY-SA 3.0 |
added first line
|
| Mar 31, 2012 at 18:49 | comment | added | Seva | One more remark: there is no necessary and sufficient condition which is easy to check computationally. However, there still can possibly exist a "logically simple" and useful condition! | |
| Mar 31, 2012 at 18:36 | comment | added | Seva | And, by the way: does the problems remain NP-complete if we confine to vertex-transitive hypergraphs? | |
| Mar 31, 2012 at 18:31 | comment | added | Seva | Thanks! I was unaware of the three-dimensional matching problem. As to the second part of your answer, the degree assumptions are exactly what I had in mind mentioning "unreasonable conditions"... | |
| Mar 31, 2012 at 14:10 | history | answered | domotorp | CC BY-SA 3.0 |