Timeline for Counting triples family with double shared elements
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2018 at 19:24 | vote | accept | Mohammad Al-Turkistany | ||
| Aug 28, 2018 at 19:24 | comment | added | Gerhard Paseman | What is 237 intersect 251? Gerhard "Not Sure It's A Counterexample" Paseman, 2018.08.28. | |
| Aug 28, 2018 at 18:46 | comment | added | Mohammad Al-Turkistany | See the counterexample in the edited post | |
| Jun 30, 2018 at 9:29 | vote | accept | Mohammad Al-Turkistany | ||
| Aug 28, 2018 at 18:45 | |||||
| Jun 29, 2018 at 20:32 | comment | added | Gerhard Paseman | Also this is one instance where you can prove F does not admit an exact subcover. Gerhard "Hopefully That About Covers It" Paseman, 2018.06.29. | |
| Jun 29, 2018 at 20:29 | comment | added | Gerhard Paseman | Since F is essentially unique, I have no idea what NP completeness for this family F would mean. Gerhard "Perhaps You Mean Something Different?" Paseman, 2019.06.29. | |
| Jun 29, 2018 at 20:08 | comment | added | Mohammad Al-Turkistany | Nice, Do you know whether Exact cover by 3-sets problem is NP-complete for this family of triples? | |
| Jun 29, 2018 at 3:15 | comment | added | James | I created a new post, with a picture, to not crowd out your reasoning. | |
| Jun 29, 2018 at 1:56 | comment | added | Gerhard Paseman | I normally do not encourage edits to my posts. In this case though, you might add (bracketed by "Edit by James" or something like that) your interpretation below the main part of the post (and above the signature, please). I think it is good to have a geometric interpretation to aid the combinatorial version, which can be hard to visualize. Joseph O'Rourke does it as a separate answer, so you could do it that way if you prefer. Gerhard "Sometimes Pictures Make A Proof" Paseman, 2018.06.28. | |
| Jun 29, 2018 at 1:50 | comment | added | James | These two geometric conditions do in fact imply that every vertex belongs to one of a collection of disjoint tetrahedrons (as you pointed out). Your formula $(4k)!/(k!(4!)^k)$ could be obtained by taking k disjoint tetrahedrons, looking at all labelings of those tetrahedrons, and quotienting out by symmetries among and within each tetrahedron. All this is just to give a geometric interpretation of this question. | |
| Jun 29, 2018 at 1:46 | comment | added | James | I thought I had a counter-example to your claim "the union cannot contain five elements", but realized I was mistaken, so have deleted that response! I'll post the correct part of my response here: We can think of each triple as defining a triangle (2-simplex).The condition |T∩S|∈{0,2} means any two simplices are either disjoint or share exactly one edge. The condition that every element is in exactly three triples says that every vertex has exactly three simplices attached to it. | |
| Jun 29, 2018 at 0:06 | history | edited | Gerhard Paseman | CC BY-SA 4.0 |
deleted 4 characters in body
|
| Jun 29, 2018 at 0:00 | history | answered | Gerhard Paseman | CC BY-SA 4.0 |