Hedgehog (hypergraph)

Hedgehog for t = 5

Not to be confused with hedgehog (geometry) or hedgehog space.

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.[1][2]

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

## References

[edit]

1. ^ a b Conlon, David; Fox, Jacob; Rödl, Vojtěch (2017), "Hedgehogs are not colour blind", Journal of Combinatorics, 8 (3): 475–485, arXiv:1511.00563, doi:10.4310/JOC.2017.v8.n3.a4, MR 3668877
2. ^ a b Fox, Jacob; Li, Ray (2020), "On Ramsey numbers of hedgehogs", Combinatorics, Probability and Computing, 29 (1): 101–112, arXiv:1902.10221, doi:10.1017/s0963548319000312, MR 4052929