Are there any(other than the full complex/1-case)? Is there a name for this ($k$-edge-regular I call it)?
Thanks.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
There are many such examples. If d=2 (plus some connectivity) those are called pseudomanifolds, so there are many of those, and there are many examples for larger values of d. When every set of size k is a k-edge these are designs.
answered Mar 4, 2020 at 16:48
-
$\begingroup$ I don't think this answer is true. As t-design requires that every (t-1) subset of V is contained in exactly d t-edges. And there could be an hypergraph that is not a design with this property. $\endgroup$ Apr 2, 2020 at 12:53
-
1$\begingroup$ Yes, as I said in the answer those examples are designs when every set of $k$ is in the hypergraph. Examples like psudomanifolds, and buildings, and quotients of building are more general; they need not be designs. $\endgroup$ Apr 11, 2020 at 22:02
-
$\begingroup$ Yes, sorry. I misunderstood this to suggest that the name is designs. I don't know why. $\endgroup$ Apr 11, 2020 at 22:10
$\begingroup$
$\endgroup$
1
I have looked for such construction with 5 vertices(and less). There were none. But it is possible with 6. Here are possible lists of triplets, as returned by Wolfram Mathematica.
{{{1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {1, 4, 6}, {1, 5, 6}, {2, 3, 6}
, {2, 4, 5}, {2, 5, 6}, {3, 4, 5}, {3, 4, 6}}, {{1, 2, 3}, {1, 2,4}
, {1, 3, 6}, {1, 4, 5}, {1, 5, 6}, {2, 3, 5}, {2, 4, 6}, {2, 5, 6}
, {3, 4, 5}, {3, 4, 6}}, {{1, 2, 3}, {1, 2, 5}, {1, 3, 4}, {1, 4,6}
, {1, 5, 6}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}, {3, 4, 5}, {3, 5, 6}
}, {{1, 2, 3}, {1, 2, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6}, {2, 3,4}
, {2, 4, 6}, {2, 5, 6}, {3, 4, 5}, {3, 5, 6}}, {{1, 2, 3}, {1, 2, 6}
, {1, 3, 4}, {1, 4, 5}, {1, 5, 6}, {2, 3, 5}, {2, 4, 5}, {2, 4, 6}
, {3, 4, 6}, {3, 5, 6}}, {{1, 2, 3}, {1, 2, 6}, {1, 3, 5}, {1,4, 5}
, {1, 4, 6}, {2, 3, 4}, {2, 4, 5}, {2, 5, 6}, {3, 4, 6}, {3, 5, 6}
}, {{1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 6}, {1, 5, 6}, {2,3, 5}
, {2, 3, 6}, {2, 4, 6}, {3, 4, 5}, {4, 5, 6}}, {{1, 2, 4}
, {1, 2, 5}, {1, 3, 5}, {1, 3, 6}, {1, 4, 6}, {2, 3, 4}, {2, 3, 6}
, {2, 5, 6}, {3, 4, 5}, {4, 5, 6}}, {{1, 2, 4}, {1, 2, 6}, {1, 3,4}
, {1, 3, 5}, {1, 5, 6}, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {3, 4, 6}
, {4, 5, 6}}, {{1, 2, 4}, {1, 2, 6}, {1, 3, 5}, {1, 3, 6}, {1, 4,5}
, {2, 3, 4}, {2, 3, 5}, {2, 5, 6}, {3, 4, 6}, {4, 5, 6}}, {{1, 2, 5}
, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 4, 6}, {2, 3, 4}, {2, 3, 6}
, {2, 4, 5}, {3, 5, 6}, {4, 5, 6}}, {{1, 2, 5}, {1, 2, 6}, {1,3, 4}
, {1, 3, 6}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 6}, {3, 5, 6}
, {4, 5, 6}}, {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1,3, 4}
, {1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6}, {1, 5, 6}, {2, 3, 4}
, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}, {2, 5, 6}, {3, 4, 5}
, {3, 4, 6}, {3, 5, 6}, {4, 5, 6}}}
Also, Conlon's hypergraph construction satisfies it:
$\begingroup$
$\endgroup$
These are called $d$-(upper) regular $k$-complexes as defined here