***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * This information is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * ***************************************************************************** ----------------------------------------------------------------------------- Statistic identifier: St001734 ----------------------------------------------------------------------------- Collection: Graphs ----------------------------------------------------------------------------- Description: The lettericity of a graph. Let \$D\$ be a digraph on \$k\$ vertices, possibly with loops and let \$w\$ be a word of length \$n\$ whose letters are vertices of \$D\$. The letter graph corresponding to \$D\$ and \$w\$ is the graph with vertex set \$\{1,\dots,n\}\$ whose edges are the pairs \$(i,j)\$ with \$i < j\$ sucht that \$(w_i, w_j)\$ is a (directed) edge of \$D\$. ----------------------------------------------------------------------------- References: [1] PetkovÅ¡ek, M. Letter graphs and well-quasi-order by induced subgraphs [[MathSciNet:1844046]] ----------------------------------------------------------------------------- Code: # very silly code, see PetkovÅ¡ek for a characterisation def letter_graph(w, D): """ INPUT: - w, a word of length n with letters being vertices of D - D, a digraph, loops allowed OUTPUT: - a k-letter graph with n vertices """ n = len(w) E = [(i,j) for i in range(n) for j in range(i) if D.has_edge(w[i], w[j])] return Graph([list(range(n)), E]) from sage.misc.lazy_list import lazy_list from sage.databases.findstat import FindStatCollection @cached_function def letter_graphs(n, k): """ The set of all k-letter graphs with n vertices. """ n_graphs = FindStatCollection(20).levels_with_sizes() c_graphs = set() def graph_iterator(): c_digraphs = set() for L in subsets(range(k)): for Ds in digraphs(k): D = DiGraph([Ds.vertices(), Ds.edges() + [(l,l) for l in L]], loops = True) D = D.canonical_label().copy(immutable=True) if D in c_digraphs: continue c_digraphs.add(D) for w in Words(alphabet=D.vertices(), length=n): G = letter_graph(w, D).canonical_label().copy(immutable=True) if G not in c_graphs: c_graphs.add(G) yield(G) if n in n_graphs and len(c_graphs) == n_graphs[n]: return return lazy_list(graph_iterator()) def statistic(G): G = G.canonical_label().copy(immutable=True) n = G.num_verts() for k in range(1, n+1): if G in letter_graphs(n, k): return k ----------------------------------------------------------------------------- Statistic values: ([],1) => 1 ([],2) => 1 ([(0,1)],2) => 1 ([],3) => 1 ([(1,2)],3) => 2 ([(0,2),(1,2)],3) => 2 ([(0,1),(0,2),(1,2)],3) => 1 ([],4) => 1 ([(2,3)],4) => 2 ([(1,3),(2,3)],4) => 2 ([(0,3),(1,3),(2,3)],4) => 2 ([(0,3),(1,2)],4) => 2 ([(0,3),(1,2),(2,3)],4) => 2 ([(1,2),(1,3),(2,3)],4) => 2 ([(0,3),(1,2),(1,3),(2,3)],4) => 2 ([(0,2),(0,3),(1,2),(1,3)],4) => 2 ([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 2 ([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 1 ([],5) => 1 ([(3,4)],5) => 2 ([(2,4),(3,4)],5) => 2 ([(1,4),(2,4),(3,4)],5) => 2 ([(0,4),(1,4),(2,4),(3,4)],5) => 2 ([(1,4),(2,3)],5) => 3 ([(1,4),(2,3),(3,4)],5) => 2 ([(0,1),(2,4),(3,4)],5) => 3 ([(2,3),(2,4),(3,4)],5) => 2 ([(0,4),(1,4),(2,3),(3,4)],5) => 2 ([(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(1,3),(1,4),(2,3),(2,4)],5) => 2 ([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 2 ([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 3 ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 2 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,4),(1,3),(2,3),(2,4)],5) => 3 ([(0,1),(2,3),(2,4),(3,4)],5) => 2 ([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 2 ([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 2 ([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 3 ([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 3 ([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 2 ([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 3 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 3 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2 ([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 1 ([],6) => 1 ([(4,5)],6) => 2 ([(3,5),(4,5)],6) => 2 ([(2,5),(3,5),(4,5)],6) => 2 ([(1,5),(2,5),(3,5),(4,5)],6) => 2 ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 2 ([(2,5),(3,4)],6) => 3 ([(2,5),(3,4),(4,5)],6) => 2 ([(1,2),(3,5),(4,5)],6) => 3 ([(3,4),(3,5),(4,5)],6) => 2 ([(1,5),(2,5),(3,4),(4,5)],6) => 2 ([(0,1),(2,5),(3,5),(4,5)],6) => 3 ([(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 2 ([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,5),(1,5),(2,4),(3,4)],6) => 3 ([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 3 ([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 2 ([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 2 ([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,4),(2,3)],6) => 3 ([(1,5),(2,4),(3,4),(3,5)],6) => 3 ([(0,1),(2,5),(3,4),(4,5)],6) => 3 ([(1,2),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 3 ([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 3 ([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 3 ([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 3 ([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 4 ([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 2 ([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 3 ([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => 3 ([(0,1),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,5),(1,5),(2,3),(2,4),(3,4)],6) => 3 ([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6) => 3 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6) => 3 ([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 3 ([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6) => 3 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6) => 3 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6) => 3 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 2 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 3 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 3 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6) => 3 ([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6) => 3 ([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 3 ([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 4 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6) => 2 ([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 3 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6) => 2 ([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6) => 3 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6) => 2 ([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 2 ([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6) => 3 ([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 3 ([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6) => 3 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 3 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 4 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 3 ([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 3 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2 ([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1 ----------------------------------------------------------------------------- Created: Jul 09, 2021 at 12:04 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Jul 09, 2021 at 12:04 by Martin Rubey