How to get a partite minimum co-degree in a $k$-partite $k$-uniform hypergraph?

Question

I have a $k$-partite $k$-uniform hypergraph $H$ with $V(H) = V_1 \cup\cdots\cup V_k$ (each $|V_i|=n$ for $i \in [k]$), such that the minimum vertex degree $\delta(H) \ge Cn^{k-1}$ for a constant $C$. I need to find a subhypergraph $H'$ with a linear partite minimum co-degree $\delta_{k-1}^*(H') \ge C'n$.

The partite minimum co-degree of $H$ is defined as $$\delta_{k-1}^*(H) = \min_{\substack{S \in {V(H) \choose k-1} \\ |S \cap V_i|\le 1}} d(S).$$ In other words, if you fix any $k-1$ vertices, one in each set $V_i$ for $i \in [k]$, then there are at least $\delta_{k-1}^*(H)$ vertices in the remaining part that form an edge with $S$.

Answer 1

It is not always possible to do that.

Consider the following construction. Let $V_1, V_2, V_3$ be disjoint $n$-sized sets. Let $G$ be a random $3$-partite $2$-graph where every edge with endpoints in two different sets $V_i, V_j$ gets included, independently, with probability $p = 1/2$ each. Let $H$ be the $3$-partite $3$-graph consisting of all partite $3$-sets $\{v_1, v_2, v_3\}$ such that $v_1 v_2, v_1 v_3, v_2 v_3 \in G$.

One can check that, in expectation, each vertex will be contained in $p^3 n^2 = n^2 / 8$ edges in $H$; and using concentration inequalities it is possible to show that with probability very close to $1$ (if $n$ is large) each vertex will indeed get degree close to its expectation. Thus, say, $\delta(H) \geq n^2/9$ will hold.

But, on the other hand, if $H' \subseteq H$ is a subhypergraph with $\delta^\ast_2(H') > 0$, in particular it implies that each pair $x_1 x_2$ with $x_1 \in V(H') \cap V_1$ and $x_2 \in V(H') \cap V_2$ must have $d(x_1 x_2) > 0$, in particular it must hold that $x_1 x_2 \in G$. Thus all possible pairs of edges in $E(V(H') \cap V_1, V(H') \cap V_2)$ must be contained in $G$. But one can also check that, with very large probability, the largest complete bipartite graph $K_{t,t}$ contained in $G[V_1, V_2]$ will have $t = O(\log n)$. Thus $|V(H') \cap V_i| = O(\log n)$, so it cannot happen that $\delta^\ast_2(H') \geq C' n$ (again, assuming $n$ is sufficiently large).