Vignettes. Part 9. Two different meanings of “star hypergraph”.

This little post is meant to be technically useful, pointing out one of the myriad clashes of terminology that exist in just about any science.

I happenend to know the term “star hypergraph” for a long time, but only in what I thought the only and usual sense (applying to  “hypergraph” in the most standard sense nowadays: set of subsets sets of a specified set).

Yesterday I saw that within the digraph-theoretic literature, there is a another meaning of “star hypergraph”. So here there are the two definitions, for the benefit of others who are puzzled by someone else using “star hypergraph” in another way than what one is used to, and turning to search engines for help.

Definition (star hypergraph; usual meaning for abstract hypergraphs; cf. e.g. the article J. Beck, Surplus of Graphs and the Lovász Local Lemma. Section 1).

Suppose H=(V,E) is an abstract hypergraph. (I.e. V is a set and E\in 2^{2^V}.) Then H is called a star hypergraph if and only if (writing \lvert\cdot\rvert for the cardinality of a set)

  1. for all e,e'\in E, \lvert e\cap e'\rvert\leq 1,
  2. for all v\in V, \lvert \{e\in E\colon v\in e \}\rvert=2.

Remark. Obviously, axioms 1. and 2. are independent. To see 1. \not\Rightarrow 2., consider any…err…star?…consisting of more than two hyperedges, any two of which intersect in precisely one ground-set element; this “star”, which in hypergraph-theory is more usually referred to by the whimsical-yet-evocative name sunflower, or the technical term \Delta-system,  is not a “star hypergraph”, since 2. is false. To see 2. \not\Rightarrow1., an easy counterexample is the hypergraph consisting of countably-infinitely-many four-element contiguous subsets (aka intervals) of \mathbb{Z}, any two consecutive of which interesecting in exactly two ground-set-elements: there, every ground-set element is in precisely two hyperedges, so 2. is true, but 1. is false.

Definition (star hypergraph; a meaning in digraph-theory ; cf. e.g. the article Jørgen Bang-Jensen, Stéphan Thomassé: Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs. Below Theorem 3).

A star hypergraph consists of data

  • an abstract hypergraph H=(V,E)  (I.e. V  a set and E\in 2^{2^V}.)
  • a function h\colon E\rightarrow V

subject to the one axiom

  • for all e\in E, h(e)\in e.

Remark. Of course, the latter definition of “star hypergraph” is (equivalently) nothing else than a family of pointed sets.

Remark. Needless to say, the two above definition of star hypergraph do not have anything naturally to do with one another. They are already type-wise different, the latter “star hypergraph” having one more piece of specified data (the function h), and  lacking the two axioms of the former “star hypergraph”.


This entry was posted in expository, infelicities, Mathematics, Olds. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s