Neighborhood structure in a uniform hypergraph

247 Views Asked by At

Consider a $k$-uniform connected hypergraph with vertex set $V$ and hyperedge set $E$, as defined in https://en.wikipedia.org/wiki/Hypergraph#Symmetric_hypergraphs .

We impose the following condition on this hypergraph: for any vertex $v$, let $T_v$ be set of all hyperedges that are incident on $v$. Then for any two distinct vertices $v,v'$, the sets $T_v, T_{v'}$ are distinct.

Intuition is that if there were two or more vertices that shared same set of incident edges, then we would merge these vertices into one vertex, just to avoid `wasting' vertices.

Two hyperedges are said to be neighbours if there is a vertex on which both are incident. My question is, what is the minimum number of neighbours that any hyperedge in this graph must have?