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
    You can get proper formatting for things like $\min$ and $\max$ using commands like `\min` and `\max`. If you just write out the word, $\TeX$ interprets the letters as variable names and italicizes them. If you need an operator that doesn't have a predefined command, e.g. $\operatorname{tr}$, you can always use e.g. `\operatorname{tr}`.2012-02-23
  • 0
    @Brian: How is there only 1 hyperedge, sorry? Surely there are 3 hyperedges, each excluding 1 vertex (the one which the other two are neighbours of)? I interpreted $N_m$ as the set of vertices *exactly* at distance m, so each hyperedge $N_1(x)$ would not contain x, if I'm not mistaken? I think by definition, if $|N_m(x)|=c$, then there are $c$ vertices which are at distance $m$ from $x$, equivalently $c$ vertices which $x$ is at distance $m$ from, and so $x$ would be in all of these hyperedges (Which are distinct? The book assumed no small cycles for G, which I think would suffice).2012-02-23
  • 0
    @Percy: You’re right: somehow I inadvertently slipped $v$ into $N_m(v)$, which is clearly wrong.2012-02-23

0 Answers 0