Skip to main content
7 of 14
added 30 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 there is a list of cardinality $2k+m$ subsets $$L_1,L_2,\dots,L_{2n}$$ of $K_{4k}$ and a list of $t\geq 2n-1$ distinct subsets $$\mathcal I_1,\mathcal I_2,\dots,\mathcal I_{t}\subset\{1,2,\dots,2n\}$$ with $|\mathcal I_i|=n$ at every $i\in\{1,2,\dots,t\}$ with $$2k+1=\big|\cap_{j\in\mathcal I_i}L_{j}\big|=\big|\cap_{j\in\overline{\mathcal I_ i}} L_{j}\big|<\big|L_{i_j}\big|=2k+m\rightarrow(0)$$ $$\forall i,i'\in\{1,2,\dots,t\}\left\{ \begin{array}{ll} \cap_{j\in\mathcal I_{i'}}L_{j}\neq\cap_{j\in\mathcal I_i}L_{j}\rightarrow(1)\\ \cap_{j\in\overline{\mathcal I_i}} L_{j}\neq\cap_{j\in\overline{\mathcal I_{i'}}}L_{j}\rightarrow(2)\\ \big(\cap_{j\in\mathcal I_i}L_{j}\big)\cap\big( \cap_{j\in\overline{\mathcal I_i}} L_{j}\big)=\emptyset\rightarrow(2)\\ \big(\bigcup_{i''\in\{1,2,\dots,t\}}\bigcap_{j\in\mathcal I_{i''}}L_{j}\big)\cap L_i=L_i\rightarrow(4a)\\ \big(\bigcup_{i''\in\{1,2,\dots,t\}}\bigcap_{j\in\overline{\mathcal I_{i''}}}L_{j}\big)\cap L_i=L_i \rightarrow(4b)\end{array} \right.$$

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

I think $(4a)\mbox{ or }(4b)\implies(1),(2),(3)$ (but I do not have a proof) and so focusing on $(0),(4a),(4b)$ alone should work.

Can $n$ be as high as $\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)$ holds?

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.



Solving for $(0)$ alone is trivial.

Fix a $2k+1$ subset. With the remaining $2k-1$ subset in $K_{4k}$ choose $m-1$ of them. So when we solve $(0)$ alone $2n=\binom{2k-1}{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