Timeline for Minimum covers of complete graphs by $4$-cycles
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 18, 2021 at 13:26 | comment | added | SagarM | Hi can anyone tell me how I can solve this problem for $3$-cycles or equivalently $3$-cliques ? | |
| Aug 29, 2017 at 10:16 | vote | accept | Ashot | ||
| S Aug 29, 2017 at 9:58 | history | edited | Tony Huynh | CC BY-SA 3.0 |
Grammatical corrections. Content and style preserved.; edited tags
|
| S Aug 29, 2017 at 9:58 | history | suggested | Peter Heinig | CC BY-SA 3.0 |
Grammatical corrections. Content and style preserved.
|
| Aug 29, 2017 at 9:53 | comment | added | Peter Heinig | Let me mention that the simplicial complex that is obtained by taking the down-closure of the hypergraph you are interested in is far from being a matroid (which is easy to see directly from the matroid exchange axiom). If it were a matroid, the edge covering number could easily be computed via Theorem 1.3 in this preprint of Aharoni, Berger, Kotlar, Ziv. (Please note that the authors write $\beta$ instead of $\rho$.) Yet, again, your simplicial complex is not a matroid. | |
| Aug 29, 2017 at 9:48 | review | Suggested edits | |||
| S Aug 29, 2017 at 9:58 | |||||
| Aug 29, 2017 at 9:18 | answer | added | Tony Huynh | timeline score: 6 | |
| Aug 29, 2017 at 9:05 | answer | added | Gerhard Paseman | timeline score: 1 | |
| Aug 29, 2017 at 8:51 | history | edited | Ashot | CC BY-SA 3.0 |
added 290 characters in body
|
| Aug 29, 2017 at 8:14 | comment | added | Peter Heinig | The hypergraph $\mathcal{H}$ I defined above has precisely $m= \frac12 \binom{n}{4} (4-1)! = 3\binom{n}{4}$ edges, and it has $\alpha=1$ because any two distinct edges of the underlying graph are in a hyperedge of $\mathcal{H}$, so the Berger-Ziv-bound works out to a guarantee that there always is a cover of the kind you require of size at most $\lfloor \frac{(4-2)3\binom{n}{4} + 1}{4-1}\rfloor = \lfloor \frac{n(n-1)(n-2)(n-3)}{12} + \frac13 \rfloor$. While this may be non-obvious upper bound, it's too large. E.g. for $n=5$ it gives $10$, while you gave a covering by $3$ four-circuits. | |
| Aug 29, 2017 at 7:42 | comment | added | Peter Heinig | I take it that your question is really for the precise $\rho(\mathcal{H})$ defined in my comment, as a function of $n$, so this is not an answer, yet a very relevant comment: Berger and Ziv proved that for every finite hypergraph $\mathcal{H}$ with rank $r$ and $m$ edges and independence number $\alpha$, we have $\rho(\mathcal{H})\leq\frac{(r-2)m+\alpha}{r-1}$. | |
| Aug 29, 2017 at 7:22 | comment | added | Peter Heinig | Re 'edge cover': you can remember this by way of the following joke that I once heard: graph-theorists call 'book covers' 'paper covers'. (I.e., the noun modifier gives not the thing-to-be-covered, rather the thing-that-the-cover-is-made-of.) | |
| Aug 29, 2017 at 7:20 | comment | added | Peter Heinig | To put this question into the usual contemporary conceptual framework: all the OP is asking for is precisely this: the edge covering number $\rho(\mathcal{H})$ of the hypergraph $\mathcal{H}$ whose ground-set is the edge-set of the complete graph $K_n$ and whose set of hyperedges is equal to the set of edge-sets of all 4-circuits in $K_n$. Please do not be confused by the (traditional) technical term 'edge covering number': this does not refer to covering the edges, rather, the term, regrettably very widespread, refers to a covering of the ground-set by hyperedges. | |
| S Aug 29, 2017 at 7:10 | history | suggested | Peter Heinig | CC BY-SA 3.0 |
Grammatical corrections. Content and style preserved.
|
| Aug 29, 2017 at 7:07 | review | Suggested edits | |||
| S Aug 29, 2017 at 7:10 | |||||
| Aug 29, 2017 at 7:01 | history | edited | Ashot | CC BY-SA 3.0 |
edited body
|
| Aug 29, 2017 at 6:59 | comment | added | Fedor Petrov | You mean, if $n\ge 4$, not 3? | |
| Aug 29, 2017 at 6:59 | history | edited | Ashot | CC BY-SA 3.0 |
added 4 characters in body
|
| Aug 29, 2017 at 6:48 | history | edited | Martin Sleziak | CC BY-SA 3.0 |
typo in the title
|
| Aug 29, 2017 at 6:20 | history | asked | Ashot | CC BY-SA 3.0 |