Minimum vertex number that admits linear $d$-regular $k$-uniform hypergraph

extremal-combinatoricsextremal-graph-theorygraph theoryhypergraphsramsey-theory

$\newcommand\LRU{\mathrm{LRU}}\newcommand\tA{\mathrm{A}}\newcommand\tB{\mathrm{B}}\newcommand\tC{\mathrm{C}}\newcommand\tD{\mathrm{D}}\newcommand\tE{\mathrm{E}}$
For given integers $d>0$, $k>1$ and $n>0$ we look at $d$-regular $k$-uniform hypergraphs $H=(V,E)$ on $n$ vertices. This means that each hyperedge $e\in E$ has size $|e|=k$ and each vertex $v\in V$ is incident to exactly $d$ hyperedges $e\in E$, that is, $|\{e\in E:v\in e\}|=d$.

The hypergraph $H$ is linear if two distinct hyperedges agree on at most one vertex, that is, $|e\cap f|\le 1$ for $e,f\in E$ with $e\neq f$. Let $\mathcal H(d,k,n)$ be the set of all linear $d$-regular $k$-uniform hypergraphs on $n$ vertices. Finally, let
$$\LRU(d,k)=\inf\{n>0:\mathcal H(d,k,n)\neq\emptyset\}.$$

QUESTION: Is there any efficient way to determine $\LRU(d,k)$?

BACKGOUND: When I talk about $d$-regular $k$-uniform hypergraphs, I love to use pictures. For the pictures, I like to use linear hypergraphs (if the subject allows or encourages that).

