Timeline for Infinite "$T_1$"- hypergraphs
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 20, 2017 at 8:18 | answer | added | Dominic van der Zypen | timeline score: 0 | |
| Sep 18, 2017 at 14:25 | vote | accept | Dominic van der Zypen | ||
| Sep 18, 2017 at 13:44 | answer | added | Will Brian | timeline score: 3 | |
| Sep 18, 2017 at 13:21 | comment | added | Tobias Fritz | If you have a $T_0$ hypergraph, then you can make it $T_1$ by throwing in all the complements of all edges. Thus it is enough to answer the question in the case of $T_0$. Then just take $X$ to be the power set of $E$, where an edge $e$ 'contains' all those sets that is a member of. (To understand this construction better, it helps to think about the dual hypergraph, or to consider a hypergraph instead as a bipartite graph with $X$ on one side and $E$ on the other.) So we get $X = 2^E$, and this is clearly as large as $X$ can get for given $|E|$. | |
| Sep 18, 2017 at 12:13 | history | edited | Dominic van der Zypen | CC BY-SA 3.0 |
deleted 81 characters in body
|
| Sep 18, 2017 at 12:11 | comment | added | Dominic van der Zypen | It is indeed trivial for $X$ finite. Let $X = \{1,2,3,\ldots, 9\}$, arrange these points in a $3\times 3$ square and let $E$ consist of the $3$ "horizontal" lines (each containing 3 points) and the $3$ vertical lines (again each containing 3 points). Then $E$ has the $T_1$ property, and $|E| = 6 < 9 = |X|$. So it appears the question is interesting in the infinite only. Will edit accordingly. | |
| Sep 18, 2017 at 12:06 | comment | added | Dominic van der Zypen | Interesting comment, thanks @JoshuaErde . I wonder what things look like in the infinite! | |
| Sep 18, 2017 at 10:31 | comment | added | Joshua Erde | If you pick sets of size ~|X|/2 at random, then each pair of vertices is separated with probability about 1/2. So, if you pick lots of sets in this way (say |X|/2) then the probability any pair isn't separated is exponentially small, whereas the number of pairs is only quadratic in |X|. Hence, if |X| is large, the expected number of pairs which aren't separated is <1, and so by the first moment method there is some set of |X|/2 edges which separate all the pairs. This probably shows that a logarithmically small number of edges suffices. | |
| Sep 18, 2017 at 10:05 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |