T M Michelitsch

G A Maugin

F C G A Nicolleau

A F Nowakowski

S Derogar

DISPERSION RELATIONS AND WAVE OPERATORS IN SELF-SIMILAR QUASI-CONTINUOUS LINEAR CHAINS

Keywords: Self-similarity, self-similar functions, affine transformations, Weierstrass-Mandelbrot function, fractal functions, fractals, power laws, fractional integrals PACS: 05.50.+q 81.05.Zx 63.20.D-

We construct self-similar functions and linear operators to deduce a self-similar variant of the Laplacian operator and of the D'Alembertian wave operator. The exigence of self-similarity as a symmetry property requires the introduction of non-local particle-particle interactions. We derive a self-similar linear wave operator describing the dynamics of a quasi-continuous linear chain of infinite length with a spatially self-similar distribution of nonlocal inter-particle springs. The self-similarity of the nonlocal harmonic particle-particle interactions results in a dispersion relation of the form of a Weierstrass-Mandelbrot function which exhibits self-similar and fractal features. We also derive a continuum approximation which relates the self-similar Laplacian to fractional integrals and yields in the low-frequency regime a power law frequency-dependence of the oscillator density.

Introduction

In the seventies of the last century the development of the Fractal Geometry by Mandelbrot [START_REF] Mandelbrot | Fractals, Form, Chance, and Dimension[END_REF] launched a scientific revolution. However, the mathematical roots of this discipline originate much earlier in the 19 th century [START_REF] Kummer | [END_REF]. The superior electromagnetic properties of "fractal antennae" have been known already for a while [3,4]. More recently one found by means of numerical simulations that fractal gaskets such as the Sierpinski gasket reveal interesting vibrational properties [START_REF] Bondarenko | The 9th Russian-Korean International Symposium[END_REF]. Meanwhile physical problems in fractal and self-similar structures or media become more and more a subject of interest also in analytical mechanics and engineering science. This is true in statics and dynamics. However technological exploitations of effects based on self-similarity and "fractality" are still very limited due to a lack of fundamental understanding of the role of the self-similar symmetry. An improved understanding could raise an enormous new field for basic research and applications in a wide range of disciplines including fluid mechanics and the mechanics of granular media and solids. Some initial steps have been performed (see papers [START_REF] Bondarenko | The 9th Russian-Korean International Symposium[END_REF][START_REF] Kigami | [END_REF]7,8,9,10] and the references therein). However a generally accepted "fractal mechanics" has yet to be developed. Therefore, it is highly desirable to develop sufficiently simple models which are on the one hand accessible to a mathematical-analytical framework and on the other hand which capture the essential features imposed by self-similar scale invariant symmetry. The goal of this demonstration is to develop such a model.

Several significant contributions of fractal and self-similar chains and lattices have been presented [13,14,15,16]. In these papers problems on discrete lattices with fractal features are addressed. Closed form solutions for the dynamic Green's function and the vibrational spectrum of a linear chain with spatially exponential properties are developed in a recent paper [11]. A similar fractal type of linear chain as in the present paper has been considered very recently by Tarasov [7]. Unlike in the present paper the chain considered by Tarasov in [7] is discrete, i.e. there remains a characteristic length scale which is given by the next-neighbor distance of the particles.

In contrast to all these works we analyze in the present paper vibrational properties in a quasicontinuous linear chain with (in the self-similar limiting case) infinitesimal lattice spacing with a non-local spatially self-similar distribution of power-law-scaled harmonic inter-particle interactions (springs). In this way we avoid the appearance of a characteristic length scale in our chain model. It seems there are analogue situations in turbulence [17] and other areas where the present interdisciplinary approach could be useful.

Our demonstration is organized as follows: § 3 is devoted to the construction of self-similar functions and operators where a self-similar variant of the Laplacian is deduced. This Laplacian gets his physical justification in § 4. It is further shown in § 3 that in a continuum approximation this Laplacian takes the form of fractional integrals. In § 4 we consider a self-similar quasi-continuous linear chain with self-similar harmonic interactions. The equation of motion of this chain takes the form of a self-similar wave equation containing the self-similar Laplacian defined in § 3 leading to a dispersion relation having the form of the Weierstrass-Mandelbrot function which is a self-similar and for a certain parameter range also a fractal function.

Construction of self-similar functions and linear operators

In this paragraph we define the term "self-similarity" with respect to functions and operators. We call a scalar function φ(h) exact self-similar with respect to variable h if the condition

φ(Nh) = Λφ(h) (1)
is satisfied for all values h > 0 of the scalar variable h. We call (1) the "affine problem" 1 where N is a fixed parameter and Λ = N δ represents a continuous set of admissible eigenvalues. The band of admissible δ = ln Λ ln N is to be determined. A function φ(h) satisfying (1) for a certain N and admissible Λ = N δ represents an unknown "solution" to the affine problem of the form φ N,δ (h) and is to be determined.

As we will see below for a given N solutions φ(h) exist only in a certain range of admissible Λ. From the definition of the problem follows that if φ(h) is a solution of (1) it is also a solution of φ(N s h) = Λ s φ(h) where s ∈ Z is discrete and can take all positive and negative integers including zero. We emphasize that non-integer s are not admitted. The discrete set of pairs Λ s , N s are for all s ∈ Z related by a power law with the same power δ, i.e. Λ = N δ hence Λ s = (N s ) δ . By replacing Λ and N by Λ -1 and N -1 in (1) defines the identical problem. Hence we can restrict our considerations on fixed values of N > 1.

We can consider the affine problem (1) as the eigenvalue problem for a linear operator ÂN with a certain given fixed parameter N and eigenfunctions φ(h) to be determined which correspond to an admissible range of eigenvalues Λ = N δ (or equivalently to an admissible range of exponent δ = ln Λ/ln N ). For a function f (x, h) we denote by ÂN (h)f (x, h) =: f (x, Nh) when the affine transformation is only performed with respect to variable h.

We assume Λ, N ∈ R for physical reasons without too much loss of generality to be real and positive. For our convenience we define the "affine" operator ÂN as follows

ÂN f (h) =: f (Nh) (2)
It is easily verified that the affine operator ÂN is linear, i.e.

ÂN (c

1 f 1 (h) + c 2 f 2 (h)) = c 1 f 1 (Nh) + c 2 f 2 (Nh) (3)
and

Âs N f (h) = f (N s h), s = 0 ± 1, ±2, .. ± ∞ (4)
We can define affine operator functions for any smooth function g(τ ) that can be expanded into a Maclaurin series as

g(τ ) = ∞ s=0 a s τ s (5)
We define an affine operator function in the form

g(ξ ÂN ) = ∞ s=0 a s ξ s Âs N (6)
where ξ denotes a scalar parameter. The operator function which is defined by (6) acts on a function f (h) as follows

g(ξ ÂN )f (h) = ∞ s=0 a s ξ s f (N s h) (7)
where relation (4) with expansion (6) has been used. The convergence of series (7) has to be verified for a function f (h) to be admissible. An explicit representation of the affine operator ÂN can be obtained when we write

f (h) = f (e ln h ) = f (ln h) to arrive at ÂN (h) = e ln N d d(ln h) (8)
This relation is immediately verified in view of

ÂN (h)f (h) = e ln N d d(ln h) f (e ln h ) = f (e ln h+ln N ) = f (Nh) (9)
With this machinery we are now able to construct self-similar functions and operators.

Construction of self-similar functions

A self-similar function solving problem ( 1) is formally given by the series

φ(h) = ∞ s=-∞ Λ -s Âs N f (h) = ∞ s=-∞ Λ -s f (N s h) (10)
for any function f (h) for which the series ( 10) is uniformly convergent for all h. We introduce the self-similar operator

TN = ∞ s=-∞ Λ -s Âs N ( 11
)
that fulfils formally the condition of self-similarity ÂN TN = Λ TN and hence (10) solves the affine problem [START_REF] Mandelbrot | Fractals, Form, Chance, and Dimension[END_REF]. In view of the symmetry with respect to inversion of the sign of s in ( 10) and ( 11) we can restrict ourselves to N > 1 (N, Λ ∈ R) without any loss of generality2 : Let us look for admissible functions f (t) for which (10) is convergent. To this end we have to demand simultaneous convergence of the partial sums over positive and negative s. Let us assume that (where we can confine ourselves to t > 0) lim

t→0 f (t) = a 0 t α (12)
For t → ∞ we have to demand that |f (t)| increases not stronger than a power of t, i.e.

lim t→∞ f (t) = c ∞ t β (13)
with a 0 , c ∞ denoting constants. Both exponents α, β ∈ R are allowed to take positive or negative values which do not need to be integers. A brief consideration of partial sums yields the following requirements for Λ = N δ , namely: Summation over s < 0 in (10) requires absolute convergence of a geometrical series leading to the condition for its argument ΛN -α < 1. That is we have to demand δ < α. The partial sum over s > 0 requires absolute convergence of a geometrical series leading to the condition for its argument Λ -1 N β < 1 which corresponds to δ > β. Both conditions are simultaneously met if

N β < Λ = N δ < N α (14)
or equivalently

β < δ = ln Λ ln N < α (15)
Relations ( 14) and ( 15) require additionally β < α, that is only functions f (t) with the behaviour ( 12) and ( 13) with β < α are admissible in (10). The case β = 0 includes for instance certain bounded functions |f (t)| < M such as some periodic functions.

A self-similar analogue to the Laplace operator

In the sprit of ( 10) and (11) we construct an exactly self-similar function from the second difference according to

φ(x, h) = TN (h) (u(x + h) + u(x -h) -2u(x)) (16)
where u(..) denotes an arbitrary smooth continuous field variable and TN (h) expresses that the affine operator ÂN (h) acts only on the dependence on h, that is ÂN (h)v(x, h) = v(x, Nh). We have with ξ = Λ -1 the expression

φ(x, h) = ∞ s=-∞ ξ s {u(x + N s h) + u(x -N s h) -2u(x)} (17)
which is a self-similar function with respect to its dependence on h with ÂN (h)φ(x, h) = φ(x, Nh) = ξ -1 φ(x, h) but a regular function with respect to x. The function φ(x, h) exists if the series ( 17) is convergent. Let us assume that u(x) is a smooth function with a convergent Taylor series for any h.

Then we have with u(x ± h) = e ±h d dx u(x) and u(x

+ h) + u(x -h) -2u(x) = e h d dx + e -h d dx -2 u(x)
which can be written as

u(x + h) + u(x -h) -2u(x) = 4 sinh 2 h 2 d dx u(x) = h 2 d 2 dx 2 u(x) + orders h ≥4 (18)
thus α = 2 in criteria ( 12) is met. If we demand u(x) being Fourier transformable we have as necessary condition that

∞ -∞ |u(x)| dx < ∞ (19)
exists. This is true if |u(t)| tends to zero as t → ±∞ as |t| β where β < -1. We have then the condition that

β < 0 < δ = - ln ξ ln N < α = 2 (20)
We will see below that only δ > 0 is physically admissible, i.e. compatible with harmonic particleparticle interactions which decrease with increasing particle-particle distance. The 1D Laplacian ∆ 1 is defined by

∆ 1 u(x) = d 2 dx 2 u(x) = lim τ →0 (u(x + τ ) + u(x -τ ) -2u(x)) τ 2 (21)
Let us now define a self-similar analogue to the 1D Laplacian (21) where we put with ξ = N -δ

∆ (δ,N,τ ) u(x) =: const lim τ →0 τ -λ φ(x, τ ) (22) = const lim τ →0 τ -λ ∞ s=-∞ ξ s (u(x + N s τ ) + u(x -N s τ ) -2u(x)) (23)
where we have introduced a renormalisation-multiplier τ -λ with the unknown power λ to be determined such that the limiting case is finite. The constant factor const indicates that there is a certain arbitrariness in this definition and will be chosen conveniently. Let us consider the limit τ → 0 by the special sequence τ n = N -n h with n → ∞ and h being constant. Unlike in the 1D case (21), the result of this limiting process depends crucially on the choice of the sequence τ n . We see here that the self-similar Laplacian cannot be defined uniquely as in the 1D case. We have (by putting in (22

) const = h λ ) ∆ (δ,N,h) u(x) = lim n→∞ N λn ξ n ∞ s=-∞ ξ s-n u(x + N s-n h) + u(x -N s-n h) -2u(x) (24)
which assumes by replacing s -n → s the form

∆ (δ,N,h) u(x) = φ(x, h) lim n→∞ N -(δ-λ)n (25)
which is only finite and nonzero if λ = δ. The "Laplacian" can then be defined simply by

∆ (δ,N,h) u(x) =: lim n→∞ N δn φ(x, N -n h) = φ(x, h) (26)
or by using ( 16) and ( 18) we can simply write3

