most recent 30 from http://mathoverflow.net 2013-05-19T03:43:35Z http://mathoverflow.net/feeds/question/70899 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70899/classes-of-finite-graphs-closed-under-substitution Stefan Geschke 2011-07-21T12:45:42Z 2011-12-03T19:22:12Z

<p>Given graphs $G$ and $H$ and vertex $v$ of $H$, the graph $G\otimes_v H$ is the graph obtained by replacing the vertex $v$ in $G$ by a copy of $H$. The vertices in the copy of $H$ are connected to the other vertices of $G$ in the same way as $v$ was connected to these vertices. $G\otimes_v H$ is obtained by substitution of $H$ for $v$.</p> <p>Call a class $\mathcal C$ of finite graphs closed if it is closed under isomorphism, induced subgraphs and substitution.<br> The following classes of finite graphs are closed:</p> <p>Empty class, class of singletons, class of complete graphs, class of graphs without edges, class of graphs without induced paths of length 4 ($P_4$-free graphs), class of perfect graphs, class of all finite graphs.</p> <p>The closed classes form a complete lattice with respect to set-theoretic inclusion. The empty class is the smallest, the smallest above that are the singletons, minimal above the singletons are empty and complete graphs, minimal above these two incomparable classes is the class of $P_4$-free graphs. On top is the class of all finite graphs. Also, this lattice has antichains of the maximal possible size $2^{\aleph_0}$. All chains are countable since we are effectively working with subsets of a fixed countable set, the set of all finite graphs whose vertices are natural numbers.</p> <p>Has this lattice been studied systematically? Are there any structural results known apart from the easy ones mentioned above? What if we modify our notion of closed class to include closure under complementation? In the list of examples above, this would only get rid of the classes of complete and of empty graphs.</p>

http://mathoverflow.net/questions/70899/classes-of-finite-graphs-closed-under-substitution/77538#77538 Gus Wiseman 2011-10-08T14:47:17Z 2011-10-08T15:30:49Z

<p>You might redefine substitution as a <em>family</em> of replacements, one for each vertex. I am not sure if you are interested in enumeration, but for connected graphs I think your classes can then be construed as multicategories with morphisms $G\otimes \eta\rightarrow \eta$ where $\eta$ is a suitably indexed family of graphs, or as categories with $G\rightarrow G\otimes \eta$. Either way, the associativity concept derives from the lattice and decomposition structure of connected partitions of connected graphs. If you are interested in this approach I can provide a preprint of my thesis.</p>