<p>Unfortunately the conjecture is wrong (for $d \geq 2$). Here is a counterexample for $d=2$.</p>

<p>Suppose that the conjecture (in its graphical formulation) held for some $c,M_0 &gt; 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$.</p>

CC BY-SA 3.0
2017-08-01T17:57:09.983Z
2017-08-01T17:57:09.983Z
Yuval Filmus
<p>I am interested in knowing whether the following conjecture is true or not:</p>
<blockquote>
<p>For every <span class="math-container">$d \geq 1$</span> there exist constants <span class="math-container">$\delta,M_0 &gt; 0$</span> such that the following holds for all <span class="math-container">$M \geq M_0$</span>.</p>
<p>Let <span class="math-container">$\mathcal{S}$</span> be a finite family of sets of size at least <span class="math-container">$M$</span> in which each element appear at most <span class="math-container">$d$</span> times.</p>
<p>There exists a set <span class="math-container">$X$</span> such that <span class="math-container">$\delta M \leq |S \cap X| \leq M$</span> for all <span class="math-container">$S \in \mathcal{S}$</span>.</p>
</blockquote>
<p>We can also formulate this in terms of hypergraphs:</p>
<blockquote>
<p>For every <span class="math-container">$d \geq 1$</span> there exist constants <span class="math-container">$\delta,M_0 &gt; 0$</span> such that the following holds for all <span class="math-container">$M \geq M_0$</span>.</p>
<p>Let <span class="math-container">$H$</span> be a <span class="math-container">$d$</span>-uniform hypergraph in which each vertex has degree at least <span class="math-container">$M$</span>. There is a subhypergraph <span class="math-container">$H'$</span> of <span class="math-container">$H$</span>, obtained by only deleting hyperedges, in which the degree of each vertex is between <span class="math-container">$\delta M$</span> and <span class="math-container">$M$</span>.</p>
</blockquote>
<p>(If we want to make the statements completely equivalent, we should ask all hyperedges to have uniformity <em>at most</em> <span class="math-container">$d$</span> rather than <em>exactly</em> <span class="math-container">$d$</span>.)</p>
<p>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.</p>

CC BY-SA 3.0
2017-08-01T16:38:38.930Z
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
<graph-theory><co.combinatorics><matching><hypergraphs>
Almost regular subhypergraph of hypergraph with large minimal degree
Yuval Filmus
# Almost regular subhypergraph of hypergraph with large minimal degree

(Asked by: username_0 on 2017-08-01)

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.

**Tags:** graph-theory, co.combinatorics, matching, hypergraphs

> **Comments:**
> **username_1**: 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.)  

---

## 1 answers

### Answer by username_0 on 2017-08-01. Score: 3 | Accepted answer

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


---