∆ (δ,N,h) = 4 TN (h) sinh 2 h 2 ∂ ∂x = 4 ∞ s=-∞ N -δs sinh 2 N s h 2 ∂ ∂x (27)
where TN (h) is the self-similar operator defined in (11). The self-similar analogue of Laplace operator defined by (27) depends on the parameters δ, N, h. We furthermore observe the self-similarity of Laplacian ( 27) with respect to its dependence on h, namely

∆ (δ,N,N h) = N δ ∆ (δ,N,h) (28)

Continuum approximation -link to fractional integrals

For numerical evaluations it may be convenient to utilize a continuum approximation of the self-similar Laplacian (27). To this end we put N = 1 + ǫ (with 0 < ǫ ≪ 1 thus ǫ ≈ ln N) where ǫ is assumed to be "small" and sǫ = v such that dv ≈ ǫ and

N s = (1 + ǫ) v ǫ ≈ e v .
In this approximation N s ≈ e v becomes a (quasi)-continuous variable when s runs through s ∈ Z. Then we can write (10) in the form

φ(h) = ∞ s=-∞ N -sδ f (N s h) ≈ 1 ǫ ∞ -∞ e -δv f (he v )dv (29)
which can be further written with he v = τ (h > 0) and dτ τ = dv and τ (v

→ -∞) = 0 and τ (v → ∞) = ∞ as φ(h) ≈ h δ ǫ ∞ 0 f (τ ) τ 1+δ dτ (30)
In this continuum approximation the function φ(h) obeys the same scaling behaviour as (10), namely φ(hλ) = λ δ φ(h) but in contrast to (10) λ can assume any continuous positive value. This is due to the fact that (30) is holding for N = 1 + ǫ with sufficiently small ǫ > 0 since in this limiting case there exists for any continuous value λ > 0 an m ∈ Z such that N m ≈ λ. The existence requirement for integral (30) leads to the same requirements for f (t) as in (10), namely inequality (15). Application of the approximate relation (30) to Laplacian (27) yields

∆ (δ,ǫ,h) u(x) ≈ h δ ǫ ∞ 0 (u(x -τ ) + u(x + τ ) -2u(x)) τ 1+δ dτ ( 31
)
where this integral exists for β < 0 < δ < 2 and β < -1 because the required existence of integral [START_REF] Miller | An Introduction to the Fractional Calculus and Fractional Differential Equations[END_REF] and relation (18). By performing two partial integrations and by taking into account the vanishing boundary terms at τ = 0 and τ = ∞ for 0 < δ < 2, we can re-write (31) in the form of a convolution of the conventional 1D Laplacian

d 2 u dx 2 (x), namely ∆ (δ,ǫ,h) u(x) ≈ ∞ -∞ g(|x -τ |) d 2 u dτ 2 (τ )dτ (32)
with the kernel

g(|x|) = h δ δ(δ -1)ǫ |x| 1-δ , δ = 1 ( 33
)
where 0 < δ < 2 and g(|x|) = -h ǫ ln |x| for δ = 1. We can further write for δ = 1 (32) in terms of fractional integrals

∆ (δ=2-D,ǫ,h) u(x) ≈ h 2-D ǫ Γ(D) (D -1)(D -2) D -D -∞,x + (-1) D D -D ∞,x ∆ 1 u(x) (34)
where ∆ 1 u(x) = d 2 dx 2 u(x) denotes the conventional 1D-Laplacian and D = 2 -δ > 0 which is positive in the admissible range of 0 < δ < 2. For 0 < δ < 1 the quantity D can be identified with the estimated fractal dimension of the fractal dispersion relation of the Laplacian [18] which is deduced in the next section. In (34) we have introduced the Riemann-Liouville fractional integral D -D a,x which is defined by(e.g. [START_REF] Miller | An Introduction to the Fractional Calculus and Fractional Differential Equations[END_REF][START_REF] Kilbas | Theory and Application of Fractional Differential Equations[END_REF])

D -D a,x v(x) = 1 Γ(D) x a (x -τ ) D-1 v(τ )dτ ( 35
)
where Γ(D) denotes the Γ-function which represents the generalization of the factorial function to non-integer D > 0. The Γ-function is defined as

Γ(D) = ∞ 0 τ D-1 e -τ dτ

The physical chain model

We consider an infinitely long quasi-continuous linear chain of identical particles. Any space-point x corresponds to a "material point" or particle. The mass density of particles is assumed to be spatially homogeneous and equal to one for any space point x. Any particle is associated with one degree of freedom which is represented by the displacement field u(x, t) where x is its spatial (Lagrangian) coordinate and t indicates time. In this sense we consider a quasi continuous spatial distribution of particles. Any particle at space-point x is non-locally connected by harmonic springs of strength ξ s to particles located at x ± N s h, where N > 1 and N ∈ R is not necessarily integer, h > 0, and s = 0, ±1, ±2, .. ± ∞. The requirement of decreasing spring constants with increasing particle-particle distance leads to the requirement that ξ = N -δ < 1 (N > 1) i.e. only chains with δ > 0 are physically admissible. In order to get exact self-similarity we avoid the notion of "next-neighbour particles" in our chain which would be equivalent to the introduction of an internal length scale (the next neighbour distance). To admit particle interactions over arbitrarily close distances N s h → 0 (s → -∞, h = const) our chain has to be quasi-continuous. This is the principal difference to the discrete chain considered recently by Tarasov [7] which is discrete and not self-similar. The Hamiltonian which describes our chain can be written as

H = 1 2 ∞ -∞ u2 (x, t) + V(x, t, h) dx (37)
In the spirit of ( 10) the elastic energy density V(x, t, h) is assumed to be constructed self-similarly, namely4

V(x, t, h) = 1 2 TN (h) (u(x, t) -u(x + h, t)) 2 + (u(x, t) -u(x -h, t)) 2 (38)
where TN (h) is the self-similar operator (11) with ξ = Λ -1 = N -δ to arrive at

V(x, t, h) = 1 2 ∞ s=-∞ ξ s (u(x, t) -u(x + hN s , t)) 2 + (u(x, t) -u(x -hN s , t)) 2 (39)
The elastic energy density V(x, t, h) fulfills the condition of self-similarity with respect to h, namely

ÂN (h)V(x, t, h) = V(x, t, Nh) = ξ -1 V(x, t, h) (40)
We have to demand in our physical model that the energy is finite, i.e. (39) needs to be convergent which yields α = 2 as for the Laplacian (17). To determine β we have to demand that u(x, t) is a Fourier transformable field 5 . Thus we have to have an asymptotic behaviour of |u(x ± τ, t)| → 0 as τ β where β < -1 as τ → ∞. From this follows |u(x, t) -u(x ± τ, t)| 2 behaves then as |u(x, t)| 2 . Hence, the elastic energy density (39) is finite if

0 < δ < 2 (41)
where β < -1. This inequality determines the range of the admissible values of δ in order to achieve convergence. The equation of motion is obtained from

∂ 2 u ∂t 2 = - δH δu (42)
(where δ./δu stands for a functional derivative) to arrive at

∂ 2 u ∂t 2 = - ∞ s=-∞ ξ s (2u(x, t) -u(x + hN s , t) -u(x -hN s , t)) (43)
∂ 2 u ∂t 2 = ∆ (δ,N,h) u(x, t) (44)
with the self-similar Laplacian ∆ (δ,N,h) of equation ( 27). As the elastic energy density (39) the equation of motion is convergent for δ being in the interval (41) where β < -1. We can re-write (44) in the compact form of a wave equation

2 (δ,N,h) u(x, t) = 0 (45)
where 2 (δ,N,h) is the self-similar analogue of the d'Alembertian wave operator having the form

2 (δ,N,h) = ∆ (δ,N,h) - ∂ 2 ∂t 2 (46)
The d'Alembertian (46) with the Laplacian (27) describes the wave propagation in the self-similar chain with Hamiltonian (37). The present approach seems to be useful as a point of departure to establish a generalized theory of wave propagation in self-similar media. Now we determine the dispersion relation, which is constituted by the (negative) eigenvalues of the (semi-)negative definite Laplacian (27). To this end we make use of the fact that the displacement field u(x, t) is Fourier transformable (guaranteed by choosing β < -1) and that the exponentials e ikx are eigenfunctions of the self-similar Laplacian (27). We hence write the Fourier integral

u(x, t) = 1 2π ∞ -∞ ũ(k, t)e ikx dk (47)
to re-write (44) for the Fourier amplitudes ũ(k, t) in the form

∂ 2 ũ ∂t 2 (k, t) = -ω 2 (k) ũ(k, t) (48)
and obtain

ω 2 (kh) = 4 ∞ s=-∞ N -δs sin 2 ( khN s 2 ) ( 49
)
The series (49) describes a Weierstrass-Mandelbrot function which is a continuous and for 0 < δ ≤ 1 a nowhere differentiable function [START_REF] Mandelbrot | Fractals, Form, Chance, and Dimension[END_REF]18]. The Weierstrass-Mandelbrot function (49) fulfills the condition of self-similar symmetry, namely

ω 2 (Nkh) = N δ ω 2 (kh) ( 50
)
where the interval of convergence of the series of the Weierstrass-Mandelbrot function (49) is also given by (41). We emphasize that indeed only exponents δ in the interval (41) are admissible in Hamiltonian (37) with the elastic energy density (39) in order to have a "well-posed" problem. It was shown by Hardy [18] that for ξN > 1 and ξ = N -δ < 1 or equivalently for

0 < δ < 1 (51)
the Weierstrass-Mandelbrot function of the form (49) is not only self-similar but also a fractal curve of (estimated) non-integer fractal (Hausdorff) dimension D = 2 -δ > 1. Figs. 234show dispersion curves ω 2 (kh) for different decreasing values of admissible 0 < δ < 1 and increasing fractal dimension D. Fig. 1 corresponds to the non-fractal case (δ = 1.2 > 1). The increase of the fractal dimension from Figs. 2-4 is indicated by the increasingly irregular harsh behaviour of the curves. In Fig. 4 the fractal dimension of the dispersion curve is with D = 1.9 already close to the plane-filling dimension 2.

To evaluate (49) approximately it is convenient to replace the series by an integral utilizing a similar substitution as in Sec. 3.3 (ǫ ≈ ln N). By doing so we smoothen the Weierstrass-Mandelbrot function (49). It is important to notice that the resulting approximate dispersion relation is hence differentiable and has not any more a fractal dimension D > 1 in the interval (51). For sufficiently "small" |k|h (h > 0), i.e. in the long-wave regime we arrive at

ω 2 (kh) ≈ (h|k|) δ ǫ C (52)
which is only finite if (|k|h) δ is in the order of magnitude of ǫ or smaller. This regime which includes the long-wave limit k → 0 is hence characterized by a power law behaviour ω(k) ≈ Const |k| δ/2 of the dispersion relation. The constant C introduced in (52) is given by the integral

C = 2 ∞ 0 (1 -cos τ ) τ 1+δ dτ ( 53
)
which exists for δ being within interval (41).

This approximation holds for "small" ǫ ≈ ln N = 0 (0 < ǫ ≪ 1)6 which corresponds to the limiting case that N s = e v is continuous. In this limiting case we obtain the oscillator density from [11]

7 ρ(ω) = 2 1 2π d|k| dω (54)
which is normalized such that ρ(ω)dω counts the number (per unit length) of normal oscillators having frequencies within the interval [ω, ω + dω]. We obtain then a power law of the form

ρ(ω) = 2 πδh ǫ C 1 δ ω 2 δ -1 (55)
where δ is restricted within interval (41). We observe hence that the power 2 δ -1 is restricted within the range 0 < 2 δ -1 < ∞ for 0 < δ < 2, especially with always vanishing oscillator density ρ(ω → 0) = 0. We emphasize that neither is the dependence on k of the Weierstrass-Mandelbrot function (49) represented by a continuous |k| δ -dependence nor is this function differentiable with respect to k. Application of ( 54) is hence only justified to be applied to the approximative representation (52) if 0 < ǫ ≪ 1 thus N = 1 + ǫ is sufficiently close to 1 so that N s is a quasi-continuous function when s runs through s ∈ Z. Hence (54) is not generally applicable to (49) for any arbitrary N > 1. We can consider (55) as the low-frequency regime ω → 0 of the oscillator density holding only in the quasi-continuous case N = 1 + ǫ with 0 < ǫ ≪ 1.

Conclusions

We have depicted how self-similar functions and linear operators can be constructed in a simple manner by utilizing a certain category of conventional "admissible" functions. This approach enables us to construct non-local self-similar analogues to the Laplacian and d'Alembert wave operator. The linear self-similar equation of motion describes the propagation of waves in a quasi-continuous linear chain with harmonic non-local self-similar particle-interactions. The complexity which comes into play by the self-similarity of the non-local interactions is completely captured by the dispersion relations which assume the forms of Weierstrass-Mandelbrot functions (49) exhibiting exact self-similarity and for certain parameter combinations (relation (51)) fractal features. In a continuum approximation the self-similar Laplacian is expressed in terms of fractional integrals (eq. ( 34)) leading for small k (long-wave limit) to a power-law dispersion relation (eq. ( 52)) and to a power-law oscillator density (eq. ( 55)) in the low-frequency regime.

