Skip to main content
2 of 14
added 368 characters in body
user avatar
user avatar

A Non-trivial intersecting complete subgraph problem

Given large enough $k\in\Bbb N$ fix $m\in\{2,\dots,k\}$ and fix $4k$ vertex complete graph $K_{4k}$.

What is the maximum $n\in\Bbb N$ such that there is a list of complete sub-graphs $$G_1,G_2,\dots,G_{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}V(G_{j})\big|=\big|\cap_{j\in\overline{\mathcal I_ i}} V(G_{j})\big|<\big|V(G_{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'}}V(G_{j})\neq\cap_{j\in\mathcal I_i}V(G_{j})\rightarrow(1)\\ \cap_{j\in\mathcal I_i}V(G_{j})\neq \cap_{j\in\overline{\mathcal I_i}} V(G_{j})\rightarrow(2)\\ \cap_{j\in\overline{\mathcal I_i}} V(G_{j}\neq\cap_{j\in\overline{\mathcal I_{i'}}}V(G_{j})\rightarrow(3)\\ \big(\bigcup_{i''\in\{1,2,\dots,t\}}\bigcap_{j\in\mathcal I_{i''}}V(G_{j})\big)\cap V(G_i)=V(G_i)\rightarrow(4a)\\ \big(\bigcup_{i''\in\{1,2,\dots,t\}}\bigcap_{j\in\overline{\mathcal I_{i''}}}V(G_{j})\big)\cap V(G_i)=V(G_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)$?

What is a sharp lower bound and upper bound for $n$?

I think probabilistic method should help.


Solving for $(0)$ alone is trivial.

Fix a $2k+1$ vertices. With the remaining $2k-1$ vertices in $K_{4k}$ choose $m-1$ of them. So $2n=\binom{2k-1}{m-1}$ holds when we solve $(0)$ alone.

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 give more freedom and improve $2n$ to exponential in $k$.

user94040