RESULTS:

  • Handshaking.
    By counting vertex-hyperedge pairs we notice that
    $$dn=\sum_{v\in V}\sum_{e\in E}\unicode{120793}\{v\in e\}=\sum_{e\in E}\sum_{v\in V}\unicode{120793}\{v\in e\}=k|E|,$$
    so we have $d\LRU(d,k)\in k\mathbb Z_{>0}$. Thus, with $r=k/\gcd(d,k)$ we have $\LRU(d,k)\in r\mathbb Z_{>0}$.
  • Trivial Degree. We have $\LRU(1,k)=k$ because $\LRU(1,k)\ge k$ by Handshaking and $H=([k],\{[k]\})$ is a witness, where $[k]=\{1,\dots,k\}$. Now, we can restrict to $d>1$.
  • Trivial Arity. For $k=2$ the hypergraph is a simple graph and all simple graphs are linear, so $\LRU(d,2)=d+1$ (clique on $d+1$ vertices, cf. here). Now, we can restrict to $k>2$.
  • Trivial Lower Bound. Since the hypergraph is linear, for any given vertex $v$ the $d$ hyperedges of size $k$ incident to $v$ only coincide on $v$, which already requires $\LRU(d,k)\ge 1+d(k-1)$.
    Using Handshaking, we have $\LRU(d,k)\ge\min\{n\in r\mathbb Z:n\ge 1+d(k-1)\}$.
  • Cube Hypergraph. The cube hypergraph on $[k]^d$ (where $k$ distinct vertices form a hyperedge if they agree on all coordinates except for one) is linear. This gives the bound $\LRU(d,k)\le k^d$.
  • Algorithm. For fixed $d$, $k$ we can now cycle through the remaining values of $n$. For given $n$, take the canonical neighborhood for vertex $1$, meaning the hyperedges
    $$[k],\{1\}\cup[1+2(k-1)]\setminus[k],\dots,\{1\}\cup[1+d(k-1)]\setminus[1+(d-1)(k-1)].$$
    For vertex $i>1$ obtain the neighborhood by going through all possible choices of $d-1$ distinct hyperedges that contain $i$ and avoid $[i-1]$ successively and continue if the resulting hypergraph is still linear (a check which shouldn't be too expensive if we remember for each vertex which hyperedges it participates in). For vertices that are isolated so far we can always assume that their labels are minimal (out of all labels of isolated vertices), due to symmetry.
    There are a lot of other symmetries at play here, but it seems rather challenging to make use of them.

CONCLUSION: Unfortunately, I'm not familiar enough with all the special classes of (linear regular uniform) hypergraphs (e.g. the cube hypergraph). This would be an easy way to improve the upper bound (maybe even answer the question). If the problem turns out to be harder, maybe we can borrow ideas from Ramsey Theory?

I'm very grateful for any pointer in the right direction, say, partial answers that improve the bounds above or ideas on how to solve the problem algorithmically.

PROGRESS:

  • Symmetry. For any $(V,E)\in\mathcal H(d,k,n)$ we have $(V',E')\in\mathcal H(k,d,n)$, where $V'=E$, $E'=\{e_v:v\in V\}$ and $e_v=\{e\in E:v\in e\}$. Thus, for any linear $d$-regular $k$-uniform hypergraph $H=(V,E)$ we have $\LRU(d,k)\le|V|$ and $\LRU(k,d)\le|E|$.
    For example, using the Cube Hypergraph this gives $\LRU(d,k)\le kd^{k-1}$. Also, notice that for $H=(V,E)\in\mathcal H(d,k,n)$ with $\LRU(d,k)=|V|=n$ we have $$\LRU(k,d)=|E|=\frac{dn}{k}=\frac dk\LRU(d,k).$$ Hence, we can restrict to $d\ge k\ge 3$ using Trivial Arity.

  • Projective Planes. Thanks to user14111, projective planes (cf. here and here) give $\LRU(q+1,q+1)= q^2+q+1$ and $\LRU(q+1,q)= q^2$ iff $q$ is such that the corresponding projective plane exists, cf. here. In particular, this holds if $q$ is a prime power.

  • Steiner Systems. Thanks to user14111, hypergraphs for which the Trivial Lower Bound is tight, are exactly Steiner Systems $S(2,k,1+d(k-1))$.
    Steiner triples $S(2,3,n)$ exist if and only if $n=6a+1$ or $n=6a+3$ for some $a$.
    This shows that the Trivial Lower Bound $\LRU(d,3)=1+2d$ is tight if and only if $d\not\in 3\mathbb Z+2$. For $d\in 3\mathbb Z+2$ the Trivial Lower Bound gives $\LRU(d,3)\ge 2+2d$.
    Also results for other Steiner $2$-designs are known, say, $S(2,4,v)$ exists if and only if $v\in 12\mathbb Z+1$ or $v\in12\mathbb Z+4$ (cf. here). In oher words, we have $\LRU(d,4)=1+3d$ if and only if $d\in 4\mathbb Z$ or $d\in4\mathbb Z+1$. For $d\in4\mathbb Z+2$ we have $\LRU(d,4)\ge2+3d$ and for $d\in4\mathbb Z+3$ we have $\LRU(d,4)\ge3+3d$.

  • Upper Bound. Thanks to user14111. Let $V=\binom{[k-1+d]}{k-1}$ be the $(k-1)$-subsets of $[k-1+d]$ and let the hyperedges $E=\{\binom{X}{k-1}:X\in\binom{[k-1+d]}{k}\}$ be the $(k-1)$-subsets of the $k$-subsets. Then $(V,E)$ is a witness for $\LRU(d,k)\le\binom{k-1+d}{k-1}$.

MINIMAL OPEN CASE:

  • We have $\LRU(1,k)=k$ by Trivial Degree, then $d\ge k$ by Symmetry and $\LRU(d,2)=d+1$ by Trivial Arity. This allows to restrict to $d\ge k$ with $d,k\ge 3$.
  • We have $\LRU(3,3)=2^2+2+1=7$, $\LRU(4,3)=3^2=9$ and $\LRU(4,4)=3^2+3+1=13$ by Projective Planes.

Now, the minimal open case is $12\le\LRU(5,3)\le21$.

Best Answer

QUESTION: Is there any efficient way to determine $\operatorname{LRU}(d,k)$?

No, not in general, at least in the present state of human knowledge.

It is easy to see that any $(q+1)$-regular $(q+1)$-uniform linear hypergraph on $q^2+q+1$ vertices is a projective plane, i.e., each pair of distinct vertices (points) is incident with a common hyperedge (line), and each pair of distinct hyperedges (lines) is incident with a common vertex (point). Therefore we have:

Proposition. $\operatorname{LRU}(q+1,q+1)=q^2+q+1$ if and only if a projective plane of order $q$ exists.

A large computation by C. W. H. Lam et al. established that $\operatorname{LRU}(11,11)\gt111$. As far as I know, it is still an unsolved problem whether $\operatorname{LRU}(13,13)\gt157$.

If you could efficiently determine $\operatorname{LRU}(d,k)$ exactly in all cases, you could in particular determine all possible orders of projective planes. That would be a major advance.

Related Question