The self-similar wave operator (46) with the Laplacian (27) can be generalized to describe wave propagation in fractal and self-similar structures which are fractal subspaces embedded in Euclidean spaces of 1-3 dimensions. The development of such an approach could be a crucial step towards a better understanding of the dynamics in materials with scale hierarchies of internal structures ("multiscale materials") which may be idealized as fractal and self-similar materials.

We hope to inspire further work and collaborations in this direction to develop appropriate approaches useful for the modelling of static and dynamic problems in self-similar and fractal structures in a wider interdisciplinary context.

  positive integers D > 0 the Γ-function reproduces the factorial-function Γ(D) = (D -1)! with D = 1, 2, ..∞.

  δ=1.2 (nonfractal case D=1)

Figure 1 :

 1 Figure 1: Dispersion relation ω 2 (kh) in arbitrary units for N = 1.5 and δ = 1.2

Figure 2 :

 2 Figure 2: Dispersion relation ω 2 (kh) in arbitrary units for N = 1.5 and δ = 0.7

Figure 3 :

 3 Figure 3: Dispersion relation ω 2 (kh) in arbitrary units for N = 1.5 and δ = 0.5

Figure 4 :

 4 Figure 4: Dispersion relation ω 2 (kh) in arbitrary units for N = 1.5 and δ = 0.1

where we restrict here to affine transformations h ′ = N h + c with c = 0.

We also can exclude the trivial case N = 1.

We have to replace d dx → ∂ ∂x if the Laplacian acts on a field u(x, t) as in Sec.

The additional factor 1/2 in the elastic energy avoids double counting.

This assumption defines the (function) space of eigenmodes and corresponds to infinite body boundary conditions.

ǫ = 0 has to be excluded since it corresponds to N = 1.

The additional prefactor "2" takes into account the two branches of the dispersion relation (49) (one for k < 0 and one for k > 0).

Acknowledgements

Fruitful discussions with J.-M. Conoir, D. Queiros-Conde and A. Wunderlin are gratefully acknowledged.


Sergey Kitaev
email: sergey@ru.is

Toufik Mansour
email: toufik@math.haifa.ac.il

Patrice Séébold
email: patrice.seebold@lirmm.fr

Counting ordered patterns in words generated by morphisms

Keywords: morphisms, patterns, rises, descents, inversions, repetitions

We start a general study of counting the number of occurrences of ordered patterns in words generated by morphisms. We consider certain patterns with gaps (classical patterns) and that with no gaps (consecutive patterns). Occurrences of the patterns are known, in the literature, as rises, descents, (non-)inversions, squares and p-repetitions. We give recurrence formulas in the general case, then deducing exact formulas for particular families of morphisms. Many (classical or new) examples are given illustrating the techniques and showing their interest.

Introduction

In algebraic combinatorics, an occurrence of a pattern p in a permutation π is a subsequence of π (of the same length as that of p) whose elements are in the same relative order as those in p. For example, the permutation π = 536241 contains an occurrence of the pattern p = 2431. Babson and Steingrímsson introduced generalized patterns where two adjacent elements of a pattern must also be adjacent in the permutation [START_REF] Babson | Generalized permutation patterns and a classification of the Mahonian statistics[END_REF].

In combinatorics on words, an occurrence of a pattern p in a word u is a factor of u having the same shape as p. For example the word u = abaabaaabab contains an occurrence of the pattern p = ααβααβ.

Burstein [START_REF] Burstein | Enumeration of words with forbidden patterns[END_REF] realized a "mixing" of these two notions by considering ordered alphabets. An occurrence of an (ordered) pattern in a word is a factor or a subsequence having the same shape, and in which the relative order of the letters is the same as that in the pattern. In [START_REF] Kitaev | The Peano curve and counting occurrences of some patterns[END_REF] one computed the number of occurrences of many of ordered patterns in the Peano words. In the present paper we start a general study of counting the number of occurrences of ordered patterns in words generated by morphisms.

Preliminaries

Definitions and notations

We refer to [START_REF] Lothaire | Encyclopedia of Mathematics and its Applications[END_REF] for standard definitions in combinatorics on words.

Let n be a non-negative integer. The incidence matrix of f n is the k × k matrix M (f n ) = (m n,i,j ) 1≤i,j≤k where m n,i,j is the number of occurrences of the letter a i in the word f n (a j ), i.e., m n,i,j = |f n (a j )| ai .

Property 1 For every n ∈ IN, M (f ) n = M (f n ).

Ordered patterns

Let A be a totally ordered alphabet and let ℵ be the ordered alphabet whose letters are the first n positive integers in the usual order (thus ℵ = {1, 2, . . . , n}).

An ordered pattern is any word over ℵ ∪ {#}, # ∈ ℵ, without two consecutive #. If a pattern contains at least one #, not at the very beginning or at the very end, it is an ordered pattern with gaps; otherwise it is an ordered pattern with no gaps. Moreover, in this paper the four ordered patterns u, #u, u#, and #u# are considered to be the same (but of course u#u is not the same pattern as uu). In particular, if x is a word over ℵ, we will write (x#) ℓ or (#x) ℓ to represent the ordered pattern x#x# • • • #x containing l occurrences of the word x.

A word v over A contains an occurrence of the ordered pattern

u = u 1 #u 2 # • • • #u n , u i ∈ ℵ + and n ≥ 1, if v = w 0 v 1 w 1 v 2 w 2 • • • w n-1 v n w n and there exists a literal morphism f : ℵ * → A * such that f (u i ) = v i , 1 ≤ i ≤ n,

Ordered patterns with gaps and morphisms

Let k be an integer (k ≥ 2) and A the k-letter ordered alphabet

A = {a 1 < a 2 < • • • < a k }. Let f be any morphism on A: for 1 ≤ i ≤ k, f (a i ) = a i1 . . . a ip i with p i ≥ 0 (p i = 0 if and only if f (a i ) = ε).

Inversions, non-inversions, and repetitions with gaps of f n

In what follows we are interested in some particular forms of ordered patterns.

In accordance with permutations theory, an inversion (resp. non-inversion) is an occurrence of the ordered pattern 2#1 (resp. 1#2). Repetitions with gaps of one letter are occurrences of the ordered patterns (1#) p , p ≥ 1.

Inversions and non-inversions

Let n be a non-negative integer.

The vector RG(f n ) of non-inversions (resp. vector DG(f n ) of inversions) of f n is the k vector whose i-th entry is the number of occurrences of the ordered pattern 1#2 (resp. 2#1) in the word f n (a i ), i.e.,

RG(f n ) = (|f n (a i )| 1#2 ) 1≤i≤k DG(f n ) = (|f n (a i )| 2#1 ) 1≤i≤k .
Our goal is to obtain recurrence formulas giving the entries of RG(f n+1 ) and

DG(f n+1 ). Since f n+1 = f n • f = f • f n , we have two different ways to compute RG(f n+1 ) and DG(f n+1 ).
Let ℓ be an integer,

1 ≤ ℓ ≤ k. Either |f n+1 (a ℓ )| 1#2 (resp. |f n+1 (a ℓ )| 2#1
) will be obtained from the word f (a ℓ ) and the entries of RG(f n ) (resp. DG(f n )) (see 1. below), or it will be computed from the values of RG(f ) (resp. DG(f )) and f n (a ℓ ) (see 2. below).

1. From f n+1 = f n • f : Since f (a ℓ ) = a ℓ1 . . . a ℓp ℓ , the number of occurrences of the ordered pattern 1#2 in f n+1 (a ℓ ) = f n (f (a ℓ )) = f n (a ℓ1 . . . a ℓp ℓ )

is obtained by adding two values:

• The number of occurrences of the ordered pattern 1#2 in each f n (a ℓi ), 1 ≤ i ≤ p ℓ . Since the ℓ-th column of the incidence matrix of f indicates which letters appear in f (a ℓ ) (and how many times), this number is obtained by multiplying the vector RG(f n ) by the ℓ-th column of M (f ), i.e., it is equal to

k t=1 |f n (a t )| 1#2 • m 1,t,ℓ .
• The number of occurrences of the ordered pattern 1#2 in each of the f n (a ℓi a ℓj ), 1 ≤ i < j ≤ p ℓ , where the letter corresponding to 1 is in f n (a ℓi ) and the letter corresponding to 2 is in f n (a ℓj ). In what follows we will call such an occurrence of 1#2 in f n (a ℓi a ℓj ) an external occurrence of the ordered pattern 1#2 in f n (a ℓi a ℓj ), and denote it |f n (a ℓi a ℓj )| ext 1#2 . The value of |f n (a ℓi a ℓj )| ext 1#2 is obtained by adding, for all the integers r, 1 ≤ r ≤ k -1, the product of the number of occurrences of the letter a r in f n (a ℓi ) (|f n (a ℓi )| ar ) by the number of occurrences of all the letters of f n (a ℓj ) greater than a r (|f n (a ℓj )| as , r + 1 ≤ s ≤ k). This gives

k-1 r=1 (m n,r,ℓi • k s=r+1 m n,s,ℓj ).
The number of external occurrences of 1#2 in all the f n (a ℓi a ℓj ), 1 ≤ i < j ≤ p ℓ , is thus given by

1≤i<j≤p ℓ |f n (a ℓi a ℓj )| ext 1#2 = 1≤i<j≤p ℓ ( k-1 r=1 (m n,r,ℓi • k s=r+1 m n,s,ℓj )). 2. From f n+1 = f • f n . Let q ℓ = |f n (a ℓ )| : f n+1 (a ℓ ) = f (f n (a ℓ )) = f (a ℓ ′ 1 . . . a ℓ ′ q ℓ
). Here the number of occurrences of the ordered pattern 1#2 in f n+1 (a ℓ ) is obtained by adding:

• The number of occurrences of the ordered pattern 1#2 in each f n (a

ℓ ′ i ), 1 ≤ i ≤ q ℓ . As above it is equal to k t=1 |f (a t )| 1#2 • m n,t,ℓ .
• The number of external occurrences of the ordered pattern 1#2 in each of the f (a ℓ ′ i a ℓ ′ j ), 1 ≤ i < j ≤ q ℓ . As above, this number is given by

1≤i<j≤q ℓ |f (a ℓ ′ i a ℓ ′ j )| ext 1#2 = 1≤i<j≤q ℓ ( k-1 r=1 (m 1,r,ℓ ′ i • k s=r+1 m 1,s,ℓ ′ j )).
The same reasoning applies for calculating the entries of DG(f n+1 ), replacing 1#2 by 2#1 and "greater" by "smaller". Thus we have the following.

Proposition 1. For each letter a ℓ ∈ A, let p ℓ and q ℓ be such that f

(a ℓ ) = a ℓ1 . . . a ℓp ℓ and f n (a ℓ ) = a ℓ ′ 1 . . . a ℓ ′ q ℓ
. Then, for all n ∈ IN,

|f n+1 (a ℓ )| 1#2 = 1≤i<j≤q ℓ ( k-1 r=1 (m 1,r,ℓ ′ i • k s=r+1 m 1,s,ℓ ′ j ))+ k t=1 |f (a t )| 1#2 •m n,t,ℓ , (1)
|f n+1 (a ℓ )| 2#1 = 1≤i<j≤q ℓ ( k r=2 (m 1,r,ℓ ′ i • r-1 s=1 m 1,s,ℓ ′ j )) + k t=1 |f (a t )| 2#1 • m n,t,ℓ . (2)
Of course, the analysis we have done above could be realized to compute more complex ordered patterns with gaps, such as 1#23, 1#2#3, • • • The only difficulty is to adapt the computation of external inversions and non-inversions.

Repetitions of one letter

