Timeline for Low rate c-uniform pairwise intersecting set systems
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 20, 2011 at 20:22 | vote | accept | CommunityBot | ||
| May 20, 2011 at 20:22 | history | bounty ended | TMM | ||
| May 20, 2011 at 19:59 | answer | added | Gerhard Paseman | timeline score: 0 | |
| May 17, 2011 at 20:04 | answer | added | Thomas Kalinowski | timeline score: 2 | |
| May 17, 2011 at 18:28 | answer | added | Clinton Conley | timeline score: 2 | |
| May 17, 2011 at 15:13 | comment | added | Clinton Conley | For every $c$ it's not too hard to build a corresponding $\mathcal{S}$ with $r(\mathcal{S})$ approximately equal to $4/c$. The exact value for the construction I have in mind depends a tiny bit on the parity. So I guess you should aim to do better than that. | |
| May 17, 2011 at 12:09 | history | edited | TMM | CC BY-SA 3.0 |
deleted 14 characters in body
|
| May 17, 2011 at 12:07 | comment | added | TMM | Thanks kali, that was easier than I thought (why didn't I think of that?). At least this gives an upper bound on $f(c)$, for prime powers $c - 1$. For the application I'm using it for it is most important to show that $f(c)$ becomes really small as $c$ becomes large, so such an upper bound (even with gaps) would already be a somewhat nice result. But of course in general it is an interesting question whether we can prove that $f(c)$ is minimized when $S$ is a proj. plane (and whether it is true). For $c - 1 \neq p^m$ I'm not sure how to continue, or what $f(c)$ should be. | |
| May 17, 2011 at 1:20 | comment | added | Thomas Kalinowski | I'm not quite sure what "over $\mathbb{F}_2$ should mean, but the rate of a projective plane of order c-1 is indeed $c/(c^2-c+1)$. To see this let $V$ be any subset of the point set. We just have to show that there is a line $L$ such that $|V\cap L|/|V|\leqslant c/(c^2-c+1)$. Now suppose that's not the case, i.e. $|V\cap L|> c|V|/(c^2-c+1)$ for every line $L$. Summing over the lines we obtain $$\sum_{L}|V\cap L|>c|V|.$$ But on the left hand side every element of $V$ is counted $c$ times, so the LHS is equal to $c|V|$, contradiction. By th way, what's your plan for $c$'s without proj. planes? | |
| May 14, 2011 at 23:50 | history | edited | TMM | CC BY-SA 3.0 |
added 4 characters in body
|
| May 13, 2011 at 19:31 | history | bounty started | TMM | ||
| May 11, 2011 at 9:49 | history | edited | TMM | CC BY-SA 3.0 |
deleted 1 characters in body
|
| May 10, 2011 at 21:26 | history | edited | TMM | CC BY-SA 3.0 |
added 1017 characters in body
|
| May 9, 2011 at 12:25 | comment | added | Clinton Conley | I don't know if this is at all useful (and it's possibly well known?), but you can in some sense uniformly finitize the problem. If $\mathcal{S}$ is a $c$-uniform pairwise intersecting set system and some $u \in U$ is in more than $c^{c-1}$ elements of $\mathcal{S}$, then $r(\mathcal{S}) \geq 1/(c-1)$ which (if my arithmetic is correct) is already above the bound given by the projective plane of order $(c-1)$. This gives explicit finite bounds on $|U|$ and $|\mathcal{S}|$ (in terms of $c$) for potential counterexamples. | |
| May 9, 2011 at 8:41 | answer | added | Thomas Kalinowski | timeline score: 0 | |
| May 6, 2011 at 19:55 | comment | added | Gerhard Paseman | Regarding matroids, no I cannot. I was initially thinking of picking a set $D$ in $S$ and using it to classify sets in S, using the fact that for any partition $E \cup F$ of $D$, any set in $S$ which intersects $D$ in $G \subseteq E$ must intersect any other set in $S$ which intersects $D$ in $H \subseteq F$, and using that to classify the isomorphism types of set systems $S$, but I know of no clean way to proceed after that. While finite combinatorial designs may ultimately be what you want, I can't guarantee finite. Thus matroids. Gerhard "Ask Me About System Design" Paseman, 2011.05.06 | |
| May 6, 2011 at 18:23 | comment | added | TMM | Could you be a bit more specific? I am not that familiar with matroid theory, but I don't see how formulating this as a matroid problem makes the problem easier. Actually at first I was hoping that this "maximality" of projective planes was some obvious property I did not know about, but apparently it is not... | |
| May 5, 2011 at 21:56 | comment | added | Gerhard Paseman | I imagine matroids may be useful here. Perhaps searching the web for your favorite terms with "matroid" is worth a few minutes of your time. Gerhard "Ask Me About System Design" Paseman, 2011.05.05 | |
| May 5, 2011 at 18:07 | history | edited | TMM | CC BY-SA 3.0 |
added 86 characters in body
|
| May 5, 2011 at 15:06 | history | asked | TMM | CC BY-SA 3.0 |