0
$\begingroup$

Consider two undirected $k$-regular hypergraphs on $n$ vertices with (see e.g. OEIS A319190). Are the two hypergraphs isomorphic if an only if the two multisets of the sizes of their respective hyperedges are equal?

Alternatively, we can think about two families of sets in $\mathcal{P}([n])$ where all elements have the same given frequency. Are the two families isomorphic, i.e. equal up to a permutation of the elements, if and only if the two multisets of the sizes of their respective sets are equal?

I would say the answer is negative, and maybe this is obvious, but up to now I couldn't find a counterexample.

Any suggestion?

Improve this question
$\endgroup$
3
  • $\begingroup$ By isomorphism, we can map the edge set of one hypergraph to the other, just like congruence. Therefore, if we just change the labels of the multisets of one hypergraph to one of its automorphic ones, we would get a different multiset, but with isomorphism between them. In fact, even the more stronger one of automorphism does not have equal multisets, right. $\endgroup$
    – vidyarthi
    Commented Sep 3, 2023 at 9:59
  • $\begingroup$ There is no isomorphism involved in A319190. $\endgroup$
    – Brendan McKay
    Commented Sep 3, 2023 at 12:22
  • $\begingroup$ @BrendanMcKay yes, in fact I wanted to compute the equivalent of that sequence for non-isomorphic hypergraphs. $\endgroup$
    – Fabius Wiesner
    Commented Sep 3, 2023 at 12:55

1 Answer 1

Reset to default
2
$\begingroup$

No. There are already multiple isomorphism classes of regular graphs. Consider two disjoint triangles (i.e., $\{12,23,31\}\cup \{45,56,64\}$), versus a cycle of length 6 ($\{12,23,34,45,56,61\}$).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .