Robertson-Seymour
Robertson-Seymour
Does a given rule preserve forbidden minors?
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?
For strings, is it forbidden words?
In[]:=
EnumerateSubstitutionSystemRules[{22,22},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[{22,22},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
Graphs
Graphs
Enumerate all 8-node graphs
R-S
R-S
For families closed under taking minors
[ Maybe only undirected ]
https://en.wikipedia.org/wiki/Forbidden_graph_characterization
https://en.wikipedia.org/wiki/Forbidden_graph_characterization
R-S theorem
R-S theorem
This can’t be a subgraph.... [not can it be a minor]