Timeline for Maximal induced cycles on $n$-clique graphs
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 1, 2015 at 9:03 | comment | added | Dominic van der Zypen | It was me that was a bit slow in understanding your answer. It makes perfect sense, thanks! | |
| Dec 1, 2015 at 9:02 | comment | added | Fedor Petrov | Sorry, I was maybe too concise yesterday (it is annoying to type formulae on the cellphone). | |
| Nov 30, 2015 at 19:55 | vote | accept | Dominic van der Zypen | ||
| Nov 30, 2015 at 15:54 | comment | added | Dominic van der Zypen | That would be quite elegant - thanks @BenBarber . So we still have that the length of the longest cycle in any $n$-clique graph (whether you use my a bit botched definition, or Ben's) is at most $3$? (I'm a bit slow in understanding Fedor's argument, sorry) | |
| Nov 30, 2015 at 15:22 | comment | added | Ben Barber | This question would surely be cleaner stated in terms of hypergraphs. You are asking for the longest induced cycle over all $n$-uniform hypergraphs in which every pair of edges shares precisely one vertex. Here induced cycle should mean a (cyclic) sequence of vertices such that each adjacent pair is contained in some edge, and no non-adjacent pairs are contained in any edge. | |
| Nov 30, 2015 at 15:08 | comment | added | Dima Pasechnik | in combinatorics people normally talk about partial linear spaces, whenever they have a subset system S on X such that any pair of points in X is in at most one subset in S. Your extra condition 3 makes S very degenerate... | |
| Nov 30, 2015 at 14:51 | comment | added | Dominic van der Zypen | Here's an example of a $5$-clique graph: Let $V = \{0\}\cup\{k\cdot 100 + i: k=1,\ldots,5 \text{ and } i=1,\ldots,4\}$. Set $S_k = \{0\}\cup \{k\cdot 100 + i:i=1,\ldots,4\}$, and define $E$ as in item 4 above. In this example of a $5$-clique graph, we have indeed no induced cycle with length $\leq 4$. | |
| Nov 30, 2015 at 14:35 | answer | added | Fedor Petrov | timeline score: 2 | |
| Nov 30, 2015 at 14:21 | comment | added | Wolfgang | For me it doesn't, sorry. Your condition 3 (was 2 before) should be removed, maybe. Or can you provide an example of a non trivial n-clique graph as you are imagining it? (and is it on purpose that the new condition 1 uses the same n as cardinality?) | |
| Nov 30, 2015 at 14:09 | history | edited | Dominic van der Zypen | CC BY-SA 3.0 |
added 42 characters in body
|
| Nov 30, 2015 at 14:09 | comment | added | Dominic van der Zypen | Sorry again for my notational slip-up... hope the question makes more sense now | |
| Nov 30, 2015 at 14:07 | history | undeleted | Dominic van der Zypen | ||
| Nov 30, 2015 at 9:37 | history | deleted | Dominic van der Zypen | via Vote | |
| Nov 30, 2015 at 9:37 | comment | added | Dominic van der Zypen | You are right - sorry! | |
| Nov 30, 2015 at 9:34 | comment | added | Wolfgang | In fact, I missed condition 2 which implies that all cliques have same size and thus the clique graph of $G$ (i.e. the "original" graph of my comment) must be a complete graph. Which means the problem is trivial, c(n)=3 for all n. Am I missing something? | |
| Nov 30, 2015 at 9:18 | comment | added | Wolfgang | If you take any graph with $n$ vertices, add a vertex on each edge and replace each vertex $v$ of the original graph with a clique $K_d$ (connecting the new vertices adjacent to it, where $d$ is the degree of $v$), isn't the result exactly an $n$-clique graph? And so its induced cycles correspond 1-1 to those of the original graph? | |
| Nov 30, 2015 at 9:07 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |