Hypergraph vertex plus incident edge deletion giving isomorphic subgraphs

101 Views Asked by At

There exist hypergraphs $H = (V, E)$ such that upon the deletion of any arbitrary vertex $v \in V$ and any edge $e \in E$ that is incident to $v$ (along with all vertices in $e$), one obtains the same subgraph $G$. An example is the $n \times n$ grid-hypergraph $H$, i.e., a family of sets $\{A_1, \dots, A_n, B_1, \dots, B_n\}$ such that $|A_i| = |B_i| = n$ for $1 \leq i \leq n$, $A_i \cap A_j = B_i \cap B_j = \emptyset$ for $1 \leq i < j \leq n$ and $|A_i \cap B_j| = 1$ for $1 \leq i, j \leq n$, for which the deletion of any vertex and edges incident to the vertex (along with all vertices in those edges) gives rise to the $(n-1) \times (n-1)$ grid-hypergraph $G$.

I would like to know if there is a characterisation of the hypergraphs $G$ that can be $\textit{lifted}$ to a hypergraph $H$ with this property. Can only grid hypergraphs be lifted in such a manner?

1

There are 1 best solutions below

2
On

Any vertex-transitive hypergraph has this property. For any vertices $v,w$ there is an automorphism taking $v$ to $w$; when we do the vertex-plus-neighbor deletion from $v$ and from $w$, the automorphism becomes an isomorphism between the remainders.

There are plenty of non-grid examples of hypergraphs that could be "left over" from a vertex-transitive graph. For example, you can take a cycle hypergraph (loose or tight or anything in between) and be left with the same path hypergraph after you delete any vertex and all its neighbors.

There are also examples of hypergraphs with this property that aren't vertex transitive - for example, any hypergraph in which every two vertices are on a hyperedge together, because then we're left with nothing when we delete a vertex and all its neighbors. But I don't know if there's anything here that gives us new examples of "left over" graphs, other than the null graph.