Timeline for Minimizing the maximum degree of a set of sets
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 23, 2017 at 12:22 | answer | added | Włodzimierz Holsztyński | timeline score: 2 | |
| Mar 23, 2017 at 11:11 | comment | added | Dominic van der Zypen | Lovely example - if you post it as an answer, I'll vote it up | |
| Mar 23, 2017 at 11:09 | comment | added | monkeymaths | A simple example with $m = n/2 + 1$: For $n = 2k$ even, take as your ground-set $X$ the set of all points $(i,r)$ in the plane where $1 \leq i \leq k$ and $r \in \{ 0, 1 \}$. Take $\mathcal{C}$ as the set of all lines through at least two of these points. (1) Not all lie on a line (if $k \geq 2$). (2) Any two lie on a common line. (3) Any two lines have at most one common point. (4) Each point lies in $k+1$ lines. | |
| Mar 23, 2017 at 11:03 | vote | accept | Dominic van der Zypen | ||
| Mar 23, 2017 at 10:15 | answer | added | Włodzimierz Holsztyński | timeline score: 4 | |
| Mar 23, 2017 at 7:12 | comment | added | Dominic van der Zypen | If I understand your argument correctly, we get that $|{\cal C}| \geq n-1$, but how does it imply that the maximum degree of all the points is $\geq n-1$? (Probably I'm missing something) | |
| Mar 23, 2017 at 7:09 | comment | added | Pietro Majer | In the third assumption, any $\{x,y\}$ is included in one and only one set (and maybe in $\mathcal{C}$ there are some more sets that are singletons). It follows $m\ge n-1$,doesn't it? (no it doesn't :) ) | |
| Mar 23, 2017 at 7:03 | history | edited | Dominic van der Zypen | CC BY-SA 3.0 |
added 53 characters in body
|
| Mar 23, 2017 at 7:01 | comment | added | Dominic van der Zypen | Very nice - all these examples escaped me! - I was wondering, what happens if you add a 3rd condition to the 2 stated in the question: $|A\cap B| \leq 1$ for all $A\neq B\in{\cal C}$. -- Just edited the question accordingly | |
| Mar 23, 2017 at 6:58 | comment | added | Pietro Majer | what if we take $\mathcal{C}$ to be the three sets $\{1,2\}$, $[n]\setminus \{1 \}$ and $[n]\setminus\{2\}$? | |
| Mar 23, 2017 at 6:56 | comment | added | Dominic van der Zypen | Nice - can you put this as an answer? Or would it be better to delete the question entirely? | |
| Mar 23, 2017 at 6:32 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |