Patrón inevitable

Al igual que una palabra, un patrón (también llamado término ) es una secuencia de símbolos sobre algún alfabeto .

La multiplicidad mínima del patrón${\displaystyle p}$es${\displaystyle m(p)=\min(\mathrm {count_{p}} (x):x\in p)}$dónde${\displaystyle \mathrm {count_{p}} (x)}$es el número de ocurrencias del símbolo${\displaystyle x}$en patrón${\displaystyle p}$. En otras palabras, es el número de ocurrencias en${\displaystyle p}$del símbolo que aparece con menos frecuencia en${\displaystyle p}$.

Dados alfabetos finitos${\displaystyle \Sigma }$y${\displaystyle \Delta }$, una palabra${\displaystyle x\in \Sigma ^{*}}$es un ejemplo del patrón${\displaystyle p\in \Delta ^{*}}$si existe un morfismo de semigrupo no borrador${\displaystyle f:\Delta ^{*}\rightarrow \Sigma ^{*}}$de tal manera que${\displaystyle f(p)=x}$, dónde${\displaystyle \Sigma ^{*}}$denota la estrella de Kleene de${\displaystyle \Sigma }$. No borrar significa que${\displaystyle f(a)\neq \varepsilon }$a pesar de${\displaystyle a\in \Delta }$, dónde${\displaystyle \varepsilon }$denota la cadena vacía .

Una palabra${\displaystyle w}$Se dice que coincide o encuentra un patrón.${\displaystyle p}$si un factor (también llamado subpalabra o subcadena ) de${\displaystyle w}$es un ejemplo de${\displaystyle p}$. De lo contrario,${\displaystyle w}$Se dice que evita${\displaystyle p}$, o ser${\displaystyle p}$-libre. Esta definición puede generalizarse al caso de un infinito${\displaystyle w}$, basado en una definición generalizada de "subcadena".

Un patrón${\displaystyle p}$es inevitable en un alfabeto finito${\displaystyle \Sigma }$si cada palabra suficientemente larga${\displaystyle x\in \Sigma ^{*}}$debe coincidir${\displaystyle p}$; formalmente: si${\displaystyle \exists n\in \mathrm {N} .\ \forall x\in \Sigma ^{*}.\ (|x|\geq n\implies x{\text{ matches }}p)}$. De lo contrario,${\displaystyle p}$es evitable en${\displaystyle \Sigma }$lo que implica que existen infinitas palabras en el alfabeto.${\displaystyle \Sigma }$que evitan${\displaystyle p}$.

Por el lema de Kőnig , patrón${\displaystyle p}$es evitable en${\displaystyle \Sigma }$si y solo si existe una palabra infinita${\displaystyle w\in \Sigma ^{\omega }}$que evita${\displaystyle p}$. ^{[ 1 ]}

Dado un patrón${\displaystyle p}$y un alfabeto${\displaystyle \Sigma }$. A${\displaystyle p}$-palabra libre${\displaystyle w\in \Sigma ^{*}}$es un máximo${\displaystyle p}$-palabra gratis sobre${\displaystyle \Sigma }$si${\displaystyle aw}$y${\displaystyle wa}$fósforo${\displaystyle p}$${\displaystyle \forall a\in \Sigma }$.

Un patrón${\displaystyle p}$es un patrón inevitable (también llamado término de bloqueo ) si${\displaystyle p}$es inevitable en cualquier alfabeto finito.

Si un patrón es inevitable y no se limita a un alfabeto específico, entonces es inevitable para cualquier alfabeto finito por defecto. Por el contrario, si se dice que un patrón es evitable y no se limita a un alfabeto específico, entonces es evitable en algún alfabeto finito por defecto.

Un patrón${\displaystyle p}$es${\displaystyle k}$-evitable si${\displaystyle p}$es evitable en un alfabeto${\displaystyle \Sigma }$de tamaño${\displaystyle k}$. De lo contrario,${\displaystyle p}$es${\displaystyle k}$-inevitable, lo que significa${\displaystyle p}$es inevitable en cada alfabeto de tamaño${\displaystyle k}$. ^{[ 2 ]}

Si el patrón${\displaystyle p}$es${\displaystyle k}$-evitable, entonces${\displaystyle p}$es${\displaystyle g}$-evitable para todos${\displaystyle g\geq k}$.

Dado un conjunto finito de patrones evitables${\displaystyle S=\{p_{1},p_{2},...,p_{i}\}}$, existe una palabra infinita${\displaystyle w\in \Sigma ^{\omega }}$de tal manera que${\displaystyle w}$evita todos los patrones de${\displaystyle S}$. ^{[ 1 ]} Deje${\displaystyle \mu (S)}$denotan el tamaño del alfabeto mínimo${\displaystyle \Sigma '}$de tal manera que${\displaystyle \exists w'\in {\Sigma '}^{\omega }}$evitando todos los patrones de${\displaystyle S}$.

El índice de evitabilidad de un patrón${\displaystyle p}$es el más pequeño${\displaystyle k}$de tal manera que${\displaystyle p}$es${\displaystyle k}$-evitable y${\displaystyle \infty }$si${\displaystyle p}$es inevitable. ^{[ 1 ]}

Todas las palabras de Zimin son inevitables. ^{[ 4 ]}

Una palabra${\displaystyle w}$es inevitable si y solo si es un factor de una palabra Zimin. ^{[ 4 ]}

Dado un alfabeto finito${\displaystyle \Sigma }$, dejar${\displaystyle f(n,|\Sigma |)}$representan el más pequeño${\displaystyle m\in \mathrm {Z} ^{+}}$de tal manera que${\displaystyle w}$partidos${\displaystyle Z_{n}}$a pesar de${\displaystyle w\in \Sigma ^{m}}$. Tenemos las siguientes propiedades: ^{[ 5 ]}

• ${\displaystyle f(1,q)=1}$
• ${\displaystyle f(2,q)=2q+1}$
• ${\displaystyle f(3,2)=29}$
• ${\displaystyle f(n,q)\leq {^{n-1}q}=\underbrace {q^{q^{\cdot ^{\cdot ^{q}}}}} _{n-1}}$

${\displaystyle Z_{n}}$es el patrón inevitable más largo construido por el alfabeto${\displaystyle \Delta =\{x_{1},x_{2},...,x_{n}\}}$desde${\displaystyle |Z_{n}|=2^{n}-1}$.

Dado un patrón${\displaystyle p}$sobre algún alfabeto${\displaystyle \Delta }$, decimos${\displaystyle x\in \Delta }$es gratis para${\displaystyle p}$si existen subconjuntos${\displaystyle A,B}$de${\displaystyle \Delta }$de tal manera que se cumplan las siguientes condiciones:

1. ${\displaystyle uv}$es un factor de${\displaystyle p}$y${\displaystyle u\in A}$↔ ${\displaystyle uv}$es un factor de${\displaystyle p}$y${\displaystyle v\in B}$
2. ${\displaystyle x\in A\backslash B\cup B\backslash A}$

Por ejemplo, dejemos${\displaystyle p=abcbab}$, entonces${\displaystyle b}$es gratis para${\displaystyle p}$ya que existen${\displaystyle A=ac,B=b}$que cumplen las condiciones anteriores.

Un patrón${\displaystyle p\in \Delta ^{*}}$se reduce a patrón${\displaystyle q}$si existe un símbolo${\displaystyle x\in \Delta }$de tal manera que${\displaystyle x}$es gratis para${\displaystyle p}$, y${\displaystyle q}$se puede obtener eliminando todas las ocurrencias de${\displaystyle x}$de${\displaystyle p}$Denotemos esta relación por${\displaystyle p{\stackrel {x}{\rightarrow }}q}$.

Por ejemplo, dejemos${\displaystyle p=abcbab}$, entonces${\displaystyle p}$puede reducirse a${\displaystyle q=aca}$desde${\displaystyle b}$es gratis para${\displaystyle p}$.

Una palabra${\displaystyle w}$Se dice que está cerrado con llave si${\displaystyle w}$no tiene letra libre; por lo tanto${\displaystyle w}$no se puede reducir. ^{[ 6 ]}

Dados los patrones${\displaystyle p,q,r}$, si${\displaystyle p}$se reduce a${\displaystyle q}$y${\displaystyle q}$se reduce a${\displaystyle r}$, entonces${\displaystyle p}$se reduce a${\displaystyle r}$Denotemos esta relación por${\displaystyle p{\stackrel {*}{\rightarrow }}r}$.

Un patrón${\displaystyle p}$es inevitable si y solo si${\displaystyle p}$se reduce a una palabra de longitud uno; por lo tanto${\displaystyle \exists w}$de tal manera que${\displaystyle |w|=1}$y${\displaystyle p{\stackrel {*}{\rightarrow }}w}$. ^{[ 7 ] [ 4 ]}

Dado un gráfico simple${\displaystyle G=(V,E)}$, una coloración de borde${\displaystyle c:E\rightarrow \Delta }$coincide con el patrón${\displaystyle p}$si existe un camino simple${\displaystyle P=[e_{1},e_{2},...,e_{r}]}$en${\displaystyle G}$de tal manera que la secuencia${\displaystyle c(P)=[c(e_{1}),c(e_{2}),...,c(e_{r})]}$partidos${\displaystyle p}$. De lo contrario,${\displaystyle c}$Se dice que evita${\displaystyle p}$o ser${\displaystyle p}$-gratis.

De manera similar, una coloración de vértices${\displaystyle c:V\rightarrow \Delta }$coincide con el patrón${\displaystyle p}$si existe un camino simple${\displaystyle P=[c_{1},c_{2},...,c_{r}]}$en${\displaystyle G}$de tal manera que la secuencia${\displaystyle c(P)}$partidos${\displaystyle p}$.

El número cromático del patrón${\displaystyle \pi _{p}(G)}$es el número mínimo de colores distintos necesarios para un${\displaystyle p}$-coloración de vértices gratuita${\displaystyle c}$sobre el gráfico${\displaystyle G}$.

Dejar${\displaystyle \pi _{p}(n)=\max\{\pi _{p}(G):G\in G_{n}\}}$dónde ${\displaystyle G_{n}}$es el conjunto de todos los grafos simples con un grado máximo no mayor que${\displaystyle n}$.

Similarmente,${\displaystyle \pi _{p}'(G)}$y${\displaystyle \pi _{p}'(n)}$están definidos para los colores de los bordes.

Un patrón${\displaystyle p}$es evitable en los gráficos si${\displaystyle \pi _{p}(n)}$está delimitado por${\displaystyle c_{p}}$, dónde${\displaystyle c_{p}}$solo depende de${\displaystyle p}$.

• La evitación en palabras puede expresarse como un caso específico de evitación en gráficos; por lo tanto, un patrón${\displaystyle p}$es evitable en cualquier alfabeto finito si y solo si${\displaystyle \pi _{p}(P_{n})\leq c_{p}}$a pesar de${\displaystyle n\in \mathrm {Z} ^{+}}$, dónde${\displaystyle P_{n}}$es un gráfico de${\displaystyle n}$vértices concatenados.

Existe una constante absoluta${\displaystyle c}$, de tal manera que${\displaystyle \pi _{p}(n)\leq cn^{\frac {m(p)}{m(p)-1}}\leq cn^{2}}$para todos los patrones${\displaystyle p}$con${\displaystyle m(p)\geq 2}$. ^{[ 8 ]}

Dado un patrón${\displaystyle p}$, dejar${\displaystyle n}$representan el número de símbolos distintos de${\displaystyle p}$. Si${\displaystyle |p|\geq 2^{n}}$, entonces${\displaystyle p}$es evitable en los gráficos.

Dado un patrón${\displaystyle p}$de tal manera que${\displaystyle count_{p}(x)}$es igual para todos${\displaystyle x\in p}$, entonces${\displaystyle \pi _{p}'(K_{2}^{k})\leq 2^{k}-1}$a pesar de${\displaystyle k\geq 1}$, dónde${\displaystyle K_{n}}$es el gráfico completo de${\displaystyle n}$vértices. ^{[ 8 ]}

Dado un patrón${\displaystyle p}$de tal manera que${\displaystyle m(p)\geq 2}$y un árbol arbitrario${\displaystyle T}$, dejar${\displaystyle S}$sea ​​el conjunto de todos los subpatrones evitables y sus reflejos de${\displaystyle p}$. Entonces${\displaystyle \pi _{p}(T)\leq 3\mu (S)}$. ^{[ 8 ]}

Dado un patrón${\displaystyle p}$de tal manera que${\displaystyle m(p)\geq 2}$y un árbol${\displaystyle T}$con título${\displaystyle n\geq 2}$. Dejar${\displaystyle S}$sea ​​el conjunto de todos los subpatrones evitables y sus reflejos de${\displaystyle p}$, entonces${\displaystyle \pi _{p}'(T)\leq 2(n-1)\mu (S)}$. ^{[ 8 ]}