0
$\begingroup$

It is a very well understood problem to compute the size of the maximum independent set in a uniform hypergraph (in terms of extra conditions).

My question is the following: what is known for hypergraphs that are not uniform? I know the very elementary probabilistic proof by Spencer in his 1972 paper "Turán's theorem for k-graphs" (which uses 1st moment method) but I do not know if there is some later work in which the method is refined somehow (also, maybe using extra assumptions on the hypergraph).

Improve this question
$\endgroup$
2
  • $\begingroup$ You should explain what you are trying to do. As stated, the only thing that one can say is that there is a huge literature about independent sets in hypergraphs, and what you want is somewhere in that literature. $\endgroup$
    – Boris Bukh
    Commented Sep 29, 2023 at 17:08
  • $\begingroup$ Thanks: I want to know what is known whenever we have very weak conditions on our hypergraph. Spencer's result is a very basic one, which needs essentially nothing to our hypergraph, but my impression is that one could improve it with some more sofisticated probabilistic argument. $\endgroup$
    – Johnny Cage
    Commented Sep 30, 2023 at 8:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .