Longitudes de palabras en semigrupos de transformaciones generados por digrafos

XXXII Coloquio V´ıctor Neumann-Lara Universidad Aut´ onoma de San Luis Potos´ı

Longitudes de palabras en semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez Universidad de Guadalajara Trabajo conjunto con P.J. Cameron, M. Gadouleau y J.D. Mitchell

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Transformaciones singulares Sea [n] := {1, 2, . . . , n} y Singn := {α : [n] → [n] | α es una funci´ on singular} . Junto con la composici´ on de funciones, Singn es un semigrupo. Para α ∈ Singn , definimos el rank de α como rk(α) = |Im(α)|. Una funci´on α ∈ Singn es idempotente si α2 = α. Para a, b ∈ [n], a 6= b, definimos (a → b) ∈ Singn como la funci´on que fija todos los elementos de [n] \ {a} y manda a en b.

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Transformaciones singulares

Las funciones (a → b) son idempotentes de rank n − 1. Dado un subconjunto U ⊆ Singn , denotamos por hUi al subsemigrupo de Singn generado por U. Se sabe que el conjunto U := {(a → b) : a, b ∈ [n], a 6= b} genera a Singn . Se sabe adem´as que bastan la mitad de los idempotentes de U para generar a Singn ; de hecho, n(n−1) es la m´ınima cardinalidad de un 2 conjunto generador de Singn .

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Semigrupos y digrafos

A cualquier digrafo simple D con V (D) = [n] asociamos un semigrupo hDi ⊆ Singn como sigue hDi := h{(a → b) : (a, b) ∈ E (D)}i . Por ejemplo, si Kn es el grafo completo no dirigido, tenemos que hKn i = Singn . De hecho, Singn es generado por D si y s´ olo si D contiene un torneo fuertemente conexo.

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Semigrupos y digrafos El semigrupo OIn := {α ∈ Singn : v ≤ α(v ), ∀v ∈ [n]} de funciones singulares no decrecientes est´a generado por un torneo transitivo.

1

2

3 ~5 Figura: T

4

5

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Longitudes de palabras Estamos interesados en las longitudes de funciones α ∈ hDi escritas como palabras en los generadores {(a → b) : (a, b) ∈ E (D)}. Denotamos dichas longitudes como `(D, α).

Theorem (Howie-Iwahori ’77) Para cualquier α ∈ Singn , `(Kn , α) = n + cycl(α) − fix(α), donde cycl(α) es el n´ umero de componentes c´ıclicos en la gr´afica de α, y fix(α) es el n´ umero de puntos fijos de α.

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Longitudes de palabras No se conocen resultados no triviales para `(D, α) cuando D 6= Kn . Debido a las siguientes cotas `(D, α) ≥ n + cycl(α) − fix(α) ≥ n − fix(α) ≥ n − rk(α) nos interesa clasificar los digrafos D tales que se cumplan las siguientes condiciones: (C1) ∀α ∈ hDi, `(D, α) = n + cycl(α) − fix(α). (C2) ∀α ∈ hDi, `(D, α) = n − fix(α). (C3) ∀α ∈ hDi, `(D, α) = n − rk(α).

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Transformaciones constantes Las transformaciones constantes siembre alcanzan la menor de las cotas anteriores. Lemma Para cualquier digrafo D en [n], si α ∈ hDi tiene rank 1, entonces `(D, α) = n − 1.

En los siguientes resultados, s´ olo consideramos digrafos conexos ya que si D1 , . . . , Dk son las componentes conexas de D, entonces hDi ∼ = hD1 i × · · · × hDk i.

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Digrafos cerrados

Definition ¯ = V (D) y La cerradura D¯ de D es el digrafo cuyos v´ertices son V (D) cuyas aristas son ¯ = E (D) ∪ {(a, b) : (b, a) ∈ E (D) est´a en un ciclo dirigido de D}. E (D) ¯ Decimos que D es cerrado si D = D.

Lemma Para cualquier digrafo D, ¯ hDi = hDi.

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Condici´on (C1) Theorem Sea D un digrafo conexo en [n]. Las siguientes afirmaciones son equivalentes: 1

(C1): ∀α ∈ hDi, `(D, α) = n + cycl(α) − fix(α).

2

D es cerrado y satisface la siguiente propiedad: (?) Si v0 , v1 , v2 es un camino dirigido en D tal que d(v0 , v2 ) = 2, entonces N + ({v1 , v2 }) ⊆ {v0 , v1 , v2 }.

Corollary Cualquier digrafo cerrado y transitivo satisface la condici´on (C1).

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Condici´on (C2) Consideremos los siguientes digrafos:

1

2

4

3

5

4

4

2

5

3

Γ1

Γ2

1

5

3

2

1 Γ3

1

4

2

3 Γ4

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Condici´on (C2)

Denotamos por Θk al ciclo dirigido con k v´ertices. Theorem Sea D un digrafo conexo en [n]. Las siguientes afirmaciones son equivalentes: 1

(C2): ∀α ∈ hDi, `(D, α) = n − fix(α).

2

D es cerrado, satisface la propiedad (?), y no tiene un subdigrafo isomorfo a Γ1 , Γ2 , Γ3 , Γ4 , o Θk , con k ≥ 5.

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Condici´on (C3)

Theorem Sea D un digrafo conexo en [n]. Las siguientes afirmaciones son equivalentes: 1

(C3): ∀α ∈ hDi, `(D, α) = n − rk(α).

2

hDi es una banda, i.e. todo elemento α ∈ hDi es idempotente.

3

n=2yD∼ = K2 , o D es un digrafo bipartito (cuyas aristas siempre van en el mismo sentido entre las partes).

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Palabras largas

Tambi´en estamos interesados en las palabras m´ as largas en semigrupos generados por algunas familias de digrafos. Sea Dn una familia de digrafos en [n]. ax {`(D, α) : D ∈ Dn , α ∈ hDi, rk(α) = r } , `D m´ ax (n, r ) := m´ `D ax {`(D, α) : D ∈ Dn , α ∈ hDi} . m´ ax (n) := m´

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Palabras largas

Sea Dn la familia de todos los digrafos en [n]. n\r 2 3 4 5 6

1 1 2 3 4 5

2

3

4

5

6 11 18 26

13 24 42

33 51

66

Cuadro: Primeros valores de `D m´ ax (n, r )

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Digrafos ac´ıclicos

Theorem Sea Acyclicn la familia de digrafos ac´ıclicos en [n]. Para cualquier n ≥ 3 y 2 ≤ r ≤ n − 1, tenemos que `Acyclic (n, r ) = m´ ax

(n − r )(n + r − 3) + 1, 2

1 `Acyclic (n) = `Acyclic (n, 2) = (n2 − 3n + 4). m´ ax m´ ax 2 Constru´ımos expl´ıcitamente un digrafo ac´ıclico Qn el cual siempre alcanza las cotas superiores del teorema anterior.

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Torneos fuertemente conexos La familia Tourn de torneos fuertemente conexos en [n] es interesante porque representa conjuntos generadores minimales de Singn formados por idempotentes. n\r 3 4 5 6 7

2 (6, 6) (8, 8) (6, 11) (8, 13) (8, 16)

3

4

5

6

(11, 11) (8, 14) (10, 18) (10, 22)

(10, 17) (11, 21) (11, 26)

(13, 24) (13, 29)

(15, 32)


Tour Cuadro: Primeros valores de `Tour m´ın (n, r ), `m´ ax (n, r ) .

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Torneos fuertemente conexos

Theorem Para cualquier n impar, tenemos que n + r − 2 ≤ `Tour m´ın (n, r ) ≤ n + 8r , (ˆ r + 1)(n − rˆ) − 1 ≤ `Tour m´ ax (n, r ) ≤ 6rn + n − 10r . donde rˆ = m´ın{r − 1, bn/2c}.

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Torneos fuertemente conexos Conjetura (max) Para toda r , `(πn , r ) = `Tour m´ ax (n, r ), donde πn es el torneo en [n] con aristas E (πn ) = {(i, (i + 1)mod(n)) : i ∈ [n]} ∪ {(i, j) : j + 1 < i}.

1

2

3 Figura: π5

4

5

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Torneos fuertemente conexos Conjetura (min) Para toda n ≥ 3 impar y toda r , `Tour m´ın (n, r ) = `(κn , r ), donde κn es el torneo circulante en [n]. 5

4

1

3

2 Figura: κ5 .

Semigrupos de transformaciones generados por digrafos

Alonso Castillo Ram´ırez

Gracias por esuchar!

P.J. Cameron, A. Castillo-Ramirez, M. Gadouleau, J.D. Mitchell, Lengths of words in transformation semigroupsgenerated by digraphs, Journal of Algebraic Combinatorics 45 (2017) 149–170.