0
$\begingroup$

Are there any(other than the full complex/1-case)? Is there a name for this ($k$-edge-regular I call it)?

Thanks.

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – user2679290 Apr 2 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$ – Gil Kalai Apr 11 at 22:02
  • $\begingroup$ Yes, sorry. I misunderstood this to suggest that the name is designs. I don't know why. $\endgroup$ – user2679290 Apr 11 at 22:10
1
$\begingroup$

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:

https://arxiv.org/abs/1709.10006

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Some of them are probably isomorphic $\endgroup$ – user2679290 Mar 1 at 1:21
0
$\begingroup$

These are called $d$-(upper) regular $k$-complexes as defined here

https://arxiv.org/abs/1607.07734

| cite | improve this answer | |
$\endgroup$

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.