Theoretical Computer Science
graph-theory co.combinatorics matching hypergraphs
Updated Tue, 07 Jun 2022 06:17:21 GMT

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.




Solution

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$.