Are there known results about $n,k,r$ such that $n$-vertex $k$-uniform $r$-regular hypergraphs exist? If this is too large a class of hypergraphs, what if $k=\tilde{\theta}(\sqrt{n})$? What if an extra condition holds, requiring 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$, and '$n$-vertex' means $|V|=n$, and '$k$-unform' means each set in $\mathcal{E}$ is a $k$-subset of $V$, and '$r$-regular' means for every vertex, there are $r$ hyperedges containing it.

This question is motivated by projective planes and affine planes over finite fields. The former are $(q^2+q+1)$-vertex $(q+1)$-uniform $(q+1)$-regular hypergraphs, for a given prime powers $q$, i.e., there, $n=q^2+q+1$, $k=q+1$, and $r=q+1$.

  • 1
    $\begingroup$ Yes, $\tilde{\theta}(n)$ means it has order of magnitude of $n$ up to some power of logarithm factor $\log n$. For example $(\log n)^8 n$. While I think it is more meaningful to require $\tilde{\theta}(\sqrt{n})$, so I revised it. $\endgroup$ – Connor Oct 6 '17 at 14:01

I will, as is common, use $v$ rather than $n$ for $|V|.$ The number of edges (often called blocks) is $b=\frac{vr}k$ and this must be an integer. If you are motivated by finite projective planes and the like then you should add a condition that there is a number $\lambda$ such that every pair of vertices is in $\lambda$ common blocks (I will say why in a bit). This number is then determined by $v,k,r$ as $\lambda=\frac{r(k-1)}{v-1}.$ The structure is then called a $2$-design. It is most common to use $(v,k,\lambda)$ as the parameters. It is known that for each fixed pair $k,\lambda$ there is an $N=N_{k,\lambda}$ so that there is a $(v,k,\lambda)$ $2$-design provided that $r=\frac{\lambda(v-1)}{k-1}$ and $b=\frac{vr}k$ are integers. Maybe not that interesting.

Here is one illustration of why this pairwise condition makes it much more interesting: You mention $(v,r,k)=(q^2+q+1,q+1,q+1)$ designs. These are trivial without the pairwise condition. Just pick your $q$ at will. Take $0,1,2,...,v-1$ and the $v$ blocks $\{j,j+1,\cdots,j+k\}$ considered $\mod v.$ That always works. It works for $r=k$ any time $\gcd(v,k)=1.$

With the added condition that $\lambda$ exists, it must be $\lambda=1$ and then one has a finite projective plane of order $q$. There are projective planes (sometimes many) if $q$ is a prime power. A huge question is if there are ever examples with $q$ not a prime power. It is known that if $q=4m+2$ then it must be a sum of two squares for a projective plane of order $q$ to exist. This rules out $q=6$ which is possible to do by hand. A massive calculation ruled out $q=10.$ The case $q=12$ is open.

For the rest of this answer I will forget about the pairwise condition.

If you allow repeated blocks then any $(v,k,r)$ with $\frac{vr}{k} \in \mathbb{Z}$ is possible (provided $k \leq v$) using a simple cyclic construction as above. So let's demand distinct blocks, which limits it to $b \leq \binom{n}{k}.$ I won't go into any detail, but cyclic constructions can cover many cases and these can be combined to cover more.

My guess is that for each fixed $r,k$ there is an $N_{k,r}$ such that what you want exists provided $v \gt N$ and $b \in \mathbb{Z}.$ In fact this may be much easier than in the $2$-design case: You can combine a $(v_1,k,r)$ and $(v_2,k,r)$ with disjoint vertex sets to get a $(v_1+v_2,k,r).$ This allow $(v,k,r)$ for any $v$ of the form $sv_1+tv_2$ which can include all but finitely many possible values of $v.$ Of course this does not tell us about letting $k$ grow with $v.$


This is a baby version of designs and most probably should be studied already. You may try to search standard references on designs.

Here are some immediate necessary and sufficient conditions, still not matching, alas.

By double counting of pairs (hyperedge, a vertex of this hyperedges), the number of hyperedges equals $nr/k$, thus this must be integer. Another necessary condition is that the number of edges should not be greater than $\binom{n}k$.

Denote $n=dn_1$, $k=dn_1$, where $n_1,k_1$ are coprime, $d=\text{gcd}(n,k)$.Then $r$ is divisible by $k_1$, $r=k_1w$. Partition our $n$ vertices onto $n_1$ blocks by $d$ vertices in each block and place the blocks around the circle. Take all hyperedges containing $k_1$ consecutive blocks. We get a $k_1$-regular (and $k$-uniform) hypergraph. Taking the unions of such hypergraphs for different partitions onto blocks we get examples for higher values of $w$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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