Hedgehog (hypergraph)

In the mathematical theory of hypergraphs, a hedgehog is a 3-uniform hypergraph defined from an integer parameter ${\displaystyle t}$. It has ${\displaystyle t+(\genfrac{}{}{0ex}{}{t}{2})}$ vertices, ${\displaystyle t}$ of which can be labeled by the integers from ${\displaystyle 1}$ to ${\displaystyle t}$ and the remaining ${\displaystyle (\genfrac{}{}{0ex}{}{t}{2})}$ of which can be labeled by unordered pairs of these integers. For each pair of integers ${\displaystyle i,j}$ in this range, it has a hyperedge whose vertices have the labels ${\displaystyle i}$, ${\displaystyle j}$, and ${\displaystyle \{i,j\}}$. 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