2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Sasho Nikolov Aug 1 '17 at 16:38
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.