- FindStat

Your data matches 86 different statistics following compositions of up to 3 maps.
(click to perform a complete search on your data)

Matching statistic: St000624
(load all 18 compositions to match this statistic)

Mapping

St000624: Permutations ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => 0
[2,1] => 0
[1,2,3] => 0
[1,3,2] => 1
[2,1,3] => 0
[2,3,1] => 1
[3,1,2] => 0
[3,2,1] => 0
[1,2,3,4] => 0
[1,2,4,3] => 1
[1,3,2,4] => 1
[1,3,4,2] => 1
[1,4,2,3] => 1
[1,4,3,2] => 1
[2,1,3,4] => 0
[2,1,4,3] => 1
[2,3,1,4] => 1
[2,3,4,1] => 1
[2,4,1,3] => 1
[2,4,3,1] => 1
[3,1,2,4] => 0
[3,1,4,2] => 1
[3,2,1,4] => 0
[3,2,4,1] => 1
[3,4,1,2] => 1
[3,4,2,1] => 1
[4,1,2,3] => 0
[4,1,3,2] => 1
[4,2,1,3] => 0
[4,2,3,1] => 1
[4,3,1,2] => 0
[4,3,2,1] => 0
[1,2,3,4,5] => 0
[1,2,3,5,4] => 1
[1,2,4,3,5] => 1
[1,2,4,5,3] => 1
[1,2,5,3,4] => 2
[1,2,5,4,3] => 2
[1,3,2,4,5] => 1
[1,3,2,5,4] => 2
[1,3,4,2,5] => 1
[1,3,4,5,2] => 1
[1,3,5,2,4] => 2
[1,3,5,4,2] => 2
[1,4,2,3,5] => 1
[1,4,2,5,3] => 2
[1,4,3,2,5] => 1
[1,4,3,5,2] => 2
[1,4,5,2,3] => 2
[1,4,5,3,2] => 2

Description

The normalized sum of the minimal distances to a greater element. Set

$\pi_0 = \pi_{n+1} = n+1$ , then this statistic is

$\sum_{i=1}^n \min_d(\pi_{i-1-d}>\pi_i\text{ or }\pi_{i+1+d}>\pi_i)$ A closely related statistic appears in [1]. The generating function for the sequence of maximal values attained on

$\mathfrak S_r$ ,

$r\geq 0$ apparently satisfies the functional equation

$(x-1)^2 (x+1)^3 f(x^2) - (x-1)^2 (x+1) f(x) + x^3 = 0.$

Matching statistic: St000272

