*****************************************************************************
* www.FindStat.org - The Combinatorial Statistic Finder *
* *
* Copyright (C) 2019 The FindStatCrew <info@findstat.org> *
* *
* 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