Hedgehog (Hypergraph)

In the mathematical theory of hypergraphs, a hedgehog is a 3-uniform hypergraph defined from an integer parameter [math]\displaystyle{ t }[/math]. It has [math]\displaystyle{ t+\tbinom{t}{2} }[/math] vertices, [math]\displaystyle{ t }[/math] of which can be labeled by the integers from [math]\displaystyle{ 1 }[/math] to [math]\displaystyle{ t }[/math] and the remaining [math]\displaystyle{ \tbinom{t}{2} }[/math] of which can be labeled by unordered pairs of these integers. For each pair of integers [math]\displaystyle{ i,j }[/math] in this range, it has a hyperedge whose vertices have the labels [math]\displaystyle{ i }[/math], [math]\displaystyle{ j }[/math], and [math]\displaystyle{ \{i,j\} }[/math]. Equivalently it can be formed from a complete graph by adding a new vertex to each edge of the complete graph, extending it to an order-3 hyperedge.^[1][2]

The properties of this hypergraph make it of interest in Ramsey theory.^[1][2]

References

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Hedgehog (hypergraph). Read more