How many hyperedges are in a (k, r) regular hypergraph?

Question

I'm trying to write an algorithm to produce random $r$-regular $k$-uniform hypergraphs, the representation I am interested in is the incidence matrix.

I've done this for the simpler case of a regular graph (2-uniform hypergraph), and that was not general enough for my problem, that's why I need the hypergraph version.

For a 2-uniform $r$-regular hypergraph, the number of edges $E$ and the number of nodes $N$ are related by:

$$ E = r \times N / 2 $$

Would the $k$-uniform hypergraph version be just

$$ E = r \times N / k $$

??

To build the algorithm I would need to know the number of hyperedges I'm expecting to have.

And if anyone can point me to an efficient algorithm to build such hypergraphs I would be really pleased! The one I did (for graphs) works but there might be better ways to do it.

[edit 1]: fixed the $r$ and $k$ that I had mixed up.

[edit 2]: would the linearity of the graph change the number of possible hyperedges? If it does, I would expect linear $(k, r)$ hypergraphs having a well defined number of hyperedges while nonlinear ones have at least the same number as linear ones, but possibly more.

Answer 1

You are right about $E=rN/k$. To show this, simply double count the number of pairs $(v,e)\in V\times E$ such that $v\in e$. Then $$rN=\sum_{v\in V}\deg(v) = \sum_{v\in V}\#\{e\in E\mid v\in e\}=\sum_{e\in E}\#\{v\in V\mid v\in e\}=kE.$$

The linearity of the graph would not change this, but it does put an upper bound on the number of edges. Again, this comes from a double counting argument, but this on the triples $(v,v',e)\in V^2\times E$ such that $v\neq v'\in e$. Note that for any pair $(v,v')$ with $v\neq v'$, there is at most one $e$ that contains both of them. Therefore $$k(k-1)E = \sum_{e\in E}\#\{(v,v')\in V^2\mid v\neq v'\in e\}\leq \#\{(v,v')\in V\mid v\neq v'\}=N(N-1),$$ and as we know that $kE=rN$, we get $r\leq (N-1)/(k-1)$. This shows that the degree of each vertex cannot be too large when $N$ and $k$ are fixed, which is the same as saying that the number of edges cannot be too large.

Answer 2

Well I ended up implementing an algorithm that doesn't require the pior knowledge of how many hyperedges are going to be created, and it seems that my intuition was right about the number of hyperedges. But it doesn't seem to matter whether it is a linear hypergraph or not.