# 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.) – Sasho Nikolov Aug 1 '17 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$.