Mapping

Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St000272: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 0
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 0
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,5,3,2] => [.,[[[.,[.,.]],.],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0

Description

The treewidth of a graph. A graph has treewidth zero if and only if it has no edges. A connected graph has treewidth at most one if and only if it is a tree. A connected graph has treewidth at most two if and only if it is a series-parallel graph.

Matching statistic: St000362

Mapping

Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St000362: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 0
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 0
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,5,3,2] => [.,[[[.,[.,.]],.],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0

Description

The size of a minimal vertex cover of a graph. A '''vertex cover''' of a graph

$G$ is a subset

$S$ of the vertices of

$G$ such that each edge of

$G$ contains at least one vertex of

$S$ . Finding a minimal vertex cover is an NP-hard optimization problem.

Matching statistic: St000536

Mapping

Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St000536: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 0
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 0
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 0
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 0
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 1
[1,4,5,3,2] => [.,[[[.,[.,.]],.],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 0

Description

The pathwidth of a graph.

Matching statistic: St001176

Mapping

Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00110: Posets —Greene-Kleitman invariant⟶ Integer partitions
St001176: Integer partitions ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => [2]
 => 0
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => [2]
 => 0
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => [2,1]
 => 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => [2,1]
 => 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,4,5,3,2] => [.,[[[.,[.,.]],.],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0

Description

The size of a partition minus its first part. This is the number of boxes in its diagram that are not in the first row.

Matching statistic: St001214

Mapping

Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00110: Posets —Greene-Kleitman invariant⟶ Integer partitions
St001214: Integer partitions ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => [2]
 => 0
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => [2]
 => 0
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => [2,1]
 => 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => [2,1]
 => 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => [3]
 => 0
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => [3,1]
 => 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => [3,1]
 => 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => [4]
 => 0
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => [4,1]
 => 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => [4,1]
 => 1
[1,4,5,3,2] => [.,[[[.,[.,.]],.],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => [5]
 => 0

Description

The aft of an integer partition. The aft is the size of the partition minus the length of the first row or column, whichever is larger. See also [[St000784]].

Matching statistic: St000822

Mapping

Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St000822: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 1 = 0 + 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 1 = 0 + 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2 = 1 + 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2 = 1 + 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,5,3,2] => [.,[[[.,[.,.]],.],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1

Description

The Hadwiger number of the graph. Also known as clique contraction number, this is the size of the largest complete minor.

Matching statistic: St001580

Mapping

Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St001580: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 1 = 0 + 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 1 = 0 + 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2 = 1 + 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2 = 1 + 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,5,3,2] => [.,[[[.,[.,.]],.],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1

Description

The acyclic chromatic number of a graph. This is the smallest size of a vertex partition

$\{V_1,\dots,V_k\}$ such that each

$V_i$ is an independent set and for all

$i,j$ the subgraph inducted by

$V_i\cup V_j$ does not contain a cycle.

Matching statistic: St001670

Mapping

Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St001670: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 1 = 0 + 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 1 = 0 + 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2 = 1 + 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2 = 1 + 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,5,3,2] => [.,[[[.,[.,.]],.],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1

Description

The connected partition number of a graph. This is the maximal number of blocks of a set partition

$P$ of the set of vertices of a graph such that contracting each block of

$P$ to a single vertex yields a clique. Also called the pseudoachromatic number of a graph. This is the largest

$n$ such that there exists a (not necessarily proper)

$n$ -coloring of the graph so that every two distinct colors are adjacent.

Matching statistic: St001963

Mapping

Mp00061: Permutations —to increasing tree⟶ Binary trees
Mp00013: Binary trees —to poset⟶ Posets
Mp00198: Posets —incomparability graph⟶ Graphs
St001963: Graphs ⟶ ℤResult quality: 100% ●values known / values provided: 100%●distinct values known / distinct values provided: 100%

Values

[1,2] => [.,[.,.]]
 => ([(0,1)],2)
 => ([],2)
 => 1 = 0 + 1
[2,1] => [[.,.],.]
 => ([(0,1)],2)
 => ([],2)
 => 1 = 0 + 1
[1,2,3] => [.,[.,[.,.]]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[1,3,2] => [.,[[.,.],.]]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[2,1,3] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2 = 1 + 1
[2,3,1] => [[.,[.,.]],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[3,1,2] => [[.,.],[.,.]]
 => ([(0,2),(1,2)],3)
 => ([(1,2)],3)
 => 2 = 1 + 1
[3,2,1] => [[[.,.],.],.]
 => ([(0,2),(2,1)],3)
 => ([],3)
 => 1 = 0 + 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[1,4,3,2] => [.,[[[.,.],.],.]]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,1,4,3] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[2,4,3,1] => [[.,[[.,.],.]],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,1,4,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,2,1,4] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,2,4,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[3,4,2,1] => [[[.,[.,.]],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,1,3,2] => [[.,.],[[.,.],.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,2,1,3] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,2,3,1] => [[[.,.],[.,.]],.]
 => ([(0,3),(1,3),(3,2)],4)
 => ([(2,3)],4)
 => 2 = 1 + 1
[4,3,1,2] => [[[.,.],.],[.,.]]
 => ([(0,3),(1,2),(2,3)],4)
 => ([(1,3),(2,3)],4)
 => 2 = 1 + 1
[4,3,2,1] => [[[[.,.],.],.],.]
 => ([(0,3),(2,1),(3,2)],4)
 => ([],4)
 => 1 = 0 + 1
[1,2,3,4,5] => [.,[.,[.,[.,[.,.]]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,3,5,4] => [.,[.,[.,[[.,.],.]]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,2,4,5,3] => [.,[.,[[.,[.,.]],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,2,5,4,3] => [.,[.,[[[.,.],.],.]]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,4,5,2] => [.,[[.,[.,[.,.]]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,3,5,4,2] => [.,[[.,[[.,.],.]],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
 => ([(0,4),(1,4),(2,3),(4,2)],5)
 => ([(3,4)],5)
 => 2 = 1 + 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
 => ([(0,4),(1,2),(2,4),(4,3)],5)
 => ([(2,4),(3,4)],5)
 => 2 = 1 + 1
[1,4,5,3,2] => [.,[[[.,[.,.]],.],.]]
 => ([(0,4),(2,3),(3,1),(4,2)],5)
 => ([],5)
 => 1 = 0 + 1

Description

The tree-depth of a graph. The tree-depth

$\operatorname{td}(G)$ of a graph

$G$ whose connected components are

$G_1,\ldots,G_p$ is recursively defined as

$\operatorname{td}(G)=\begin{cases} 1, & \text{if }|G|=1\\ 1 + \min_{v\in V} \operatorname{td}(G-v), & \text{if } p=1 \text{ and } |G| > 1\\ \max_{i=1}^p \operatorname{td}(G_i), & \text{otherwise} \end{cases}$ Nešetřil and Ossona de Mendez [2] proved that the tree-depth of a connected graph is equal to its minimum elimination tree height and its centered chromatic number (fewest colors needed for a vertex coloring where every connected induced subgraph has a color that appears exactly once). Tree-depth is strictly greater than [[St000536|pathwidth]]. A [[St001120|longest path]] in

$G$ has at least

$\operatorname{td}(G)$ vertices [3].

The following 76 statistics, ordered by result quality, also match your data. Click on any of them to see the details.

St001907The number of Bastidas - Hohlweg - Saliola excedances of a signed permutation. St001630The global dimension of the incidence algebra of the lattice over the rational numbers. St000668The least common multiple of the parts of the partition. St000707The product of the factorials of the parts. St000708The product of the parts of an integer partition. St000933The number of multipartitions of sizes given by an integer partition. St001767The largest minimal number of arrows pointing to a cell in the Ferrers diagram in any assignment. St001330The hat guessing number of a graph. St000515The number of invariant set partitions when acting with a permutation of given cycle type. St000815The number of semistandard Young tableaux of partition weight of given shape. St000937The number of positive values of the symmetric group character corresponding to the partition. St001603The number of colourings of a polygon such that the multiplicities of a colour are given by a partition. St000698The number of 2-rim hooks removed from an integer partition to obtain its associated 2-core. St001605The number of colourings of a cycle such that the multiplicities of colours are given by a partition. St000454The largest eigenvalue of a graph if it is integral. St000455The second largest eigenvalue of a graph if it is integral. St000260The radius of a connected graph. St000704The number of semistandard tableaux on a given integer partition with minimal maximal entry. St001878The projective dimension of the simple modules corresponding to the minimum of L in the incidence algebra of the lattice L. St000620The number of standard tableaux of shape equal to the given partition such that the minimal cyclic descent is odd. St000681The Grundy value of Chomp on Ferrers diagrams. St000714The number of semistandard Young tableau of given shape, with entries at most 2. St000770The major index of an integer partition when read from bottom to top. St000929The constant term of the character polynomial of an integer partition. St001123The multiplicity of the dual of the standard representation in the Kronecker square corresponding to a partition. St001597The Frobenius rank of a skew partition. St001877Number of indecomposable injective modules with projective dimension 2. St001124The multiplicity of the standard representation in the Kronecker square corresponding to a partition. St000318The number of addable cells of the Ferrers diagram of an integer partition. St000771The largest multiplicity of a distance Laplacian eigenvalue in a connected graph. St000772The multiplicity of the largest distance Laplacian eigenvalue in a connected graph. St001864The number of excedances of a signed permutation. St001960The number of descents of a permutation minus one if its first entry is not one. St001128The exponens consonantiae of a partition. St000284The Plancherel distribution on integer partitions. St000632The jump number of the poset. St000901The cube of the number of standard Young tableaux with shape given by the partition. St000298The order dimension or Dushnik-Miller dimension of a poset. St000640The rank of the largest boolean interval in a poset. St000845The maximal number of elements covered by an element in a poset. St000846The maximal number of elements covering an element of a poset. St001491The number of indecomposable projective-injective modules in the algebra corresponding to a subset. St001896The number of right descents of a signed permutations. St000307The number of rowmotion orbits of a poset. St001624The breadth of a lattice. St001621The number of atoms of a lattice. St001487The number of inner corners of a skew partition. St001632The number of indecomposable injective modules

$I$ with

$dim Ext^1(I,A)=1$ for the incidence algebra A of a poset. St001876The number of 2-regular simple modules in the incidence algebra of the lattice. St001820The size of the image of the pop stack sorting operator. St000259The diameter of a connected graph. St000302The determinant of the distance matrix of a connected graph. St000466The Gutman (or modified Schultz) index of a connected graph. St000467The hyper-Wiener index of a connected graph. St000777The number of distinct eigenvalues of the distance Laplacian of a connected graph. St001645The pebbling number of a connected graph. St001604The multiplicity of the irreducible representation corresponding to a partition in the relabelling action on polygons. St000848The balance constant multiplied with the number of linear extensions of a poset. St000849The number of 1/3-balanced pairs in a poset. St000850The number of 1/2-balanced pairs in a poset. St001095The number of non-isomorphic posets with precisely one further covering relation. St001582The grades of the simple modules corresponding to the points in the poset of the symmetric group under the Bruhat order. St001823The Stasinski-Voll length of a signed permutation. St001946The number of descents in a parking function. St001860The number of factors of the Stanley symmetric function associated with a signed permutation. St001905The number of preferred parking spots in a parking function less than the index of the car. St001935The number of ascents in a parking function. St001569The maximal modular displacement of a permutation. St001773The number of minimal elements in Bruhat order not less than the signed permutation. St001574The minimal number of edges to add or remove to make a graph regular. St001576The minimal number of edges to add or remove to make a graph vertex transitive. St001742The difference of the maximal and the minimal degree in a graph. St000408The number of occurrences of the pattern 4231 in a permutation. St000440The number of occurrences of the pattern 4132 or of the pattern 4231 in a permutation. St000036The evaluation at 1 of the Kazhdan-Lusztig polynomial with parameters given by the identity and the permutation. St001570The minimal number of edges to add to make a graph Hamiltonian.