Skip to main content
1 of 4
Connor
  • 281
  • 1
  • 7

Known result about existence of $n$-vertex $k$-uniform $r$-hypergraph?

Are there known results about $n,k,r$ such that $n$-vertex $k$-uniform $r$-regular graphs exist? If it involves a too large class of graphs, what if $k= \tilde{\theta}(n)$? What if an extra constant holds that for any two vertices, there is at most one hyperedge containing them?

Here a hypergraph consists of a vertex set $V$ and a hyperedge set $\mathcal{E}$ which is a family of subsets of $V$. $n$-vertex means $|V|=n$. $k$-unform means each set in $\mathcal{E}$ is a $k$-subset of $V$. $r$-regular means for every vertex, there are $r$ hyperedges contain it.

And this question is motivated by projective planes and affine planes over finite fields, for the former one, it is $(q^2+q+1)$-vertex $(q+1)$-uniform $(q+1)$-regular hypergraphs for all prime powers $q$.

Connor
  • 281
  • 1
  • 7