1
$\begingroup$

I'm teaching myself about hypergraphs and can't get my head around a statement in the book I'm using which seems just plain wrong. Hopefully someone here can explain why either I'm misunderstanding things or the book is incorrect. It says the following:

For a graph $G$, we define $N_m(x)$ to be the set of vertices at distance $m$ from $x$ ($x$ a vertex of $G$). We define, for $m$ a positive integer, $k_m$ to be $\min_{v \in V}|N_m(v)|$ and $l_m$ to be $\max_{v \in V}|N_m(v)|$.

...Now consider the hypergraph $G^\star = \{N_m(x):x \in V\}$. Then $G^\star$ has rank $k_m$.

Now as far as my understanding grows, a hypergraph is a collection of vertices and of 'edges' which are subsets of the vertices. The 'rank' is the maximum cardinality of any of the edges of the hypergraph. So then, how can it possibly be that the maximum cardinality of any edge is $k_m$, which appears to me to be the minimum cardinality? Surely it must be $l_m$? The book later goes on to say the maximum degree is $l_m$, which I certainly agree with, but why the rank should be $k_m$ confounds me. If anything it seems like it should be $l_m$. Could someone clarify?

  • 0
    @Percy: You’re right: somehow I inadvertently slipped $v$ into $N_m(v)$, which is clearly wrong.2012-02-23

0 Answers 0