Liven large enough $k\in\Bbb N$ fix $m\in\{2,3,\dots,k\}$ and fix $4k$ cardinality set $K_{4k}$.

What is the maximum $n\in\Bbb N$ such that at some $t\geq2n-1$ there are $$\mbox{ subsets }L_1,L_2,\dots,L_{2n}\subset K_{4k}\subseteq\bigcup_{i\in\{1,2,\dots,2n\}}L_i$$ $$\mbox{ index sets }\mathcal I_1,\mathcal I_2,\dots,\mathcal I_{t}\subset\{1,2,\dots,2n\}\subseteq\bigcup_{i\in\{1,2,\dots,t\}}\mathcal I_i$$ with the properties $$\lceil\beta k\rceil=\big|\cap_{j\in\mathcal I_i}L_{j}\big|=\big|\cap_{j\in\overline{\mathcal I_ i}} L_{j}\big|<\big|L_{i}\big|=\lceil\beta k\rceil+m\mbox{ at some }\beta\in(1,2)\rightarrow(P_0)$$ $$\forall i\in\{1,2,\dots,t\}\mbox{ we have }\left\{\begin{array}{ll}\quad\quad|\mathcal I_i|=|\mathcal I_{i'}|=n\rightarrow(P_{1a})\\ \big(\cap_{j\in\mathcal I_i}L_{j}\big)\cap\big( \cap_{j\in\overline{\mathcal I_i}} L_{j}\big)=\emptyset\rightarrow(P_{1b})\end{array}\right.$$

$$\forall i,i'\in\{1,2,\dots,t\}\mbox{ with }i\neq i'\left\{ \begin{array}{ll} \cap_{j\in\mathcal I_{i'}}L_{j}\neq\cap_{j\in\mathcal I_i}L_{j}\rightarrow(P_{2a})\\ \cap_{j\in\overline{\mathcal I_i}} L_{j}\neq\cap_{j\in\overline{\mathcal I_{i'}}}L_{j}\rightarrow(P_{2b}) \\ \end{array} \right.$$ $$K_{4k}\subseteq\bigcup_{i''\in\{1,\dots,t\}}\bigcap_{j\in\mathcal I_{i''}}L_{j} \rightarrow(P_{3a})$$ $$K_{4k}\subseteq\bigcup_{i''\in\{1,\dots,t\}}\bigcap_{j\in\overline{\mathcal I_{i''}}}L_{j} \rightarrow(P_{3b})$$

where $\overline{\mathcal I_i}=\{1,2,\dots,2n\}\backslash\mathcal I_i$ holds?

Can $n=\Omega\bigg(\frac{(1+c)^{k/{(\log k)^{\frac1c}}}}{k^{\frac1c}}\bigg)$ for some $c\in(0,1)$ when $m=\omega\Big(\frac k{\log k}\Big)$ hold?

What is a sharp lower bound and upper bound for $n$ at given $m\in\{2,3,\dots,k\}$?

I think probabilistic method should help.

$\underline{\mbox{My thoughts}}$:

Solving for $(0)$ alone is trivial.

Fix a $2k$ subset. With the remaining $2k$ subset in $K_{4k}$ choose $m-1$ of them. So when we solve $(0)$ alone $2n=\binom{2k}{m-1}$ holds which grows faster than exponential at $m=k$.

This example works for all $2^{2n}$ intersections satisfying $(0)$. I want only for $\geq2n-1$ of them. May be this and breaking the condition that all intersections are identical and need to cover $K_{4k}$ will still leave freedom to get $2n$ to be exponential in $k$.

  • $\begingroup$ $(4a)$ and $(4b)$ are essentially covering properties. $\endgroup$ – user94040 Nov 20 '16 at 22:00
  • $\begingroup$ A few points are unclear to me. For instance, what does the graph structure have to do with anything? It seems to me that it's not important at all, right? Everything seems to be about vertex sets, so why not just state it all in terms of sets? [and this problem doesn't strike me as one where the probabilistic method would help. It sounds like you're insisting on something far from random. But I admit I might not be understanding you correctly, since I'm not quite sure what you mean.] $\endgroup$ – Pat Devlin Nov 21 '16 at 5:25
  • $\begingroup$ @PatDevlin You are right in only vertex set matters. I thought it will be easy to visualize in these terms. I see your point on randomness. I just felt there may be a possibility. $\endgroup$ – user94040 Nov 21 '16 at 5:31
  • $\begingroup$ @PatDevlin rewrote in terms of sets. what is unclear? $\endgroup$ – user94040 Nov 21 '16 at 5:42
  • $\begingroup$ 13 edits in under 24 hours. $\endgroup$ – Gerry Myerson Nov 21 '16 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy