Patrón inevitable

En matemáticas y en informática teórica , un patrón es un patrón inevitable si es inevitable en cualquier alfabeto finito.

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 es donde es el número de ocurrencias del símbolo en el patrón . En otras palabras, es el número de ocurrencias en del símbolo que ocurre con menor frecuencia en . ${\estilo de visualización p}$${\displaystyle m(p)=\min(\mathrm {count_{p}} (x):x\in p)}$${\displaystyle \mathrm {count_{p}} (x)}$${\displaystyle x}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$

Dados alfabetos finitos y , una palabra es una instancia del patrón si existe un morfismo de semigrupo que no se borra tal que , donde denota la estrella de Kleene de . No borrable significa que para todos los , donde denota la cadena vacía . ${\displaystyle \Sigma }$${\displaystyle \Delta }$${\displaystyle x\in \Sigma ^{*}}$${\displaystyle p\in \Delta ^{*}}$ ${\displaystyle f:\Delta ^{*}\rightarrow \Sigma ^{*}}$${\displaystyle f(p)=x}$${\displaystyle \Sigma ^{*}}$${\displaystyle \Sigma }$${\displaystyle f(a)\neq \varepsilon }$${\displaystyle a\in \Delta }$${\displaystyle \varepsilon }$

Se dice que una palabra coincide o encuentra un patrón si un factor (también llamado subpalabra o subcadena ) de es una instancia de . De lo contrario, se dice que evita , o que es libre de . Esta definición se puede generalizar al caso de un infinito , basándose en una definición generalizada de "subcadena". ${\displaystyle w}$${\displaystyle p}$${\displaystyle w}$${\displaystyle p}$${\displaystyle w}$${\displaystyle p}$${\displaystyle p}$${\displaystyle w}$

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

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

Dado un patrón y un alfabeto , una palabra libre es una palabra libre máxima si y coincide . ${\displaystyle p}$${\displaystyle \Sigma }$${\displaystyle p}$${\displaystyle w\in \Sigma ^{*}}$${\displaystyle p}$${\displaystyle \Sigma }$${\displaystyle aw}$${\displaystyle wa}$${\displaystyle p}$ ${\displaystyle \forall a\in \Sigma }$

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

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 es -evitable si es evitable en un alfabeto de tamaño . De lo contrario, es -inevitable, lo que significa que es inevitable en todo alfabeto de tamaño . ^[2]${\displaystyle p}$${\displaystyle k}$${\displaystyle p}$${\displaystyle \Sigma }$${\displaystyle k}$${\displaystyle p}$${\displaystyle k}$${\displaystyle p}$${\displaystyle k}$

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

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

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

• Un patrón es evitable si es una instancia de un patrón evitable . ^[3]${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle p}$
• Sea el patrón evitable un factor del patrón , entonces también es evitable. ^[3]${\displaystyle p}$${\displaystyle q}$${\displaystyle q}$
• Un patrón es inevitable si y sólo si es un factor de algún patrón inevitable .${\displaystyle q}$${\displaystyle q}$${\displaystyle p}$
• Dado un patrón inevitable y un símbolo que no está en , entonces es inevitable. ^[3]${\displaystyle p}$${\displaystyle a}$${\displaystyle p}$${\displaystyle pap}$
• Dado un patrón inevitable , entonces la reversión es inevitable.${\displaystyle p}$ ${\displaystyle p^{R}}$
• Dado un patrón inevitable , existe un símbolo tal que aparece exactamente una vez en . ^[3]${\displaystyle p}$${\displaystyle a}$${\displaystyle a}$${\displaystyle p}$
• Sea el número de símbolos distintos del patrón . Si , entonces es evitable. ^[3]${\displaystyle n\in \mathrm {N} }$${\displaystyle p}$${\displaystyle |p|\geq 2^{n}}$${\displaystyle p}$

Dado el alfabeto , las palabras Zimin (patrones) se definen recursivamente para y . ${\displaystyle \Delta =\{x_{1},x_{2},...\}}$${\displaystyle Z_{n+1}=Z_{n}x_{n+1}Z_{n}}$${\displaystyle n\in \mathrm {Z} ^{+}}$${\displaystyle Z_{1}=x_{1}}$

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

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

Dado un alfabeto finito , sea , el más pequeño que coincida con todos los . Tenemos las siguientes propiedades: ^[5]${\displaystyle \Sigma }$${\displaystyle f(n,|\Sigma |)}$${\displaystyle m\in \mathrm {Z} ^{+}}$${\displaystyle w}$${\displaystyle Z_{n}}$${\displaystyle w\in \Sigma ^{m}}$

• ${\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 desde . ${\displaystyle \Delta =\{x_{1},x_{2},...,x_{n}\}}$${\displaystyle |Z_{n}|=2^{n}-1}$

Dado un patrón sobre algún alfabeto , decimos que es libre si existen subconjuntos de tales que se cumple lo siguiente: ${\displaystyle p}$${\displaystyle \Delta }$${\displaystyle x\in \Delta }$${\displaystyle p}$${\displaystyle A,B}$${\displaystyle \Delta }$

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

Por ejemplo, sea , entonces es libre porque existen que satisfacen las condiciones anteriores. ${\displaystyle p=abcbab}$${\displaystyle b}$${\displaystyle p}$${\displaystyle A=ac,B=b}$

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

Por ejemplo, sea , entonces se puede reducir a ya que es libre para . ${\displaystyle p=abcbab}$${\displaystyle p}$${\displaystyle q=aca}$${\displaystyle b}$${\displaystyle p}$

Se dice que una palabra está bloqueada si no tiene ninguna letra libre; por lo tanto, no se puede reducir. ^[6]${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$

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

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

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

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

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

Sea donde es el conjunto de todos los gráficos simples con un grado máximo no mayor que . ${\displaystyle \pi _{p}(n)=\max\{\pi _{p}(G):G\in G_{n}\}}$${\displaystyle G_{n}}$${\displaystyle n}$

De manera similar, y se definen para coloraciones de bordes. ${\displaystyle \pi _{p}'(G)}$${\displaystyle \pi _{p}'(n)}$

Un patrón se puede evitar en los gráficos si está limitado por , donde solo depende de . ${\displaystyle p}$${\displaystyle \pi _{p}(n)}$${\displaystyle c_{p}}$${\displaystyle c_{p}}$${\displaystyle p}$

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

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

Dado un patrón , represente la cantidad de símbolos distintos de . Si , entonces es evitable en gráficos. ${\displaystyle p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle |p|\geq 2^{n}}$${\displaystyle p}$

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

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

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

• La secuencia de Thue-Morse no tiene cubos ni superposiciones, por lo que evita los patrones y . ^[2]${\displaystyle xxx}$${\displaystyle xyxyx}$
• Una palabra sin cuadrados es aquella que evita el patrón . La palabra sobre el alfabeto obtenida tomando la primera diferencia de la secuencia de Thue-Morse es un ejemplo de una palabra infinita sin cuadrados. ^{[9] [10]}${\displaystyle xx}$${\displaystyle \{0,\pm 1\}}$
• Los patrones son inevitables en cualquier alfabeto, ya que son factores de las palabras Zimin. ^{[11] [1]}${\displaystyle x}$${\displaystyle xyx}$
• Los patrones de potencia son 2-evitables. ^[1]${\displaystyle x^{n}}$${\displaystyle n\geq 3}$
• Todos los patrones binarios se pueden dividir en tres categorías: ^[1]
  • ${\displaystyle \varepsilon ,x,xyx}$son inevitables.
  • ${\displaystyle xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy}$tienen un índice de evitabilidad de 3.
  • otros tienen un índice de evitabilidad de 2.
• ${\displaystyle abwbaxbcyaczca}$tiene un índice de evitabilidad de 4, al igual que otras palabras bloqueadas. ^[6]
• ${\displaystyle abvacwbaxbcycdazdcd}$tiene un índice de evitabilidad de 5. ^[12]
• El umbral repetitivo es el ínfimo de exponentes que se puede evitar en un alfabeto de tamaño . Véase también el teorema de Dejean .${\displaystyle RT(n)}$${\displaystyle k}$${\displaystyle x^{k}}$${\displaystyle n}$

• ¿Existe un patrón evitable tal que el índice de evitabilidad sea 6?${\displaystyle p}$${\displaystyle p}$
• Dado un patrón arbitrario , ¿existe un algoritmo para determinar el índice de evitabilidad de ? ^[1]${\displaystyle p}$${\displaystyle p}$

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Cambridge University Press . ISBN 978-0-521-82332-6.Zbl 1086.11015  .
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatoria de palabras. Palabras de Christoffel y repeticiones en palabras . Serie monográfica CRM. Vol. 27. Providence, RI: American Mathematical Society . ISBN. 978-0-8218-4480-9.Zbl 1161.68043  .
• Lothaire, M. (2011). Combinatoria algebraica sobre palabras . Enciclopedia de matemáticas y sus aplicaciones. Vol. 90. Con prólogo de Jean Berstel y Dominique Perrin (reimpresión de la edición de tapa dura de 2002). Cambridge University Press . ISBN 978-0-521-18071-9.Zbl 1221.68183  .
• Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Lecture Notes in Mathematics. Vol. 1794. Berlín: Springer-Verlag . ISBN. 3-540-44141-7.Zbl 1014.11015  .