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