Let n be a non-negative integer and p a positive integer. The vector of p-repetitions with gaps of one letter of f n is the k vector whose i-th entry is the number of occurrences of the ordered pattern (1#) p in the word

f n (a i ), i.e., R p G(f n ) = (|f n (a i )| (1#) p ) 1≤i≤k .
The following is obvious. Proposition 2. For each letter a ℓ ∈ A and for all n ∈ IN,

|f n (a ℓ )| (1#) p = k t=1 m n,t,ℓ p . (3)

Some examples in the binary case

The Thue-Morse morphism The Thue-Morse morphism µ ([10], [START_REF] Prouhet | Mémoire sur quelques relations entre les puissances des nombres[END_REF], [START_REF] Morse | Recurrent geodesics on a surface of negative curvature[END_REF]) is defined by µ(a 1 ) = a 1 a 2 , µ(a 2 ) = a 2 a 1 . It generates the famous Thue-Morse sequence t = µ ω (a 1 ) which has been widely studied.

For every positive integers n, the incidence matrix of µ n is

M (µ n ) = 2 n-1 2 n-1 2 n-1 2 n-1 .
Thus, from equations ( 1), (2), and (3) we obtain

|µ n+1 (a 1 )| 1#2 = |µ n+1 (a 2 )| 1#2 = 2 2(n-1) + |µ n (a 1 )| 1#2 + |µ n (a 2 )| 1#2 , |µ n+1 (a 1 )| 2#1 = |µ n+1 (a 2 )| 2#1 = 2 2(n-1) + |µ n (a 1 )| 2#1 + |µ n (a 2 )| 2#1 , |µ n (a 1 )| (1#) p = |µ n (a 2 )| (1#) p = 2 • 2 n-1 p .
Since RG(µ) = 1 0 and DG(µ) = 0 1 , Proposition 1 gives the following well known result.

Corollary 1. For any integer n ≥ 2,

RG(µ n ) = DG(µ n ) = 2 2n-3 2 2n-3 and R p G(µ n ) = 2 • 2 n-1 p 2 • 2 n-1 p .
The Fibonacci morphism The Fibonacci morphism ϕ is defined by ϕ(a 1 ) = a 1 a 2 , ϕ(a 2 ) = a 1 . It generates the well known Fibonacci sequence f = ϕ ω (a 1 ) which is the prototype of a Sturmian word (see, e.g., [START_REF] Lothaire | Encyclopedia of Mathematics and its Applications[END_REF]).

Let (F n ) n≥-1 be the sequence of Fibonacci numbers:

F -1 = 0, F 0 = 1, F n = F n-1 + F n-2 for n ≥ 1.
The following property of Fibonacci numbers will be useful below.

Property 2 For every positive integer n, F n •F n-2 = F 2 n-1 + 1 if n is even, -1 if n is odd.
An easy computation gives that, for every positive integer n, the incidence

matrix of ϕ n is M (ϕ n ) = F n F n-1 F n-1 F n-2 .
The vector of non-inversions of ϕ is RG(ϕ) = 1 0 . Moreover equation (1) (see Property 2) gives, for n ≥ 1

|ϕ n+1 (a 1 )| 1#2 = m n,1,1 • m n,2,2 + |ϕ n (a 1 )| 1#2 + |ϕ n (a 2 )| 1#2 = F n • F n-2 + |ϕ n (a 1 )| 1#2 + |ϕ n (a 2 )| 1#2 = F 2 n-1 + |ϕ n (a 1 )| 1#2 + |ϕ n (a 2 )| 1#2 + 1 if n is even, -1 if n is odd
The vector of inversions of ϕ is DG(ϕ) = 0 0 . Moreover, equation (2) gives, for n ≥ 1

|ϕ n+1 (a 1 )| 2#1 = m n,2,1 • m n,1,2 + |ϕ n (a 1 )| 2#1 + |ϕ n (a 2 )| 2#1 = F 2 n-1 + |ϕ n (a 1 )| 2#1 + |ϕ n (a 2 )| 2#1 . Now, |ϕ n+1 (a 2 )| 1#2 = |ϕ n (a 1 )| 1#2 and |ϕ n+1 (a 2 )| 2#1 = |ϕ n (a 1 )| 2#1 because ϕ(a 2 ) = a 1 .
From this we obtain formulas to compute, for every n ≥ 0, |ϕ n+2 (a 1 )| 1#2 and |ϕ n+2 (a 1 )| 2#1 from the sequence of Fibonacci numbers.

Corollary 2. For every integer n ≥ 0,

|ϕ n+2 (a 1 )| 2#1 = n p=0 F p F 2 n-p , |ϕ n+2 (a 1 )| 1#2 = |ϕ n+2 (a 1 )| 2#1 + F n + 1 if n is odd, -1 if n is even. Regarding repetitions of one letter, R p G(ϕ) = 1 p + 1 p 1 p
and, for n ≥ 0, the vector R p G(ϕ n+2 ) is obtained from equation (3).

A particular family of morphisms

Let k be an integer (k ≥ 2) and A the k-letter ordered alphabet

A = {a 1 < a 2 < • • • < a k }.
In this section we are interested in morphisms f having the following particularities:

1. there exists a positive integer m such that |f (a

1 )| ai = m, 1 ≤ i ≤ k , 2. there exists a positive integer d such that |f (a 2 . . . a k )| ai = d, 1 ≤ i ≤ k , 3. for every i, j, 1 ≤ i, j ≤ k, |f (a i a j )| ext 1#2 = |f (a j a i )| ext 1#2 .
(Conditions 1. and 2. are particular cases of the more general situation, considered in Theorem 1 below, in which the alphabet A is partitioned in sets A 1 , A 2 , . . ., A n such that, for each A i , the sum of the number of occurrences of each letter in the images of letters of A i is the same.) In this case we are able to give direct formulas to compute |f n+1 (a 1 )| 1#2 and others from m, d, and n. Proposition 3. For every positive integer n,

|f n+1 (a 1 )| 1#2 = m(d + m) n-1 k i=1 |f (a i )| 1#2 + [m(d+m) n-1 -1]m(d+m) n-1 2 k j=1 |f (a j a j )| ext 1#2 +m 2 (d + m) 2n-2 1≤i<j≤k |f (a i a j )| ext 1#2 , |f n+1 (a 2 . . . a k )| 1#2 = d(d + m) n-1 k i=1 |f (a i )| 1#2 + [d(d+m) n-1 -1]d(d+m) n-1 2 k j=1 |f (a j a j )| ext 1#2 +d 2 (d + m) 2n-2 1≤i<j≤k |f (a i a j )| ext 1#2 .
Now the same reasoning can be applied for

|f n+1 (a 1 )| 2#1 and |f n+1 (a 2 . . . a k )| 2#1 ,
because of the following obvious property.

Property 3 Let f be a morphism on A. For every non-negative integer n, and for every integers i, j,

1 ≤ i, j ≤ k, |f n (a i a j )| ext 1#2 = |f n (a j a i )| ext 2#1 .
Thus, using equation ( 2), we have the following.

Proposition 4. For every positive integer n,

|f n+1 (a 1 )| 2#1 = m(d + m) n-1 k i=1 |f (a i )| 2#1 + [m(d+m) n-1 -1]m(d+m) n-1 2 k j=1 |f (a j a j )| ext 2#1 +m 2 (d + m) 2n-2 1≤i<j≤k |f (a i a j )| ext 2#1 , |f n+1 (a 2 . . . a k )| 2#1 = d(d + m) n-1 k i=1 |f (a i )| 2#1 + [d(d+m) n-1 -1]d(d+m) n-1 2 k j=1 |f (a j a j )| ext 2#1 +d 2 (d + m) 2n-2 1≤i<j≤k |f (a i a j )| ext 2#1 .
The previous reasoning can of course be applied if conditions 1. and 2. are verified for any partition of the alphabet (in Propositions 3 and 4 the partition is in two sets A = {a 1 } ∪ {a 2 . . . a k }). Then we obtain the following general result.

Theorem 1. Let k be an integer (k ≥ 2), and A the k-letter ordered alphabet A = {a 1 < a 2 < . . . < a k }. Let f be a morphism on A fulfilling the following conditions:

there exist a positive integer p and a set of p positive integers {m 1 , . . . , m p } such that A can be partitioned into p subsets A 1 , . . . , A p with

a∈A ℓ |f (a)| ai = m ℓ , 1 ≤ i ≤ k, -for every i, j, 1 ≤ i, j ≤ k, |f (a i a j )| ext 1#2 = |f (a j a i )| ext 1#2 . Let M = m 1 + . . . + m p and let u = 1#2 or u = 2#1. For every integer n ≥ 1 and for each A ℓ , 1 ≤ ℓ ≤ p, a∈A ℓ |f n+1 (a)| u = m ℓ M n-1 k i=1 |f (a i )| u + (m ℓ M n-1 -1)m ℓ M n-1 2 k j=1 |f (a j a j )| ext u +m 2 ℓ M 2n-2 1≤i<j≤k |f (a i a j )| ext u .

Examples

In this section we give a series of examples of application of Theorem 1.

The Thue-Morse morphism

The Thue-Morse morphism (see Section 3.2) is the simplest example of a morphism fulfilling conditions 1. to 3. above. Indeed m = d = 1, and

|µ(a 1 a 2 )| ext 1#2 = |a 1 a 2 a 2 a 1 | ext 1#2 = 1 = |a 2 a 1 a 1 a 2 | ext 1#2 = |µ(a 2 a 1 )| ext 1#2 , |µ(a 1 a 1 )| ext 1#2 = |µ(a 2 a 2 )| ext 1#2 = 1. Since |µ(a 1 )| 1#2 = |µ(a 2 )| 2#1 = 1, and |µ(a 1 )| 2#1 = |µ(a 2 )| 1#2 =
0, we obtain from Propositions 3 and 4 that

|µ n+1 (a 1 )| 1#2 = |µ n+1 (a 1 )| 2#1 = |µ n+1 (a 2 )| 1#2 = |µ n+1 (a 2 )| 2#1 = 2 2n-1 .

The Prouhet morphisms

Let k ≥ 2, and let A be the k-letter ordered alphabet

A = {a 1 < • • • < a k }. The Prouhet morphism π k ([9]) is defined on A by π k (a i ) = a i a i+1 . . . a k a 1 . . . a i-1 , 1 ≤ i ≤ k.
As above we obtain a corollary of Theorem 1. Corollary 4. For every i, 1 ≤ i ≤ k, and for every positive integer n,

|π n+1 k (a i )| 1#2 = (k -1)k n 12 3k n+1 + k -2 , |π n+1 k (a i )| 2#1 = (k -1)k n 12 3k n+1 -k + 2 .

The Arshon morphisms

Let k be any even positive integer. The morphism

β k ([1]) is defined, for every r, 1 ≤ r ≤ k/2, by a 2r-1 → a 2r-1 a 2r . . . a k-1 a k a 1 a 2 . . . a 2r-3 a 2r-2 , a 2r → a 2r-1 a 2r-2 . . . a 2 a 1 a k a k-1 . . . a 2r+1 a 2r .
Corollary 5. Let k be any even positive integer. For every i, 1 ≤ i ≤ k, and for every positive integer n,

|β n+1 k (a i )| 1#2 = k n-1 4 k n+2 • (k -1) + 2k , |β n+1 k (a i )| 2#1 = k n-1 4 k n+2 • (k -1) -2k .
Example. For every i, 1 ≤ i ≤ k, and for every n ≥ 1,

|β n+1 6 (a i )| 1#2 = 6 n-1 • (45 • 6 n + 3), |β n+1 6 (a i )| 2#1 = 6 n-1 • (45 • 6 n -3).

Three other examples

1. Let A be the four-letter ordered alphabet

A = {a 1 < a 2 < a 3 < a 4 }. Define the morphism f on A by f (a 1 ) = a 1 a 3 a 2 a 4 , f (a 2 ) = ε, f (a 3 ) = a 1 a 4 , f (a 4 ) = a 2 a 3 .
The morphism f fulfills the conditions of Theorem 1. Here we choose p = 3,

A = A 1 ∪ A 2 ∪ A 3 with A 1 = {a 1 }, A 2 = {a 2 }, A 3 = {a 3 , a 4 }, and m 1 = m 3 = 1, m 2 = 0, thus M = 2.
Corollary 6. For every positive integer n,

|f n+1 (a 1 )| 1#2 = |f n+1 (a 3 a 4 )| 1#2 = 3 • 2 n-1 • (2 n+1 + 1), |f n+1 (a 1 )| 2#1 = |f n+1 (a 3 a 4 )| 2#1 = 3 • 2 n-1 • (2 n+1 -1), |f n+1 (a 2 )| 1#2 = |f n+1 (a 2 )| 2#1 = 0.
2. Let A be the five-letter ordered alphabet A = {a 1 < a 2 < a 3 < a 4 < a 5 }. Define the morphism g on A by g(a 1 ) = a 1 a 3 a 5 a 4 a 2 , g(a 2 ) = a 4 a 2 a 3 , g(a 3 ) = a 5 a 1 , g(a 4 ) = a 1 a 5 , g(a 5 ) = a 2 a 3 a 4 .

The morphism g fulfills the conditions of Theorem 1. Here we choose p = 3,

A = A 1 ∪ A 2 ∪ A 3 with A 1 = {a 1 }, A 2 = {a 2 , a 4 }, A 3 = {a 3 , a 5 }, and m 1 = m 2 = m 3 = 1, thus M = 3.
Corollary 7. For every positive integer n, Corollary 8. For every x ∈ A and for every positive integer n,

|g n+1 (a 1 )| 1#2 = |g n+1 (a 2 a 4 )| 1#2 = |g n+1 (a 3 a 5 )| 1#2 = 3 n-1 • (5 • 3 n+1 + 2), |g n+1 (a 1 )| 2#1 = |g n+1 (a 2 a 4 )| 2#1 = |g n+1 (a 3 a 5 )| 2#1 = 3 n-1 • (5 • 3 n+1 -2).
|h n+1 (x)| 1#2 = 6 • 18 n-1 • (9 • 18 n+1 + 40), |h n+1 (x)| 2#1 = 6 • 18 n-1 • (9 • 18 n+1 -40).
6 Ordered patterns with no gaps and morphisms 6.1 Rises, descents, and squares of f n Let k be an integer (k ≥ 2) and A the k-letter ordered alphabet

A = {a 1 < a 2 < • • • < a k }. Let f be any morphism on A: for 1 ≤ i ≤ k, f (a i ) = a i1 . . . a ip i with p i ≥ 0 (p i = 0 if and only if f (a i ) = ε).
The vector of rises (resp. vector of descents, resp. vector of squares of one letter) of f n is the k vector whose i-th entry is the number of occurrences of the ordered pattern 12 (resp. 21, resp. 11) in the word f n (a i ), i.e.,

R(f

n ) = (|f n (a i )| 12 ) 1≤i≤k , D(f n ) = (|f n (a i )| 21 ) 1≤i≤k , R 2 (f n ) = (|f n (a i )| 11 ) 1≤i≤k .
We define two sequences of k vectors, (F (f n )) n∈IN and (L(f n )) n∈IN , where

F (f n )[i] is the first letter of f n (a i ) and L(f n )[i] is the last letter of f n (a i ) if f n (a i ) = ε, and F (f n )[i] = L(f n )[i] = 0 if f n (a i ) = ε.
Of course these two sequences take their values in a finite set: they are ultimately periodic. Thus they can be computed a priori from f.

Given a non-negative integer n, let ℵ ′ be the subset of ℵ such that, for each i ∈ ℵ, f n (a i ) = ε if and only if i ∈ ℵ ′ . We associate to the two vectors

F (f n ) and L(f n ) an application C 12 n : ℵ ′ × ℵ ′ → {0, 1} defined by C 12 n (i, j) = 1, if L(f n )[i] < F (f n )[j] 0, if L(f n )[i] ≥ F (f n )[j].
Similarly we define

C 21 n (i, j) = 1, if L(f n )[i] > F (f n )[j] 0, if L(f n )[i] ≤ F (f n )[j], C 11 n (i, j) = 1, if L(f n )[i] = F (f n )[j] 0, if L(f n )[i] = F (f n )[j].
For any morphism f on A, there exists a least integer M f (M f ≤ k and M f depends only on f ) such that, for every positive integer n and every a ∈ A, f n (a) = ε if and only if f M f (a) = ε. By convention, if f is a nonerasing morphism then M f = 0. The integer M f is known in the literature about L-systems as the mortality exponent of f ( [START_REF] Levé | On a conjecture about finite fixed points of morphisms[END_REF]). Now let ℓ be an integer, 1 ≤ ℓ ≤ k. One has f (a ℓ ) = a ℓ1 . . . a ℓp ℓ and we denote by ℓ 2) the number of external occurrences of the ordered pattern 12 in f n (a ℓ ′ i a ℓ ′ j ) for each subsequence a ℓ ′ i a ℓ ′ j of f (a ℓ ), 1 ≤ i < j ≤ p ′ ℓ . But the only possibility for 12 to be an external occurrence in f n (a ℓ ′ i a ℓ ′ j ) is that j = i + 1 and the last letter of f n (a ℓ ′ i ) is smaller than the first letter of f n (a ℓ ′ j ). Thus, the number of occurrences of such patterns is only the number of times L(f n )[i] < F (f n )[i+1] with i+1 ≤ p ′ ℓ , i.e., the number of times C 12 n (ℓ ′ i , ℓ ′ i+1 ) = 1 for 1 ≤ i ≤ p ′ ℓ -1. We proceed similarly with the patterns 21 and 11. Consequently we have the following proposition. ) and f n (a

′ 1 . . . ℓ ′ p ′ ℓ the subsequence of ℓ 1 . . . ℓ p ℓ such that f n+1 (a ℓ ) = f n (a ℓ ′ 1 . . . a ℓ ′ p ′ ℓ ) for every n ≥ M f .
ℓ ′ i ) = ε, 1 ≤ i ≤ p ′ ℓ . Then |f n+1 (a ℓ )| 12 = k t=1 |f n (a t )| 12 • m 1,t,ℓ + p ′ ℓ -1 i=1 C 12 n (ℓ ′ i , ℓ ′ i+1 ), (4)
|f n+1 (a ℓ )| 21 = k t=1 |f n (a t )| 21 • m 1,t,ℓ + p ′ ℓ -1 i=1 C 21 n (ℓ ′ i , ℓ ′ i+1 ), (5)
|f n+1 (a ℓ )| 11 = k t=1 |f n (a t )| 11 • m 1,t,ℓ + p ′ ℓ -1 i=1 C 11 n (ℓ ′ i , ℓ ′ i+1 ). (6)

  and if x, y ∈ ℵ, x < y ⇒ f (x) < f (y). Thus the word v contains an occurrence of the ordered pattern u if v contains a subsequence v ′ which is equal to f (u ′ ) where u ′ is obtained from u by deleting all the occurrences of #, with the additional condition that two adjacent (not separated by #) letters in u must be adjacent in v. The number of different occurrences of u as an ordered pattern in v is denoted by |v| u . Example. Let A = {a, b, c, d, e, f } with a < b < c < d < e < f. The word v = eaf dbc contains one occurrence of the ordered pattern 2#31, namely the subsequence ef d (|e af d b c| 2#31 = 1). In v, the ordered pattern 2#3#1 occurs in three occurrences: ef d, ef b, and ef c (|e af d b c| 2#3#1 = 3); the ordered pattern 231 does not occur in v (|e af d b c| 231 = 0).

Corollary 3 .

 3 For any integer n ≥ 0, R p G(ϕ n+2 ) = Fn+2 p

3 .

 3 Let A be the three-letter ordered alphabet A = {a < b < c}. Define the morphism h on A by h(a) = aba cab cac bab cba cbc, h(b) = aba cab cac bca bcb abc, h(c) = aba cab cba cbc acb abc. This morphism was proved square-free by Brandenburg in [3]. It fulfills the conditions of Theorem 1 with p = 3, A = A 1 ∪ A 2 ∪ A 3 with A 1 = {a}, A 2 = {b}, A 3 = {c}, and m 1 = m 2 = m 3 = 6, thus M = 18.

Proposition 5 .

 5 For each letter a ℓ ∈ A, f (a ℓ ) = a ℓ1 . . . a ℓp ℓ , and for all n ≥ M f , let ℓ ′ 1 . . . ℓ ′ p ′ ℓ be the subsequence of ℓ 1 . . . ℓ p ℓ such that f n+1 (a ℓ ) = f n (a ℓ ′ 1 . . . a ℓ ′ p ′ ℓ

  This means that, for every n ≥ M f , a letter a ℓi appears in a ℓ1 . . .a ℓp ℓ but not in a ℓ ′ 1 . . . a ℓ ′ p ′ ℓ if and only if f n (a ℓi ) = ε. Of course p ′ ℓ ≤ p ℓ , and if M f = 0 then p ′ ℓ = p ℓ for each 1 ≤ ℓ ≤ k.Here also, as in Section 3, the number of occurrences of the ordered pattern12 in f n+1 (a ℓ ) = f n (a ℓ1 . . . a ℓp ℓ ) = f n (a ℓ ′ 1 . . . a ℓ ′ p ′ ℓ ) (n ≥ M f ) isobtained by adding two values: (1) the number of occurrences of the ordered pattern 12 in each f n (a ℓi ), 1 ≤ i ≤ p ℓ . As in the previous case, this number is equal to k t=1 |f n (a t )| 12 •m 1,t,ℓ , and (

Some examples

No external rises, no external descents, no external squares Let us suppose that the morphism f is such that, for all i and j, L(f )[i] ≥ F (f ) [j] (there are no external rises). According to equation [START_REF] Burstein | Enumeration of words with forbidden patterns[END_REF], in this case, for each letter a ℓ ∈ A, f (a ℓ ) = a ℓ1 . . . a ℓp ℓ , and for all n ≥ M f ,

Moreover, if the above inequality is strict then, according to equation [START_REF] Kitaev | The Peano curve and counting occurrences of some patterns[END_REF],

Now if we suppose that, conversely to the previous case, the morphism f is such that, for all i and j, L(f )[i] ≤ F (f )[j] (there are no external descents) then we obtain the same result by switching 12 and 21 in the above formulas.

To end, if we suppose that the morphism f is such that, for all i and j, L(f

then, according to equation ( 6), for each letter a ℓ ∈ A, f (a ℓ ) = a ℓ1 . . . a ℓp ℓ , and for all n ≥ M f ,

The Thue-Morse morphism Since R(µ) = 1 0 , D(µ) = 0 1 and R 2 (µ) = 0 0 we obtain again a well known result.

Corollary 9. For any integer n ≥ 0,

.

The Fibonacci morphism Since R(ϕ) = 1 0 and D(ϕ) = R 2 (ϕ) = 0 0 we have again a well known result.

Corollary 10. For any integer n ≥ 1,

Erasing morphisms Let A be the four-letter ordered alphabet A = {a 1 < a 2 < a 3 < a 4 }.

1. Here we consider the erasing morphism f , given in Section 5.4, defined on A by f (a

Starting from R(f ) = 2 0 1 1 , we obtain the following corollary of Proposition 5.

Corollary 11. For any integer n ≥ 1, R 2 (f n ) = 0 0 0 0 and if n is even

.

2. Now we consider the erasing morphism g defined on A by g(a 1 ) = a 1 a 2 a 4 a 3 , g(a 2 ) = a 3 , g(a 3 ) = ε, g(a 4 ) = a 1 a 2 a 4 . Here we have M f = 2.

Corollary 12. R(g) = 2 0 0 2 , D(g) = 1 0 0 0 , R 2 (g) = 0 0 0 0 , and, for any integer n ≥ 2,


Dainis Zeps
email: dainize@mii.lu.lv

Application of the Free Minor Closed Classes in the Context of the Four Color Theorem

free-planar graphs, is discussed.

Introduction

We have two main ideas and one observation in the ground of this treatment. Free planar graph idea arouse considering dynamic graph partitioning into 3-connected components [START_REF] Zeps | On the Dynamic Partitioning of the Graph in Threeconnected Components[END_REF][START_REF] Zeps | The triconnectivity considered dynamically[END_REF]. Secondly, free planar graphs were generalized in free minor closed classes in [START_REF] Kratochvíl | About minor closed classes and the generalization of the notion of free-planar graphs[END_REF] by Jan Kratochvíl. Treating in year 1984 graph's dynamic partition into 3-connected components we observed that this partitioning algorithm can't be simplified if we had intent to build only free-planar graphs. Thus, speaking in terms of this observation, planar graphs are not more complicate than free-planar graphs, at least what concerns their reconstructibility from 3-connected components [START_REF] Zeps | On the Dynamic Partitioning of the Graph in Threeconnected Components[END_REF]. Thus, algorithmically or what concerns algorithmic re-constructibility of the graphs, planar graphs are not more complicate than free-planar graph in spite of fact that free-planar graphs are only small subset of planar graphs. Further, from four-color theorem we know that planar graph uses the same number of colors to be colored as free-planar graph. In this article we investigate how this simple fact could be put in the ground of some other approach in trying to prove four-color theorem.

Further in this article we directly mention either four-color theorem is assumed already proved or not. When it is not alleged directly then it should follow from the context.

We start with the proof what we believe should be put to ground for four-color theorem in general.

Theorem 1. Every free planar graph is colorable using four colors.

Proof. Direct check shows that 3-connected free planar graphs are 4-colorable graphs [START_REF] Zeps | Free Minor Closed Classes and the Kuratowski Theorem[END_REF]. There are only three cases to be considered. Wheel graph is 4-chromatic if odd, and 3chromatic when even. Envelope graph is 3-chromatic. Further, uniting 3-components of free planar graphs, which are at most 4-colorable graphs, via virtual edges, we get again at most 4-colorable graphs. Truly, virtual edge itself may acquire no more than two colors, what is the maximal number of colors that may be forced upon an another component.

Here we must recall that 3-components which are unique comprise 3-component tree, i.e., structure without cycles [START_REF] Zeps | On the Dynamic Partitioning of the Graph in Threeconnected Components[END_REF][START_REF] Zeps | The triconnectivity considered dynamically[END_REF].

Free-k-chromatic graphs

Graph is free-k-chromatic if it is k-chromatic and for every non-edge e G+e is k-chromatic too. More general, graph is n-free-k-chromatic if it is k-chromatic and for every non-edge set of n edges G with these edges added remains k-chromatic. Shortly we denote this property by 'nfk', saying, for example, that graph G is 2f4-graph, meaning that it is 2-free-4-chromatic graph.

Let us try to clarify how freeness of colorability could be connected with freeness of minor closed classes. One simple result we get directly.

Theorem 2. Every k-critical graph is free-k-chromatic

Proof. Every edge may receive the lonely color and thus every non-edge may be added non disturbing coloring.

Further, we may conclude that class of free-k-chromatic class is wider that k-critical class. For example, graph K k+1 with proper splitting of vertex is free-k-colorable graph, but not k-critical graph. What concerns 4-colorability, one more large class belongs to free-4-chromatic graphs, and this is class of free-planar 4-chromatic graphs. This follows from the four color theorem. Actually, if we add edge to such graph, it should remain planar and, thus, 4-chromatic according four color theorem.

But we want to prove this fact not using four color theorem. Actually, k-chromatic free planar graphs with k < 4 can't rouse any problems what concerns four-color theorem. Truly, we may apply for new edge always fourth color. We go directly to case k = 4.

But, before we need to prove simple theorem.

Theorem 3. Every atetrahedral graph is 3-colorable, and, if 3-chromatic, graph is free-4-chromatic graph.

Proof. Atetrahedral graph itself is 3-colorable by induction: start coloring with odd cycle as 3-component, using 3 colors; then after, as step of induction, add some connected component to already colored part. If all cycles are even than graph should be 2-chromatic. It is trivial that 3-chromatic atetrahedral graph is free-4-colorable.

Theorem 4. Every free planar 4-chromatic graph is free-4-chromatic graph.

Proof. If graph is 3-connected than we must check only case of odd wheel graph: adding edge it should remain 4-chromatic, because odd wheel graph is 4-critical graph, see previous theorem. Further, we must show that arbitrary free-planar graph consisting from more than one 3-component, where at least one component is odd wheel, remains 4-chromatic after edge is added.

Let graph be 4-chromatic free-planar graph consisting from more than one 3-component. Let us add edge x -y to check whether graph remains 4-chromatic.

If both ends of edge, i.e., vertices x and y, fall in the same 3-component, then we have all proved. Edge x -y is going to contract path of 3-components, see [START_REF] Zeps | On the Dynamic Partitioning of the Graph in Threeconnected Components[END_REF][START_REF] Zeps | The triconnectivity considered dynamically[END_REF] (or path of g-edges [START_REF] Zeps | Trying to Prove the Kuratowski Theorem from Below[END_REF]). We may refer problem of coloring the contractible part of graph to problem of coloring atetrahedral graph plus edge. But atetrahedral graph is 3-colorable, as we have this proved already in the theorem before, and proof of theorem is completed.

We have proved that four color theorem is true what concerns free planar graphs and even augmented with additional edge, i.e., that free planar 4-chromatic graph is free-4colorable too. But this evidently is not sufficient to conclude about the four color theorem in general. Let us go further. Theorem may be extended. It is easy to see that in place of free planar graph class may be taken some wider class, let it be called class PP, i.e., the class generalizing freeplanar graph class, without forbidden virtual edges in building graphs, contracting path of 3-components according procedure in [START_REF] Zeps | On the Dynamic Partitioning of the Graph in Threeconnected Components[END_REF]. Graphs from PP have the same components as free-planar with exception that forbidden virtual edges (for free-planarity) are now allowed. Class P P is expected to comprise free-planar (or even free-2-planar) graphs for projective planar , though at least one graph violates this expectation, D 17 , forbidden graph for projective plane [START_REF] Henry | 103 Graphs That Are Irreducible for the Projective Plane[END_REF].

Let us define class P P precisely. Similarly as in [START_REF] Zeps | Free Minor Closed Classes and the Kuratowski Theorem[END_REF], page 6, graph G from P P consists from components, where every edge may be virtual edge, as follows:

1) C k , k > 2; 2) W k , k > 2; 3) C 6 .
It is easy to see that class P P does not have free-Hadwiger class F ree(H 5 ) [where H 5 supposed without minor K 5 ] as subclass, because forbidden graph K 5 belongs to P P , but not forbidden K 3,3 doesn't belong to P P . Thus, two classes intersect. Next two theorems speak more precisely.

Theorem 5. Class P P is minor closed class.

Proof. Checking each component separately, we may see that eliminating edge or contracting edge we get some legal component. So, from W k we get either some other wheel or polygons. From envelope graph C 6 we get K 4 and polygons. Theorem 6. Class P P is equal to class N • (K - 5 , K 3,3 ). Proof. If we added constraint as forbidden graph K - 3,3 , we had P P equal to free-planar graph class. Taking off constraints from virtual edges just means allowing minor K 3,3 .

Further, K - 5 can't be obtained with allowed components. Neither K 3,3 can. In first case, largest component in K - 5 minus edge is either W 4 or K 4 , which already are closures for allowed set of components, i.e., can't be obtained from allowed 3-components with connections via virtual edges. In second case, only K - 3,3 without closure with edge may be obtained.

Theorem 7. Every graph from class P P is free-4-chromatic

4-critical graphs free-planar graphs Odd wheels

6

Class CC

Class P P K -++ 3,3 k K -++ 3,3
plus 0-critical edge Fig. 2. Classes comprising all free-4-chromatic graphs. One graph, proper K 5 , or K -++ 3,3 has K - 3,3 as subgraph, and belongs to class P P , but not belongs to F ree(H 5 ). Graph K -++ 3,3 plus 0-critical edge remains to be 4critical, but does not belong to any class in the picture, except F ree 4

CH itself. Graph proper K 5 = K -++ 3,3
especially should be taken into account because it is the only graph that is free-4-chromatic with 0-critical edge and would remain free-4-colorable after this 0-critical edge be added. Class F ree(H5) that would be between classes F ree(P lanar) and CC and intersect with class P P is not shown in the picture.

Proof. In proof of theorem 4 we may observe that it does not depend upon fact either virtual edges have constraints as in case of free-planar graphs or not. Thus previous proof fits for this theorem too.

It is easy to see that the proof of the last theorem would not change if in place of odd wheels we had arbitrary 4-critical graph. Let us use this fact and with purpose to widen the observable class of free-4-chromatic graphs define class CC which is modified class P P with 4-critical graphs allowed in place of odd wheels. Then we formulate as corollary what follows, because previous proof fits as before.

Corollary 8. Every graph from class CC is free-4-chromatic.

Let us denote by F ree k CH class of all free-k-chromatic graphs. We may conclude the following corollary.

Corollary 9. F ree(P lanar) ⊂ F ree(H

5 ) ⊂ K 3,3 : K 5 ⊃ P P ⊂ CC ⊂ F ree 4 CH, where ⊂ G 1 : G 2 ⊃

denotes symmetric property saying that classes intersect with at least G 1 not belonging to right part, and G 2 not belonging to left part.

Here we have one exceptional graph, proper K 5 plus non-planar edge, which does not fit in any of classes above, but it is free-4-chromatic. This same graph may be reconstructed as K -++ 3,3 , i.e., K 3,3 minus edge plus two edges not affecting planarity, and then removed edge restoring.

We define 0-critical edge to be such non-edge in graph that for all colorings it may be added to graph no affecting these colorings. 1-critical edge then let be such non-edge that for no coloring it may be added without affecting total coloring of the graph. Addition of 1-critical edge to graph raises graphs chromatic number always, whereas 0-critical edge's addition never changes graph's chromatic number. Lemma 10. Graph K k+1 with split being proper, i.e., not simply edge being split off, is free-k-chromatic. More over, it remains free-k-chromatic after edge vw is added, where v and w are new vertices after split done.

Proof. Let new vertices in the split would be v and w. It is easy to see that vw is 0-critical edge, because vertex before split had k+1-st color, but after split v andw should receive their colors from mutual neighbors, i.e., different colors. Every edge may be added to this graph; if, say, color of v is the same that some, say, vertex s, then s may change its color with other vertex from neighbors of w. vw may be added as well. This act of adding does not make graph not being free-k-chromatic, as it follows from previous arguments. Conjecture 11. Graph K 5 (with proper split) is the only free-4-chromatic graph with 0-critical edge.

Proof. Let us have some considerations in favor of this conjecture. Let us consider at least these classes which we build here. We have to prove that other free-4-chromatic graphs do not have 0-critical edges. If added edge falls into single component, say, some k-critical graph, k < 5, then it is not 0-critical. If edge falls in different components then vertices via virtual edges can't be forced to have or not to have different color.

In other cases, only uniquely colorable graphs or subgraphs may force 0-critical edges, but we have opposite, free-colorable graph.

Graph K 5 is not the only graph that would belong to class F ree 2 4 CH, there at least one more such graph may be given, i.e. D 17 from forbidden subgraphs of projective plane [START_REF] Henry | 103 Graphs That Are Irreducible for the Projective Plane[END_REF][START_REF] Zeps | On Free Minor Closed Classes of Graphs Outside Planarity[END_REF]. Further we would see that all critical graphs behave the same way.

Let us 'configure' our graph proper K 5 , or K -++ 3,3 , in the sequence of subsets in corollary 9.

Corollary 12. K -++ 3,3 ∈ F ree(H 5 ), K -++ 3,3 ∈ P P , K -++ 3,3
plus 0-critical edge is not in P P , and

K -++ 3,3 plus 0-critical edge is in F ree 4 CH.
Class CC hardly could be expected to be characterizable with forbidden components. But some more special case is possible. Graphs G 2k+1 , with k > 1, from [START_REF] Zeps | 4-critical Wheel Graphs of Higher Order[END_REF] that there are called higher order wheels, are 4-critical, does not have minor K 5 and thus this class is subclass of class N • (K 5 , K 3,3 ). If we would like to constrain our class CC to these 4-critical graphs then all class became subclass of this class.

By the way, these higher order wheels G 2k+1 have O -, where O is octahedron graph, as minor. But, O itself is forbidden graph for all class of G 2k+1 , k > 1. Let us formulate it as nice corollary.

Corollary 13. For the family of higher wheels octahedron minus edge is proper grandson and octahedron itself is proper grandfather.

In [START_REF] Zeps | 4-critical Wheel Graphs of Higher Order[END_REF] defined minor brackets allow to characterize this situation. For higher wheels pair (O -, O) is proper minor bracket.

Let us add to class's CC, calling it completed CC, graph with as allowed components linear graphs l k , i.e., paths of length k -1 > 0, where each vertex may serve as virtual vertex.

Let us define class of graph 4M as follows: graph G belongs to 4M if its spanning subgraph belongs to completed CC.

Theorem 14. If four color theorem is correct class 4M contains all planar graphs.

Proof. Let graph be 4-colorable. Let us reduce edges until it is free-4-colorable. Graph belongs to 4M .

Of course, we must be content with the fact that class CC can't be minor closed. Either whole class of free-4-colorable graphs can't be expected to be minor closed.

Theorem 15. If four color theorem is true, in 4-chromatic planar graph edge to be added is either non-1-critical and planar or 1-critical and non-planar.

Closures of components

In [START_REF] Zeps | Trying to Prove the Kuratowski Theorem from Below[END_REF] we introduced notion of component path closure and proved Kuratowski theorem analogue for 3-components. Let us remind some definitions from there.

Components we discuss are the same as in theory of graphs dividing into 3-connected components, i.e., polygons, bonds [if necessary], three connected graphs, with as many virtual edges as necessary. In considering free-planar graphs, our allowed components should be these allowed in building free-planar graphs, and so on. We add as very useful notion generalized vertex and edge,or g-vertex and g-edge. g-vertex is either single vertex or two distinct vertices in the graph. If not told otherwise, we would assume that with g-vertex virtual edge is connected, i.e., if {v, w} is g-vertex then {v, w} is virtual edge in G too. In case g-vertex is single vertex, it is virtual vertex too. g-edge is always pair of g-vertices, i.e., if not told otherwise, pair of virtual edges, or edge or vertex, or virtual vertices. Thus, g-edge may consist from four vertices, or three vertices, i.e. vertex and edge, or two edges with common vertex, or two vertices, i.e., vertex and vertex.

We are saying that component C is marked with g-vertex v = a or v = a, b, saying v : C is formed, when some g-vertex v is distinguished in C, and v is virtual vertex in C. Distinguishing two distinct g-vertices in C, we may speak about g-edge being distinguished in C, denoting it vw : C or e : C, where vw and e is g-edge.

Let us call closure union two components by common g-vertex, that is simple vertex. For example, we may write C 1 : e : C 1 , assuming that two marked components e : C 1 and e : C 2 have common g-vertex e, and say that components are forming closure by uniting two g-vertices in common g-vertex e. If order of e is one, i.e., it is simple vertex, then we call closure 1-closure, first order closure. If order of e is two, i.e., it pair of vertices, then we call closure 2-closure, or second order closure. Further, we may form paths of closures C 1 : e 1 : C 2 : e 2 : ...e k-1 C k with k > 1. Yet more, we may cycle in this path, speaking about new type of closure, i.e., if we cycle in path of first order closures, then we say that we did 2-closure from 1-closures, and, if we cycle in path of second order closures, i.e., at least one closure in the path was second order, then we say, that we did 3-closure from 2-closures.

Building 4-critical graphs

First order 4-chromatic higher order wheels In [START_REF] Zeps | 4-critical Wheel Graphs of Higher Order[END_REF] higher order wheels were introduced, that were 4-critical graphs. We may now illustrate on these wheels in what way 3-closures from component 2-closures path may be very useful. Let for a while us consider only wheels as components. Then graph performed from simple wheels as closure of path of closures may be characterized as sequence n 1 , ...n l , l >= 3, where n i , 1 <= i <= l, is order of i-th wheel.

Theorem 16. Graph obtained as closure of path of wheels as components is 4-critical iff l is odd and every n i in the characteristic sequence of the closure is odd and at least three.

Proof. Let l = 3, and wheel be minimal. Common vertex in virtual g-edges in cycle of closures should receive colors (A ∨ B) ∧ (B ∨ C) ∧ (C ∨ A) which gives F alce, thus new color should be generated. Every edge in construction is crucial.

Let wheel be arbitrary. The same coloring as for simple case is now possible too. Every edge is crucial in the construction by the argument that follows. For absent rim edge, rim vertices may be colored with, say, colors A and B. For absent outer and inner spike non-spike's both ends colors with the same color.

Thus, chromatic criticality rises from the condition that every edge is necessary in the construction.

Case for arbitrary odd l generalizes obviously: condition for center of wheel could be made

(A ∨ B) ∧ (B ∨ A) ∧ (A ∨ B)...(B ∨ C) ∧ (C ∨ A).
It is easy to see that, if in sequence n 1 , ...n l , l >= 3, at least one number not excluding l is not odd, then graph constructed may be colored with three colors.

In the article [START_REF] Zeps | 4-critical Wheel Graphs of Higher Order[END_REF] graphs considered were 3 -3 -3 (G 3 ), see figure 3, 3 -3 -5 (G 5 ),3 -5 -5 (G 7 ), and 5 -5 -5 (G 9 ), see figure 4.

Class of non-three-connected 4-critical graphs In [START_REF] Zeps | Trying to Prove the Kuratowski Theorem from Below[END_REF] graph in fig. 6 was wheel graph W 5 with split one edge what may be considered as smallest non-free-planar 4critical graph. Either it is example of smallest application of Hajós sum [START_REF] Bollobás | Modern Graph Theory[END_REF]. See fig. 9. This construction may generalized to give augmentable class of similar graph that would be non-tree-connected, but nevertheless 4-critical.

In place of two components K 4 , there may be even number of K 4 . It is easy to see that such graph should be 4-critical. It has general cycle of odd length. Next, on this cycle one vertex should receive 'third color', and, as a consequence, in that component fourth color should appear.

£ ¢ ¡ 2 £ ¢ ¡ 4 £ ¢ ¡ 1 £ ¢ ¡ 4 £ ¢ ¡ 1 £ ¢ ¡ 2 £ ¢ ¡ 4 £ ¢ ¡ 1 £ ¢ ¡ 3 £ ¢ ¡ 4 £ ¢ ¡ 2 £ ¢ ¡ 4 £ ¢ ¡ 2 Fig. 4. Graph 5 -5 -5 (G9 in [18]) £ ¢ ¡ 1 £ ¢ ¡ 2 £ ¢ ¡ 1 £ ¢ ¡ 3 £ ¢ ¡ 2 £ ¢ ¡ 4 £ ¢ ¡ 3
Graphs of this class are characterized by number of components K 4 , divided by two, calling it graph's order. Thus, in fig. 9 there are graphs of first and third order of the type.

Closures of paths of closures

Further, components in paths in closures may be arbitrary, i.e., not only wheels.

Theorem 17. Let A be arbitrary class of graphs which is generated from some set of allowed possibly marked components without yet applied closure of paths of closures, and graphs of this class are free-4-chromatic. Let us build new graph where one closure of path of closures is applied. Then the graph is free-4-chromatic too.

Proof. Proof is omitted here.

It may be expected that previous theorem may be generalized to case when paths are built in a way when cycles only intersect but do not touch in sort of edges. Formally, it should be done carefully. It is clear that overall generalization with whatever possible closures should give graphs that are not free-4-chromatic. It is obvious. Because, using this technics we may construct arbitrary graphs, but not every graph is free-4-chromatic.

Planar graph's reduction to free-planar graph

Pictures 9 and 11, using one Grinberg's graph [START_REF] Grinberg | On Planar Regular Graphs Degree Three without Hamiltonian Cycles[END_REF], demonstrate way, how graph may be split in a way it becomes free-planar. In first case splits are done via edges, i.e., in that case, according Tutte's theory of division into three-connected components [START_REF] Tutte | Graph Theory, Encyclopedia of mathematics and its applica-tions[END_REF][START_REF] Zeps | The triconnectivity considered dynamically[END_REF], virtual bonds with one real edge and virtual edges should appear. In another case splits are done, no affecting real edges in the graph. Both types of splits may be combined together, but we would prefer second type of splits and use only them in order to simplify theoretical outline.

Another simple proof of four-color theorem. What's wrong with it?

Let us have planar graph G with m edges and one edge take out, and let us, under induction assumption, it's vertices color in four colors, and let us split it, using second way, until it becomes free-planar, remembering vertex colorings. Now we have graph that is free-planar and free-4-chromatic. We may add eliminated edge, and graph is with m, and proof almost done.

What's wrong with this proof? Free-4-chromatic graph after adding edge should be, in general, recolored. The operation of recoloring may affect end g-vertices that should be conditioned by some border condition, according which split vertices or edges should preserve coloring, that is in concordance with coloring in graph without splits. If recoloring is possible with the preserving of this border condition, then proof would be done too. Let us say that graph may be colored in 4 colors if this border condition problem may be solved, and call it border condition problem. Let us formulate this as theorem.

Theorem 18. Border condition problem may be solved iff four color theorem is correct.

Formulating this theorem we want to express significant principal fact. What concerns number of colors, needed in coloring, coloring planar graph is as complex as coloring free planar graph. I.e., four colors are needed in both cases.

Discussion of border condition problem

How to attack border condition problem? We may show up two encouraging facts. First, in [START_REF] Grinberg | On Planar Regular Graphs Degree Three without Hamiltonian Cycles[END_REF] Grinberg mentions significant fact that only possible counterexamples of 4CT may be quasi-five connected graphs. Thus, in the border condition problem this fact should play some role. Second, if in traditional proof outline of 4CT we must consider 5-critical graph, then in our case we should consider 5-critical free-planar graph with border condition. But graph is free-planar nevertheless, where only wheels play any significant role, thus, our 5-critical graph consist from wheels connected by polygons or envelopes and with border condition.

4CT proof

Let us start as before with induction assumption, but assuming that two edges are taken out and adding one, border condition problem is solved by induction assumption.

Let us consider the only critical situation, odd wheel, where two edges being absent, it colored using four colors, in general in several ways. Adding one edge we always solve border condition problem by induction assumption, in general with several possible colorings of the graph with n -1 edges. There remains one edge to be added. Both edges may be interchanged, by symmetry assumption. If wheel had 2k + 1, k ≥ 1, spokes, then 4k(2k + 1 cases are possible. By the way, situation in general, as described above, has evident central symmetric symmetry. Is border condition problem the same, i.e., with the same symmetry? Seems not, but something like what could be expected in outer planar graph.

Let us go further. In spe.

n-free-k-chromatic graphs and unique colorable graphs

Free minor closed classes may be characterized by forbidden minors of classes against which class is made free. This is made via Kratochvil's theorem [START_REF] Kratochvíl | About minor closed classes and the generalization of the notion of free-planar graphs[END_REF][START_REF] Zeps | Free Minor Closed Classes and the Kuratowski Theorem[END_REF]. In [START_REF] Kratochvíl | About minor closed classes and the generalization of the notion of free-planar graphs[END_REF] Kratochvíl proved very powerful theorem :

F (F ree(A)) = F (A) -∪ F (A) , where B -. = {G -e | G ∈ B, e ∈ E(G)} and B . = {H | H ∼ = G v, G ∈ B, v ∈ V (G)} and operation
[in its application G v] denotes a non unique splitting of vertex v in G, which is the opposite operation to edge addition and its contraction [in result giving vertex v].

We may try to characterize classes F ree k CH similar as in case of free minor closed classes with forbidden minors, but now we expect not to use minors but subgraphs. Forbidden subgraph for 4-chromatic graph is K 5 , for example, next to it arbitrary 5critical graph, and, if four color theorem is not correct supposedly, let us say, then H, the smallest counterexample to four color theorem, that should be 5-critical graph, is similarly forbidden subgraph for 4-chromatic graphs.

Let us fix an almost trivial assertion as corollary and then generalize it as non-trivial theorem.

Corollary 19. Graph G is k-chromatic iff it does not contain as direct subgraph k+1critical subgraph and χ(G) ≮ k.

Proof. If G has as direct subgraph k+1-critical graph, it can't be k-critical.

Let G be k-chromatic. Then it can't have as direct subgraph k+1-critical graph. Let G be without direct subgraph k+1-critical graph, χ(G) ≮ k. Then eliminating edges we must stop to subgraph that is k-critical but not k+1-critical.

Theorem 20. Let n < k(k + 1)/2. Graph is n-free-k-chromatic iff it does not contain as direct subgraph k+1-critical subgraph minus n edges and χ(G) ≮ k.

Proof. Let G has property nfk. Then, if assuming opposite it had k+1-critical subgraph minus n edges, adding n edges gave graph that where not k-chromatic. Trivial. It is easy to sea that graph may be rebuilt using algorithm given in [START_REF] Robin | An Update on the Four-Color Theorem[END_REF] and [START_REF] Fowler | Unique Coloring of Planar Graphs[END_REF], page 12: K4 {1,4,5,6} and sequence of vertices 2, 8, 7, 3 do this.

Let us assume that graph G doesn't contain such subgraph that were k+1-critical minus n edges, but χ(G) ≮ k. We must prove that graph has property nfk. Let us assume opposite. Graph doesn't possess property nfk and adding n edges gave k+1-chromatic graph [where number of deleted edges satisfies n < k(k + 1)/2]. In that case we could start taking off edges, not moving n edges that were added, until graph is k+1-critical. It is possible, because in case all possible edges are removed remaining n edges can't give subgraph K k+1 because of condition on number n, n < k(k + 1)/2, that does not allow K k+1 be created. Removing added n edges we receive subgraph of G that is k+1-critical minus n edges, and come to contradiction.

Unique coloring graphs and subgraphs

To go forward we need to consider graphs with forced or unique coloring. Uniquely colorable graph is such that has only one partitioning of colored vertices into sets of one color. See [START_REF] Fowler | Unique Coloring of Planar Graphs[END_REF] on this matter. Fig. 8 shows an excellent example of such graph, graph B 7 from forbidden subgraphs of projective plane. This graph has as subgraph K - 5 three direct subgraphs and thus it is forced to have only one coloring.

There is simple algorithm that reconstructs every uniquely 4-colorable graph. Take a subgraph K 4 and add successively new vertex of degree three. This fact follows from the fact that every edge 3-colorable graph with unique coloring must have at least one triangle. This fact is know as Fiorini-Wilson-Fisk conjecture and is proved by Robin Thomas and Thomas G. Fowler in [START_REF] Fowler | Unique Coloring of Planar Graphs[END_REF]. We would refer to it as FWF conjecture. In the example of fig. 8 as K 4 generating set should be taken {1, 4, 5, 6} and as all graph generating sequence sequence of vertices 2, 8, 7, 3.

FWF conjecture deals with planar graphs, but our example B 7 is non-planar. This example shows that conjecture might work outside planarity too. We are not going to try to find out how far it reaches, but use this fact as follows: let us call graph FWFreconstructible if it may be reconstructed by FWF algorithm. Thus, we know, according [START_REF] Fowler | Unique Coloring of Planar Graphs[END_REF], that FWF-reconstructibles are planar graphs and some non planar too, for example, B 7 . Trivial FWF-reconstructible graph let us call graph K 4 .

Lemma 21. If 4-chromatic graph is nontrivial FWF-reconstructible, then it contains subgraph K - 5 .

Figure 3

 3 Figure 3 explains in example how closure of path of closures is used to build 3connected graphs.Let for a while us consider only wheels as components. Then graph performed from simple wheels as closure of path of closures may be characterized as sequence n 1 , ...n l , l >= 3, where n i , 1 <= i <= l, is order of i-th wheel.

Fig. 5 .

 5 Fig. 5. Hajós construction repeated [2].

Fig. 6 .

 6 Fig. 6. Example of map with split [red] edges. Graph becomes free planar. In this case virtual edges should coincide with real edges.

Fig. 7 .

 7 Fig. 7. Graph becomes free planar after four edge-type splits and one vertex-type split.

Fig. 8 .

 8 Fig.8. Example of graph with unique coloring, graph B7 from projective plane forbidden minors. Bold is drawn edges that go into subgraphs K - 5 . It is easy to sea that graph may be rebuilt using algorithm given in[START_REF] Robin | An Update on the Four-Color Theorem[END_REF] and[START_REF] Fowler | Unique Coloring of Planar Graphs[END_REF], page 12: K4 {1,4,5,6} and sequence of vertices 2, 8, 7, 3 do this.

  ........................... . .

	x		y
		. .	........................... . . . .
	a	b	v	w
	Fig. 1. Idea of free-four-color theorem for case of free-planar graphs. 3-components of free-planar graph may be
	replaced with 3-cycles or 4-cycles, for example, it suffices to consider triangles {x, a, b} and {y, v, w}.

  . . . . . . . . . . . . . . . . ................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	1	2 {17, 27} : C 1 . . 5	. . . . . . . . . . . . . . . . . ................... 2 . . . 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -1 5 7 . 2 4 . . . . . . . . . . . . . . . . . . . 7 7 2 7 3 1 3 1 3 . {27, 37} : C 2 {17, 37} : C 3	6	3
			Cycle of g-vertices 17, 27, 37	Resulting graph
	Fig. 3. Resulting graph is formed as 3-closure of path of 2-closures C1 : {2, 7} : C2 : {3, 7} : C3 : {1, 7} :.
	Actually, cycle of g-edges is {17, 27}, {27, 37}, {37, 17}, but we may in place of it considering corresponding cycle
	of g-vertices 17, 27, 37.

Fig. 9. Forbidden minor for projective plane E27 [START_REF] Henry | 103 Graphs That Are Irreducible for the Projective Plane[END_REF]. Graph has at least three cycles of order five, but not triangles. The part that causes odd cycles is drawn bold. Non bold edges does not affect odd cycles in the graph. This graph is 3-chromatic, but free-3-chromatic too. Bold subgraph is of course free-3-chromatic. Added edges can be colored arbitrary, thus, graph retains its free-colorability's feature.

Proof. Let start FWF construction, take K 4 and add vertex. This graph is K - 5 . Theorem 22. If graph is nontrivial FWF-reconstructible, then each its vertex goes into some minor K - 5 . Proof. In case graph is planar, the FWF-construction gives only triangulations, and every new vertex fall into some subgraph, not only minor, K - 5 . In case of non-planarity first built K 4 plus last vertex with three edges are into minor K - 5 , because three distinct paths should be from last vertex to one vertex of K 4 , because graph is always 3-connected.

We should have use of some reverse assumptions.

Theorem 23. If 4-chromatic planar graph does not have subgraph K - 5 , then it is not uniquely colorable. More over, no part of the graph taken as induced subgraph may be uniquely colorable graph.

Proof. First part of assertion follows from fact that uniquely 4-colorable planar graph is FWF-reconstructible. Second part follows straight in case subgraph is 4-chromatic. In case it most 3-chromatic, one excessive color may be interchanged with whatever color from these most three colors.

Direct subgraphs

It is easy to see that graphs we have constructed as 4-critical graphs does not contain K - 5 , though have it as minor, thus, they may not be uniquely colorable graphs and no part of graph taken as some subgraph may be colored uniquely. We want to conclude from there that k-critical graphs all have property not containing as subgraphs k+1-critical graphs minus edge.

Further we expect that planar 4-critical graph has as direct subgraph K 4 which is K 4 with split off edge. General proposition is in Conjecture 35

Let take for example graph E 27 from forbidden graphs of projective plane. It is 3chromatic and is free-3-chromatic, because does not have subgraph K - 4 , but it has of course homeomorphic subgraphs K - 4 , not being atetrahedral graph. The same applies for projective plane forbidden graphs E 11 , E 6 and F 4 too. Neither of them have K - 4 as direct subgraph and they are 3-chromatic. Thus, they are free-3-chromatic.

Two technical lemmas are needed.

Lemma 24. Every non-edge in critical graph may be colored with different colors. Proof. Let one vertex of this non-edge be colored with the lonely color.

Lemma 25. Every non-edge in critical graph may be colored with the same color.

Proof. Let one vertex of this non-edge [vw], say, vertex v, be colored with the lonely color.

Let recolor other vertex with the same color.

Both lemmas may be generalized.

Lemma 26. Every independent set of vertices in critical graph may be colored with the same color.

Proof. Let one vertex of this non-edge [vw], say, vertex v, be colored with the lonely color.

Let recolor other vertices with the same color.

Lemma 27. Every independent set of at most k -1 vertices in k-critical graph may be colored with different colors.

Proof. In case this set of vertices is separating graph into parts, proof follows straightforward. Otherwise let us use induction. Let us split graph along these vertices letting graph be hold together with what it is hold together. As a basis of induction we may take graph with, say, k + 1 vertices which should be different from K - k+1 , which must be absent at all in critical graph.

Lemma 28. Let in critical graph k distinct vertices for all colorings have k distinct colors, i.e., they color differently, then subgraph K k is in the graph.

Proof. Let us suppose opposite and these k vertices have some non-edge. But, according lemma 25, every non-edge in critical graph may be colored with one color, thus, K k on these vertices must have less than k colors in this coloring.

Lemma before may be generalized. By the way, we must observe that K k is uniquely colorable graph.

Theorem 29. In k-critical graph n distinct vertices for all colorings receive n different colors iff induced subgraph on these vertices is K n .

Proof. In one direction assertion is trivial. Let us assume that in k-critical graph exist such subgraph induced by n vertices that in all colorings it receive n colors. Let us assume, to the contrary to what theorem says, that this graph is different from K n and thus has same non-edge vw. But, according lemma there exist coloring were v and w receive different colors, thus, this subgraph is not uniquely colorable graph. Even more, there does not exist pair of vertices that for all colorings would reside in common color subset. Thus, this graph can't even have some subgraph in it that were uniquely colorable, or it is itself uniquely colorable graph K n . If subgraph has at least one edge, then it must coincide with K n , starting with K 2 . In case it does not have edges, then lemma says that graph can be colored either with one color or at least two colors.

We may generalize the theorem as follows.

Theorem 30. In k-critical graph G vertices from proper vertex subset S with m vertices for all colorings receive n different colors iff m = n and induced subgraph on these vertices is K n , or graph G as subgraph has bipartite graph with vertices S in one of its sides.

Proof. Let arbitrary vertices x and y correspondingly inside and outside of induced subgraph G(S). Then either every such pair must be united by edge to exclude possibility to color, say, x with lonely color and other end recolor with the same color, or every vertex of G(S) by colorings must go into its own color subset, i.e., G(S) is isomorphic to K n . Thus, theorem allows case when G is taken odd wheel W 2n+1 and as S is taken its rim. Technical lemmas 26 and 27 say that there is possible colorings with any independent set colored either in one color or as many as number of vertices in this independent set not exceeding k -1. If independent set in subgraph is not less than chromatic number of subgraph extracted, i.e. not greater than two, then complementary graph of this subgraph should be tree or forest. Two cases, either subgraph contains odd cycles, n = 3, or doesn't, n = 2. Technical lemma exclude case when subgraph is independent set. Cases solve trivially.

Corollary 31. Belonging to its own Hadwiger class k-critical graph has K k-1 as subgraph.

Let us try to prove it for K < 5. For case k = 3 it is right of course.

Corollary 32. Planar 4-critical graph has K 3 as its direct subgraph.

Proof. Let us assume that planar graph exist that do not have K 3 . We can't make such graph using Hajós construction, because we would need for this reason minimal block with such property, but just that what is missing. Only critical graphs without this property ar non-planar. Either the construction used in this paper in chapter cannot give graphs without K 3 . The graph we are trying to find must be at least 4-connected. ....Proof must proceed.

This fact is known as Grötzsch's theorem which says: every triangle-free planar graph is 3-colorable. See [START_REF] Bondy | Graph Theory[END_REF] p. 406.

Conjecture 33. In k-critical graph every vertex either goes in some K k-1 or belongs to nontrivial, i.e., with at least three members, independent set of vertices.

The two famous non-planar 4-critical graphs, Chvátal's graph with 12 vertices and Grötzsch graph with 11 vertices don't have triangles at all, but in both graphs every vertex belongs to independent set with at least three vertices, (see [START_REF] Bondy | Graph Theory[END_REF] pages 362 and 366). Proof. Let us give arguments in favor of this supposition. If we do vertices merging operation that subgraph K k becomes K k then graph remains k-chromatic but it is not k-critical because vertex split does not affect its chromatic number. Thus, K k can't be direct subgraph of k-chromatic graph. Doing as if all possible such splits, graph is reduced in some minimal state. Formal proof should establish this, whether it is correct consideration.

If this conjecture where true, then we were to account for derivations of K k+1 as possible forbidden subgraphs for k-critical graphs that belong to its own Hadwiger class. Other k+1-critical subgraphs were 'eaten up' by the simplest critical graph, all other critical graph contained as parts this simplest graph, thus not necessary to account in the list of eventual forbidden graphs.

In the construction above where we were building 4-critical graphs, it is easy to see that they are actually 2-free-4-chromatic. I.e., to make subgraph K - 5 in them, two edges at least should be added.

We show it there.

Lemma 36. 4-critical graph does not have W 4 as subgraph.

Proof. . W 4 is uniquely 3-colorable graph. Hub of the wheel may be removed without affecting other coloring of graph in all colorings, except these where probably hub vertex were colored using lonely color. Let us in these cases in place of all vertex with edges as spokes of the wheel remove only one spoke which can't affect these colorings.

Lemma gives what follows.

Theorem 37. Every 4-critical graph is at least 2-free-4-chromatic.

Proof. Lemma before shows that 4-critical graph can't have W 4 as subgraph. Neither other case, W 3 plus C 3 , that is other possible division of K - 5 minus edge, is possible in 4-critical graph. These two cases exhaust ways of K - 5 minus edge division into components. Thus, 4-critical edge does not have K 5 with two eliminated edges, and it is 2-free-4-chromatic according theorem 34. 12. 4-critical graph characterized by 3 -3 -3 is 3-free-4-critical, because it does not contain any subgraph K 5 minus three edges.

But some classes of 4-critical graphs may be 3-free-4-critical too. Not-3-connected 4critical graphs built above are such. Graph from class of three-connected graphs built above characterized by 3 -3 -3 is 3-free-4-critical, see fig. 13.

We know that 4-critical graphs can't contain K - k , even stronger condition being working. We are interested in question about other k+1-critical graphs minus minimum n edges possibly being present in k-critical graphs. What we know is that for K 5 n = 3. What is the general number n(4)?

We must the same question put on 5-critical graphs against 6-critical graph minus possible minimum n edges presence in them. What is the number n( 5), and can't knowledge of these facts lead to ultimate proof of 4CT? Ordinary planar graphs that are not 4-critical all are free-4-chromatic with respect set of planar edges but not with respect all, i.e., non-planar edges too. In best case it may be free-4-chromatic but not free 2 -4-chromatic. What does it mean? Critical graphs may be built from free-planar parts with some amount of closures. If in place of free-planar graphs graphs from class PP are taken, it can not affect result for 4-critical graphs, because all non-planar 3-blocks coming as ballast should be eliminated if we want obtain 4-critical graph. If we wanted to use PP graphs essentially we would get only non-planar graphs. Is there some class between PP and free-planar graph class that could spoil situation around four color theorem? Free-Hadwiger five class. But it comes only with some special cases with comparing with class PP. Thus, free-planar graph class is that that guides ways of building of class of 4-critical graphs. But this was under assumption that four color theorem is right. We need other way considered too.

If four color theorem is supposedly wrong then smallest counterexample 5-critical planar graph H must be free-5-chromatic at least. May it be built from free-planar graphs and then closures applied?

Let us find planar subgraphs of K 6 with minimum edges eliminated.

Lemma 38. H must be at least free 3 -5-chromatic.

Proof. Smallest planar subgraphs of K 6 are obtainable eliminating at least three edges. But two more edges may be more than possible in K 6 subgraphs in H, because just two edges are excessive for graph to be obtainable from free-planar graphs.

It looks like following proposition must be true. We are going to check it further.

Lemma 39. H must be at least free 5 -5-chromatic.

Proof. Smallest free-planar subgraphs of K 6 are obtainable eliminating at least five edges.

Next, cases shown in fig. 13 must be considered to the effect that they are not possible in 5-critical graph.

We must end with theorem, in spe.

Theorem 40. Planar 5-critical graph H does not exist.

Proof. Proof should be based on excluding cases from above.