3
$\begingroup$

Let $H=\left( E_0 ,E_1 ,E_2 , \ldots , E_d \right)$ be a $d$-dimensional full-hyper graph/complex. That is to say, if for some $i\in \left[d \right]$ the hyper-edge $e_j \in E_i$ than for any $i-1$-dimensional $e_k \subset e_j$: $e_k \in E_{i-1}$. The vertices are $E_0$, the hyper-edges between $2$ vertices are $E_1$, between $3$ are $E_2$ and so on.

I bring forward 2 definitions of regularity, and I'd like to show their equivalence:

  • There exists $r_1,\ldots , r_d$ such that for each $1\leq i \leq d$ each vertex $v\in E_0$ has exactly $r_i$ hyper-edges from $E_i$ to which it belongs.
  • There exists $r_1,\ldots , r_d$ such that for each $1\leq i \leq d$ each $e_j \in E_{i-1}$ has exactly $r_i$ hyper-edges from $E_i$ that contain it.

I claim that the definitions are equivalent, obviously with different values of $r_i$'s.

My attempted proof for the case of $d=3$:

$\Leftarrow$

Each vertex $v$ has $r_1$ $2$-edges, each edge has $r_2$ $3$-edges. Each $3$-edge, by definition, uses exactly a distinct pair of $v$'s $2$-edges. Therefore, each $3$-edge is counted twice - one per each $2$-edge of $v$. This makes the total number of $3$-edges exactly $\frac{r_1\cdot r_2}{2}$.

Having a bit trouble for the other direction. Could not disprove it, and I believe it holds, but not every pair of edges that share a common vertex must yield a $3$-edge.

Also, I'd like to try to generalize this for any $d$, but first, to understand the other direction for $d=3$.

Are the 2 definitions for regularity equivalent? I have 2 questions:

  • For the case of d=3?
  • For any d?

(What I provided was a proof in one direction. As for the other direction, I am not sure it holds.)

$\endgroup$
3
  • $\begingroup$ "Each vertex $v$ has $r_1$ $2$-edges". Do you mean each vertex $v$ has $r_1$ $1$-edges? $\endgroup$
    – John L.
    Jan 17, 2023 at 8:45
  • $\begingroup$ Because of the comment above, do you mean "For the case of d=2?"? $\endgroup$
    – John L.
    Jan 17, 2023 at 8:46
  • $\begingroup$ Is there any problem you are not satisfied with Discrete lizard's answer? I would like to encourage you to upvote and accept it. (This comment will be deleted upon feedback.) $\endgroup$
    – John L.
    Jun 10, 2023 at 3:16

1 Answer 1

3
$\begingroup$

Consider the following full hypergraph $H$ (or abstract simplicial complex) of dimension $2$, represented as a simplicial complex (nodes are in black, $2$-edges in red, $3$-edges are turqoise triangles): enter image description here

(or, algebraically: $E_0 = \{v_1,v_2,v_3,v_4,v_5, v_6\}$, $E_1=\{(v_1,v_2), (v_2,v_3), (v_3,v_4), (v_4,v_5), (v_5,v_6), (v_1,v_6), (v_1,v_4), (v_2,v_6), (v_3,v_5)\}$, $E_2 =\{(v_1,v_2,v_6),(v_3,v_4,v_5)\}$ )

$H$ is regular according to the first definition, since each vertex belongs to 3 $2$-edges and 1 triangle. However, $H$ is not regular according tot the second definition, because e.g. $(v_1,v_2)$ is contained in 1 triangle while $(v_2,v_3)$ is contained in 0 triangles.

This means the "other direction" does not hold for dimensions $2$ and higher, so the two properties are not equivalent. (Of course, the two definitions are trivially equivalent for dimension $1$)


As for whether the second property implies the first, your proof (which seems to be for dimension $2$) looks correct to me. The step of going from $2$-edges to $3$-edges can be generalized into $i$-edges to $(i+1)$-edges, after the proof follows by induction. So, it seems the second property is stronger than the first.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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