10
$\begingroup$

It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively.

However, I wonder whether there is a ‘nice’ lattice structure on unlabelled graphs, i.e., graphs up to isomorphism.

I'd also be happy with a lattice structure on a (reasonably) large subset, if this makes things any easier, e.g., connected or planar graphs on $n$ vertices.

To clarify: a very non-‘nice’ way to make the set of unlabelled graphs on $n$ vertices into a lattice is to pick an arbitrary total order.

An idea for a slightly nicer way might be to set $G < H$ if and only if $H$ has more edges than $G$, however this does not produce a lattice.

Improve this question
$\endgroup$
4
  • 9
    $\begingroup$ A "natural" poset structure on the set of $n$-vertex unlabelled graphs is the subgraph ordering. However, this is not a lattice for $n\geq 5$. This poset has some nice properties: it is a quotient of a boolean algebra and hence Sperner, for instance. See pp. 49-50 of my book Algebraic Combinatorics, second ed. $\endgroup$
    – Richard Stanley
    Commented Jun 19, 2020 at 23:04
  • 4
    $\begingroup$ @Martin: there is, probably, no poset structure on the set of unlabeled graphs with $n$ vertices with the property that the ordering $\le$ can be computed in polynomial time (in $n$). This is because such an ordering could be used to solve graph isomorphism, by checking whether $G \le H$ and $H \le G$. But maybe this is too obvious to merit an answer. E.g. you might consider the subgraph ordering to be nice. $\endgroup$
    – Qiaochu Yuan
    Commented Jan 12, 2021 at 0:42
  • $\begingroup$ @QiaochuYuan, I find that this is actually a rather important observation. But indeed, for me, "nice" does not imply "explicit". $\endgroup$
    – Martin Rubey
    Commented Jan 12, 2021 at 18:26
  • 2
    $\begingroup$ @QiaochuYuan, it occurred to me that we could have an ordering where $G<H$ or even just the covering relation is easy to compute. At least, I don't see right now how this would yield an easy isomorphism test. $\endgroup$
    – Martin Rubey
    Commented Feb 10, 2021 at 22:06

1 Answer 1

Reset to default
2
$\begingroup$

I guess this class is way too small, but since the questions is still unanswered, I will give you an example I like.

An EFG (Edge Firing Game) is defined from an undirected graph $G$ with a distinguished vertex called the sink. It starts from an orientation of $G$ and generates a set $L$ of orientations as follows. The initial orientation is in $L$, and if an orientation is in $L$ and has a vertex (other than the sink) with only incoming edges, then the orientation obtained by reversing all these edges also is in $L$.

                      EFG lattice

This operation defines a relation between the orientations in $L$, see above example (the sink is the black square); it is the covering relation of a distributive lattice. This was shown by James Propp in 1993 together with many other interesting results on lattices and orientations.

Interestingly, this game actually encodes all distributive lattices: each of them may be obtained from an EFG, which we have shown in 2001.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The question asks for a lattice whose elements are the unlabeled graphs on $n$ vertices. What you're describing is a method for constructing a lattice given some graph. $\endgroup$
    – Sam Hopkins
    Commented Jan 11, 2021 at 21:36
  • $\begingroup$ Well, one may view it as a lattice on a set of directed graphs (with the same underlying undirected graph), and since the question says that a lattice "on a (reasonably) large subset" is interesting, I gave it a try. But I do agree that, certainly, this class is not "reasonably" large, and that this does not make a very relevant answer to the question :/ $\endgroup$
    – Matthieu Latapy
    Commented Jan 11, 2021 at 21:49

You must log in to answer this question.

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