# Almost regular subhypergraph of hypergraph with large minimal degree

I am interested in knowing whether the following conjecture is true or not:

For every $$d \geq 1$$ there exist constants $$\delta,M_0 > 0$$ such that the following holds for all $$M \geq M_0$$.

Let $$\mathcal{S}$$ be a finite family of sets of size at least $$M$$ in which each element appear at most $$d$$ times.

There exists a set $$X$$ such that $$\delta M \leq |S \cap X| \leq M$$ for all $$S \in \mathcal{S}$$.

We can also formulate this in terms of hypergraphs:

For every $$d \geq 1$$ there exist constants $$\delta,M_0 > 0$$ such that the following holds for all $$M \geq M_0$$.

Let $$H$$ be a $$d$$-uniform hypergraph in which each vertex has degree at least $$M$$. There is a subhypergraph $$H'$$ of $$H$$, obtained by only deleting hyperedges, in which the degree of each vertex is between $$\delta M$$ and $$M$$.

(If we want to make the statements completely equivalent, we should ask all hyperedges to have uniformity at most $$d$$ rather than exactly $$d$$.)

The question has the flavor of Hall's matching theorem and of Beck-Fiala, but so far I was unable to prove the conjecture using these tools. Perhaps I am missing some simple argument, or perhaps there is a simple counterexample.

• Interesting. Is it easy to see that the fractional version is true? I.e. that there exists a vector $x \in [0,1]^U$ such that $\delta M \le (Ax)_i \le M$, where $U$ is the universe and $A$ is the incidence matrix of $\cal S$. If you can prove that, then I think Beck-Fiala could imply what you want. (But I haven't thought this through.) Aug 1, 2017 at 16:38

Unfortunately the conjecture is wrong (for $d \geq 2$). Here is a counterexample for $d=2$.
Suppose that the conjecture (in its graphical formulation) held for some $c,M_0 > 0$. Consider a complete bipartite graph in which the left side has $M^2$ vertices and the right side has $M$ vertices. Thus the left degrees are $M$ and the right degrees are $M^2$. In order to create a subgraph in which all right degrees are at most $M$, we need to remove at least $M(M^2-M)$ edges. On the other hand, any subgraph in which all left degrees are at least $cM$ must have at most $(1-c)M^3$ edges removed. This means that $M^3 (1-1/M) \leq (1-c)M^3$, which is false for large enough $M$.