Robertson-Seymour

Does a given rule preserve forbidden minors?

Enumerate graphs; then apply the rule to all graphs. What are the connected components in the result?

For strings, is it forbidden words?

In[]:=
EnumerateSubstitutionSystemRules[{22,22},2]
Out[]=
In[]:=
StringTuples["AB",4]
Out[]=
{AAAA,AAAB,AABA,AABB,ABAA,ABAB,ABBA,ABBB,BAAA,BAAB,BABA,BABB,BBAA,BBAB,BBBA,BBBB}
Each string will map to several strings under the rule....
In[]:=
InteractiveListSelectorSW[ParallelMapMonitored[MultiwaySystem[#,StringTuples["AB",4],4,"StatesGraphStructure"]#&,EnumerateSubstitutionSystemRules[{22,22},2]]]
Out[]=
In[]:=
WeaklyConnectedGraphComponents[MultiwaySystem[#,StringTuples["AB",4],4,"StatesGraphStructure"]]&/@{{"AA""BB","AB""BA"},{"AA""BB","BB""AA"},{"AB""AA","BB""BA"}}
Out[]=
In[]:=
Map[VertexList,%,{2}]
Out[]=
{{{ABAB,AABB,BAAB,ABBA,AAAA,BBBB,BABA,BBAA},{BABB,ABBB,BAAA,BBAB,ABAA,AAAB,BBBA,AABA}},{{BBBB,BAAB,AABB,BBAA,AAAA,ABBA},{BBAB,AAAB,ABBB,ABAA},{BABB,BAAA,BBBA,AABA}},{{ABAB,ABBB,ABAA,AAAB,AABB,ABBA,AAAA,AABA},{BABB,BBBB,BAAB,BABA,BBAB,BBBA,BAAA,BBAA}}}
{{"ABAB","AABB","BAAB","ABBA","AAAA","BBBB","BABA","BBAA"},{"BABB","ABBB","BAAA","BBAB","ABAA","AAAB","BBBA","AABA"}}
Even vs. odd numbers of letters
In[]:=
Union[Flatten[StringPartition[#,2,1]&/@{"BABB","ABBB","BAAA","BBAB","ABAA","AAAB","BBBA","AABA"}]]
Out[]=
{AA,AB,BA,BB}
In[]:=
Union[Flatten[StringPartition[#,3,1]&/@{"BABB","ABBB","BAAA","BBAB","ABAA","AAAB","BBBA","AABA"}]]

Graphs

Enumerate all 8-node graphs

R-S

For families closed under taking minors
[ Maybe only undirected ]

https://en.wikipedia.org/wiki/Forbidden_graph_characterization

R-S theorem

This can’t be a subgraph.... [not can it be a minor]