Skip to main content
13 of 14
added 55 characters in body
user avatar
user avatar

A Non-trivial intersecting set system problem

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 subsets $$L_1,L_2,\dots,L_{2n}\subset\bigcup_{i\in\{1,2,\dots,2n\}}L_i=K_{4k}$$ $$\mathcal I_1,\mathcal I_2,\dots,\mathcal I_{t}\subset\{1,2,\dots,2n\}$$ 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.$$ $$\bigcup_{i''\in\{1,\dots,t\}}\bigcap_{j\in\mathcal I_{i''}}L_{j}=\bigcup_{i''\in\{1,\dots,t\}}\bigcap_{j\in\overline{\mathcal I_{i''}}}L_{j}=K_{4k} \rightarrow(P_{3})$$

where $\overline{\mathcal I_i}=\{1,2,\dots,n\}\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$.

user94040