E

A M

D2020

XI ENCUENTROS ANDALUCES DE MATEMÁTICA DISCRETA

SEVILLA6 y 7 de febrero

de 2020

XI ENCUENTRO ANDALUZ DE MATEMÁTICA DISCRETA

Miércoles 5 de Febrero

RECEPCIÓN a las 20:00h en el Bulebar Café Dirección: Alameda de Hércules 83, 41002, Sevilla

Jueves 6 de Febrero

(La duración de las charlas se ha establecido según indicación de los autores, entendiéndose 20 minutos la

duración por defecto)

8:30-8:50 REGISTRO (en la entrada del IMUS)

8:50-9:00 APERTURA

9:00-10:00 Conferencia Invitada: Alberto Márquez

“Hacerse mayor y otros problemas”

10:00-10:30 CAFÉ

10:30-12:05

10:30-10:50 A.M. Encinas, M. J. Jiménez. Matrices triangulares, recurrencias combinatorias y

ecuaciones lineales en diferencia

10:50-11:10 E. Briand, M. Rosas, and Stephan Trandafir. The chamber complex for the

Littlewood-Richardson coefficients of GL4

11:10-11:25 A. Martínez-Pérez. Generalized chordality, vertex separators and hyperbolicity on

graphs

11:25-11:45 L. Boza, M.P. Revuelta, M.I. Sanz. The exact value of 3-color off-diagonal

generalized Schur numbers S(2,2,k)

11:45-12:05 L. Boza, M.P. Revuelta, M.I. Sanz. Lower bounds and exact values on the weak

Schur numbers

12:05-12:15 DESCANSO

12:15-13:40

12:15-12:30 M.A. Garrido-Vizuete, A. Márquez, R. Robles. Can labelled vertices make the graph

euclidean realizable?

12:30-12:45 C. Ansotegui, C. Dalfó, M.A. Fiol, N. López. El problema de Mondrian

12:45-13:05 D. Garijo, A. Márquez, J. Pfeifle, R.I. Silveira. The continuous mean distance of a

graph

13:05-13:25 A. Cañete, I. Fernández, A. Márquez. Optimal subdivisions of a convex body

13:25-13:40 E. Abajo Casado, M. Bendala García. Grafos regulares con cintura 5 y mínimo orden

13:40-15:10 ALMUERZO (en Comedor Universitario)

15:10-16:30

15:10-15:30 S.G. Corregidor. k-metric dimensión in some infinite graphs and ultrametric spaces

15:30-15:50 M.J. Chávez, A. Quintero, M.T. Villar-Liñán. Transversals, domination and the LS

category on surfaces

15:50-16:10 H.A. Ahangar, M.P. Álvarez, M. Chellali, S.M. Sheikholeslami, J.C. Valenzuela-

Tripodoro. Dominación romana triple en grafos

16:10-16:30 R. Reyes, J.M. Rodríguez, J.M. Sigarreta, M. Villeta. Domination on hyperbolic

graphs

16:30-17:00 CAFÉ

17:00-18:30

17:00-17:20 R.M. Casablanca, P. Dankelmann. Wiener index and average eccentricity for some

families of graphs and products

17:20-17:35 F.J. Cruz, A. del Valle, J. Núñez-Valdés, M. Pena. Sobre el concepto de jerarquía de

grafos

17:35-17:55 V. Álvarez, J.A. Armario, R.M. Falcón, M.D. Frau, F. Gudiel, M.D. Güemes, A.

Osuna. Recent progress son cocyclic matrices

17:55-18:10 J. Lacalle, R. Martín-Cuevas. Complejidad de estados cuánticos de Fibonacci

18:10-18:30 J.R. Portillo. Grafos prohibidos y lógica cuántica

18:30-18:45 BUSINESS MEETING

21:00 CENA DEL CONGRESO EN RESTAURANTE “DOÑA CLARA”

Viernes 7 de Febrero

(La duración de las charlas se ha establecido según indicación de los autores, entendiéndose 20 minutos la

duración por defecto)

9:30-10:30 Conferencia Invitada: José Cáceres

“Convexidad en grafos: una perspectiva personal”

10:30-11:00 CAFÉ

11:00-12:35

11:00-11:20. A.M. Encinas, M.J. Jiménez. La inversa de grupo de algunas matrices circulantes

11:20-11:40 A. Carmona, M. Mitjana. La constante de Kemeny de caminos aleatorios con barreras

reflejantes

11:40-12:00 M.V. Carriegos. Particiones en un submonoide de un grupo abeliano

12:00-12:20 L. Boza, M.P. Revuelta, M.I. Sanz. Números de Schur débiles no diagonales

12:20-12:35 J. Cáceres, M.A. Garrido-Vizuete, A. Márquez. Pascal automata and matroids

12:35-12:45 DESCANSO

12:45-13:45

12:45-13:05 M.I. Hartillo Hermoso, J.M. Jiménez Cobano, J.M. Ucha Enríquez. Sobre el problema

del 3-coloreado de un grafo utilizando sistemas de ecuaciones polinomiales

13:05-13:25 Mucuy-Kak Guevara. Vertex-monochromatic connectivity of strong digraphs

13:25-13:45 A.R. García Lozano, S.R. Pereira de Mattos, A. Santos Siqueira, P. Cardoso Petito, M.

Câmara de Souza, P. Genaio. Familias consistentes y coloración total de grafos

13:45-15:10 ALMUERZO (en Comedor Universitario)

15:10-16:40

15:10-15:30 J.M. Gavilán Izquierdo, A. González, M.L. Puertas. Un modelo para el aprendizaje de

la teoría de grafos

15:30-15:45 G. Aguirre Carrazana, R. González Díaz, E. Paluzo Hidalgo. Análisis topológico de

datos: Aplicación en reconocimiento de emociones

15:45-16:05 N. Atienza, L.M. Escudero, M.J. Jiménez, M. Soriano-Trigueros. Topological data

analysis for the study of self-organization of cells in a biological tissue

16:05-16:20 N. Birkeland, A. Diánez Martínez, A. García Moyano, P. García Vázquez, M.A.

González del Valle, J.M. González Grau. Estructura modular de las enzimas como punto de partida

para la síntesis de nuevos biocatalizadores

16:20-16:40 S. Ambari, J. Buceta, L.M. Escudero, P. Gómez-Gálvez, C.I. Grima, A. Márquez, R.

Robles, A. Tagua, P. Vicente-Munuera. Escutoides: pasado, presente y futuro

16:40-17:15 CLAUSURA Y CAFÉ

Hacerse mayor y otros problemas

Alberto Márquez

Universidad de Sevilla

El título de esta charla corresponde con una película (?) española de 2018 (Por si alguien

está tentando de verla, su calificación en imdb es inferior a 5), pero me ha parecido un

buen título, descriptivo, para esta charla.

Hacerse mayor significa que me he encontrado una buena cantidad de problemas a lo

largo de todos estos años, algunos de esos problemas se han resuelto gracias a que siempre

he sabido rodearme de la mejor gente (alguna virtud tenía que tener). Pero otros, a pesar

de la sabiduría de mis colaboradores, se han quedado en el limbo de los problemas no

resueltos. No voy a repasar todos ellos, sino solo una pequeña colección por si alguno

sirve de inspiración a la audiencia.

Matrices triangulares, Recurrencias Combinatorias yEcuaciones Lineales en Diferenciass

Andrés M. Encinas, M. José Jiménez

Departament de Matemàtiques, Universitat Politècnica de Catalunya.E-mail: andres.marcos.encinas@upc.edu, maria.jose.jimenez@upc.edu

Resumen. En esta comunicación presentaremos nuestro trabajo en matrices triangula-res infinitas de profundidad mayor que 1, generadas por dos sucesiones dobles. Este tipode matrices generalizan algunas recurrencias bien conocidas que aparecen en combina-toria enumerativa y están relacionadas con un problema planteado por Graham, Knuthand Patashnik sobre matrices triangulares con generadores afines.

En este trabajo haremos uso de la relación de estas matrices con ecuaciones linealesen diferencias y especialmente con la denominada Fórmula de tres términos. Mostraremospor medio de algunos ejemplos sencillos como estas matrices triangulares son compone-netes esenciales in la expresión tanto de algunos polinomios ortogonales clásicos y comode números combinatorios.

Palabras clave. Identidades combinatorias, Matrices triangulares, Ecuaciones lineales endiferencias, Fórmula de tres términos, Polinomios ortogonales.

s Parcialmente financiado por el Programa Estatal de I+D+i del Ministerio de Economíay Competitividad mediante el proyecto MTM2017-85996-R.

THE CHAMBER COMPLEX FOR THE

LITTLEWOOD-RICHARDSON COEFFICIENTS OF GL4.

EMMANUEL BRIAND, MERCEDES ROSAS, AND STEFAN TRANDAFIR

The Littlewood-Richardson coefficients cνλ,µ are a family of constants of centralimportance in representation theory. They are indexed by triples of integer par-titions. It is known that when the size of the partitions is limited to some fixedinteger N (coefficients associated to GLN ), these coefficients are given by piecewisepolynomial formulas in λ1, . . . λN , µ1, . . . , µN , ν1, . . . , νN−1. More precisely, the do-mains of polynomiality are the big cells (”chambers”) of a subdivision of a cone

in R3N−1 (the ”chamber complex”). In 2005, E. Rassart has calculated explicitlythe chamber complex for N = 3, finding 18 chambers subdividing a cone in R8,and the corresponding polynomial formulas (in this case, linear). Using Rassart’sdescription, E. Briand and M. Rosas recently listed exhaustively all symmetries ofthe chamber complex for N = 3, finding a group of 288 symmetries (much morethat the 24 symmetries known to exist for general N). It is natural to look atwhat happens in the next case, N = 4. With this aim, we have computed (usingSagemath and Singular) the chamber complex for N = 4. This object is large,since it consists in the subdivision of a cone in R11 in 67769 chambers. This compu-tation is based on known combinatorial descriptions of the Littlewood-Richardson

coefficients. For instance, the Littlewood-Richardson coefficient c(26,21,14,11)(16,13,5,2),(17,12,6,1)

counts the triangles

3634 53

29 x3 6516 x1 x2 71

0 26 47 61 72

filled with integers subject to the inequalities a+ b ≥ c+ d in all rhombi:

db c a b c b

d a c a d

of the triangle. (The bottom border entries 0, 26, 47, 61, 72 are the cumulated sumsof (26, 21, 14, 11), that are: 0, 26, 26+21, 26+21+14, 26+21+14+11 and the topborder entries 0, 16, 29, 34, 36, 5365, 71, 72 are the cumulated sums of (16, 13, 5, 2)and (17, 12, 6, 1), that are 0, 16, 16+13, 16+13+5, . . . , 16+13+5+2+17+12+6+1).

E. Briand, Departamento Matematica Aplicada I, Universidad de Sevilla

M. Rosas, Departamento de Algebra, Universidad de Sevilla

S. Trandafir, Simon Fraser University.

E. Briand and M.Rosas are partially supported by MTM2016-75024-P and FEDER, and Juntade Andalucia under grant FQM333.

GENERALIZED CHORDALITY, VERTEX SEPARATORS AND

HYPERBOLICITY ON GRAPHS

A. MARTINEZ-PEREZ

Facultad de Ciencias Sociales, Universidad de Castilla-La ManchaAvda. Real Fbrica de Seda, s/n. 45600 Talavera de la Reina, Toledo, Spain

e-mail: alvaro.martinezperez@uclm.es

Let G be a graph with the usual shortest-path metric. A graph is δ-hyperbolic iffor every geodesic triangle T , any side of T is contained in a δ-neighborhood of theunion of the other two sides. A graph is chordal if every induced cycle has at mostthree edges. A vertex separator set in a graph is a set of vertices that disconnectstwo vertices.

Being hyperbolic is an important property in metric spaces and being chordalis also a deeply studied property on graphs. In [3], the authors prove that chordalgraphs are hyperbolic giving an upper bound for the hyperbolicity constant. In [8],Wu and Zhang extend this result for a generalized version of chordality. They provethat k-chordal graphs are hyperbolic where a graph is k-chordal if every inducedcycle has at most k edges. In [1], the authors define the more general properties ofbeing (k,m)-edge-chordal and (k, k2 )-path-chordal and prove that every (k,m)-edge-

chordal graph is hyperbolic and that every hyperbolic graph is (k, k2 )-path-chordal.In [6], we continue this work and define being ε-densely (k,m)-path-chordal andε-densely k-path-chordal relating these properties with hyperbolicity and giving acharacterization of being hyperbolic in terms of chordality.

G. A. Dirac proved in [4] that a graph is chordal if and only every minimal vertexseparator is complete. See also [5, 7] and [2] and the references therein.

In this work we study the relation between vertex separator sets, the generalizedchordality properties mentioned above and the hyperbolicity of the graph. We alsogive a characterization of being quasi-isometric to a tree in terms of chordality andprove that this condition also characterizes being hyperbolic, when restricted totriangles, and having stable geodesics, when restricted to bigons.

References

[1] Bermudo, S.; Carballosa, W.; Rodrguez, J. M.; Sigarreta, J. M. On the hyperbolicity ofedge-chordal and path-chordal graphs. Filomat 2016, 30 (9), 2599–2607.

[2] Blair, J.; Peyton, B. An introduction to chordal graphs and clique trees, Graph Theory andSparse Matrix Multiplication, IMA Volumes in Mathematics and its Applications, Springer,

Berlin, Germany, 1993, Volume 56, pp. 1–29.[3] Brinkmann, G.; Koolen, J.; Moulton, V. On the hyperbolicity of chordal graphs. Ann. Comb.

2001, 5, 61–69.[4] Dirac, G. A. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg. 1961, 25, 71–76.

[5] Krithika, R.; Mathew, Rogers; Narayanaswamy, N. S., Sadagopan, N. A Dirac-type Char-acterization of k-chordal Graphs. Discrete Mathematics 2013, 313 (24), 2865–2867.

1

2 A. MARTINEZ-PEREZ

[6] Martınez-Perez, A. Chordality properties and hyperbolicity on graphs. Electr. J. Comb.2016, 23 (3), # P3.51.

[7] Sreenivasa Kumar, P.; Veni Madhavan, C.E. Minimal vertex separators of chordal graphs.

Discrete Applied Mathematics 1998, 89, 155–168.[8] Wu, Y.; Zhang, C. Hyperbolicity and chordality of a graph. Electr. J. Comb. 2011, 18, #

P43.

The exact value of 3-color off-diagonalgeneralized Schur numbers S(2, 2, k)

L. Boza, M. P. Revuelta, M. I. SanzDepartamento de Matematica Aplicada I

Universidad de Sevilla

Abstract

For integers a ≤ b, we shall denote [a, b] the integer interval con-sisting of all t ∈ N+ = {1, 2, . . . } such that a ≤ t ≤ b. A function

∆ : [1, N ] −→ {d1, . . . , dr},

where d1, . . . , dr ∈ N+ represent different colors, is a r-coloring of theinterval [1, N ].

Given a r-coloring ∆ and the equation Ek : x1 + · · · + xk = xk+1

in k + 1 variables, then we say that a solution x1, . . . , xk, xk+1 to theequation Ek is monochromatic if and only if ∆(x1) = ∆(x2) = · · · =∆(xk+1).

For integers r and ki, with r ≥ 2 and ki ≥ 2 for i = 1, . . . , r, the r-color off-diagonal generalized Schur number denoted by S(k1, k2, . . . , kr)is defined as the least integer M such that any r-coloring of theinteger interval [1,M ] must admit a j-colored solution to equationEkj : x1 + x2 + . . . + xkj = xkj+1

for some j with 1 ≤ j ≤ r.In this work, we determine the exact value of S(2, 2, k) with k ≥ 2.

Keywords: Schur numbers; sum-free sets; off-diagonal Schur numbers.

MSC 2010: 05C55; 05D10; 05-04; 05A17.

1

Lower bounds and exact values on the weakSchur numbers

L. Boza, M. P. Revuelta, M. I. Sanz

Dpto. de Matematica Aplicada I, Universidad de Sevilla

For integers k, n with k, n ≥ 1 , the n-color weak Schur number WSk(n)is defined as the least integer N , such that for every n-coloring of the integerinterval [1, N ], there exists a monochromatic solution x1, . . . , xk, xk+1 in thatinterval to the equation:

x1 + x2 + · · ·+ xk = xk+1,

with xi = xj, when i = j.In this work, we obtain the exact values of WS6(2) = 166, WS7(2) = 253,

WS3(3) = 94 and WS4(3) = 259 and we show lower bounds on n-color weakSchur number WSk(n) for n = 2, 3, 4.We determine the exact values finding upper bounds which coincide with thegeneral lower bounds translating the problem into a Boolean satisfiabilityproblem, which can be handled by a SAT solver.Keywords: Schur numbers; sum-free sets; weak Schur numbers; weaklysum-free sets; n-coloring.

1

Can labelled vertices make the graph euclidean realizable?

Marıa A. Garrido-Vizuete∗, Alberto Marquez†, and Rafael Robles‡

Dept. Matematica Aplicada I–Universidad de Sevilla

There exists a broad literature on realization of graphs in the euclidean space (euclidean graphs), in particular unit–distance graphs (see, for instance [1, 2]). On one hand, given a graph with positive edge weights, the aim of realizationproblems is to determine whether it is possible to map its vertices to different points in Rd and its edges to segments(without crossings) joining the corresponding points in such a way that the length of each segment is just its weight.On the other hand, it is a natural approach to consider weighted or labelled vertices, as, for example, in the bandwidthproblem or in graceful labelings of graphs; nevertheless, we have not found references about graph realization problemsin the case of edge weights coming from vertex weights or labels. Thus, we address realization problems of graphs withlabelled vertices.

Let G(V,E) be a graph and f : V (G) −→ R be a vertex labeling function. On one hand, a weighting on the edges of

G is defined as f(e) = |f(u)− f(v)|, for every edge e = {u, v} of E. On the other hand, f induces directions to edgeswhether each edge is oriented from its vertex with smallest label to its vertex with greatest label. Thus, f makes G anedge–weighted digraph. Note that f is a proper vertex coloring of G if adjacent vertices have different labels.

It is said that the pair (G, f) is realizable in Rd if G is realizable for edges weighted by f . Obviously, a necessarycondition for realizability is that f is a proper vertex coloring, hence, from now on, we deal with proper vertex colorings.A graph G is realizable in Rd if there exists a vertex labeling function f such that (G, f) is realizable in Rd. Thus, wecan defined the realizability index of G, denoted ri(G), as the minimum dimension d such that G is realizable in Rd,and we say that ri(G) = +∞ if G is not realizable in any Rd.

We define a monotonous path of (G, f) as any directed path of the digraph induced by f , that joins two adjacentvertices.

Theorem 1 Given a graph G and a proper vertex coloring f , the following statements are equivalent:

1. (G, f) is realizable in Rd.

2. There is no pair of adjacent vertices u and v in G such that dG(u, v) = dG−{u,v}(u, v), where distances areconsidered on weighted graphs.

3. There is no monotonous path for (G, f).

The following facts are direct consequences of the second or third statement of Theorem 1.

Corollary 2 If a graph is realizable for some coloring, then it is triangle–free.

Corollary 3 If the chromatic number of a graph G is smaller than its girth then G is realizable.

Theorem 4 It is possible to check in polynomial time whether a pair (G, f) is realizable or not.

If we focus on the family of bipartite graphs (of particular interest since they are unit–distance graphs), the followingresult can be stated:

Theorem 5 The realizability index of any bipartite graph is at most 3. Furthermore, for any d there exists a bipartitegraph G such that (G, f) is not realizable in Rd (where f represents any bicoloring of G).

In this context, we have initiated the study of some questions, among them:

1. If G is realizable find ri(G).

2. Characterize the graphs with low realizability index.

3. Find the realizability index for bipartite graphs.

References

[1] Noga Alon and Andrey Kupavskii. Two notions of unit distance graphs. Journal of Combinatorial Theory, SeriesA, 125:1 – 17, 2014.

[2] Marcus Schaefer. Realizability of graphs and linkages. In Janos Pach, editor, Thirty Essays on Geometric GraphTheory, pages 461–482. Springer New York, New York, NY, 2013.

∗Email: vizuete@us.es. Partially supported by PAI FQM-164 of Junta de Andalucıa.†Email: almar@us.es. Partially supported by MEyC grant BFU2016-74975-P and PAI FQM-164 of Junta de Andalucıa.‡Email: rafarob@us.es. Partially supported by PAI FQM-164 of Junta de Andalucıa.

El problema de Mondrians

Nacho Lopez.(Trabajo conjunto con C. Ansotegui, C. Dalfo y M.A. Fiol.)

Departamento de MatematicaUniversitat de LleidaC/ Jaume II, 69, E-25001 Lleida, Espana

E-mail: nlopez@matematica.udl.es

Resumen. El problema de Mondrian esta basado en las pinturas del artista belga Piet

Mondrian (1872-1944), cuyas famosas obras estan llenas de rectangulos coloreados con

colores primarios. De esta manera se considera el lienzo del artista como un cuadrado

de dimension n ∈ Z+ que debe llenarse completamente usando rectangulos de distintas

dimensiones enteras con los lados paralelos al cuadrado (lienzo) original. Queda prohibido

que los rectangulos se superpongan unos con otros en el lienzo, y una vez usado un

rectangulo de dimensiones enteras a × b, no se puede usar ningun otro con las mismas

dimensiones a × b ni b × a. De esta forma el lienzo queda totalmente recubierto por

rectangulos de distintas dimensiones. Una vez terminada la obra se calcula la diferencia

d entre las areas de los rectangulos de mayor y menor tamano. El problema de Mondrian

consiste en encontrar una teselacion del cuadrado de dimension n con el mınimo d posible,

dibujando de esta forma una obra cuyo lienzo esta lleno de rectangulos cuyas areas son

lo mas parecidas posibles. En esta charla se divulgara un metodo de aproximacion al

problema usando Teorıa de Grafos, ası como nuevos avances sobre este problema.

s Este trabajo ha sido parcialmente financiado por el Ministerio de Ciencia e Innovacionmediante el proyecto MTM2017-86767-R.

The continuous mean distance of a graph

Rodrigo I. SilveiraDept. de Matematiques, Universitat Politecnica de Catalunya (UPC)

Joint work with:Delia Garijo (Universidad de Sevilla), Alberto Marquez (Universidad de Sevilla),

Julian Pfeifle (UPC)

We study the concept of the continuous mean distance of a weighted graph. The meandistance of a connected unweighted graph is often defined as the arithmetic mean of all nonzerodistances between vertices, where the distance between vertices u and v is the length of ashortest path connecting u and v, and the sum is taken over all unordered pairs of verticesin the graph. This graph parameter provides a natural measure of the compactness of thegraph, and has been intensively studied, both for unweighted and weighted graphs.

In this work we study the continuous analog of the mean distance, defined for connectedweighted graphs with non-negative weights satisfying the triangle inequality. Conceptually,the continuous mean distance is the mean of the distances between all pairs of points on anedge of the graph, where a point p on an edge e = uv can be expressed as p = λpv+ (1−λp)ufor some λp ∈ [0, 1].

Despite being a very natural generalization, to the best of our knowledge this concept hasbeen barely studied, the only exception being the preliminary work by Doyle and Graver [1],where the authors define the mean distance of a shape (or type of arrangement) through alimiting process, and compute its value for a few shapes.

In this talk we will introduce the continuous mean distance, some of its computationalaspects, and we will discuss its relation with its well-known discrete counterpart.

References

[1] J. K. Doyle and J. E. Graver. Mean distance for shapes. J. Graph Theory, 6(4):453–471,1982.

1

Optimal divisions of a convex body

Antonio Canete (Universidad de Sevilla)

For a convex body C in Rn and a given division of C into C1, . . . , Cn convex subsets, wecan consider

(1) max{F(C1), . . . , F(Cn)} (respectively, mın{F(C1), . . . , F(Cn)}),where F represents one of these classical geometric functionals: the diameter, the width,the inradius and the circumradius. In some sense, the value defined by (1) provides ameasure of the quality of the division.

In this talk we will study the divisions of C minimizing (respectively, maximizing) thevalue (1). In particular, we will treat the existence of optimal divisions, bounds for thecorresponding optimal values, and algorithms leading to these optimal divisions.

This is part of a joint work with Isabel Fernandez and Alberto Marquez (Universidad deSevilla).

1

GRAFOS REGULARES CON CINTURA 5 Y MÍNIMO ORDEN

E. Abajo Casado (eabajo@us.es). Universidad de Sevilla.

M. Bendala García (mbendala@us.es). Universidad de Sevilla.

En esta charla presentamos los trabajos [1,2,3] realizados durante los últimos años. En ellos

obtenemos cotas inferiores del valor 𝑛(𝑘, 5), mínima cantidad de vértices para la que existe

un grafo 𝑘-regular con cintura 5. En el caso de que este valor sea demostrablemente el

mínimo posible, un grafo con tal orden se denomina (𝑘, 5)-jaula.

Las técnicas que empleamos para la construcción de grafos 𝑘-regulares con cintura 5 se

basan en las utilizadas por Abreu y otros [4], Funk [5] y Jørgensen [6]; junto con un cierto

número de ideas originales.

Se tratan de construcciones explícitas en las que intervienen los conceptos de semiplanos

elípticos, diferencias finitas, … conectando las ramas de álgebra, teoría de grafos y

geometrías finitas.

En algunos casos se construyen familias de grafos, mientras que en otros -especialmente

para pequeños valores de 𝑘- se requieren técnicas más finas para conseguir construir grafos

individuales con menor orden que los previamente existentes.

Los resultados obtenidos mejoran las cotas conocidas para 𝑘 = 13,14 y 𝑘 ≥ 17. Hacemos

notar que las (𝑘, 5)-jaulas se conocen exclusivamente para 𝑘 ≤ 7.

Bibliografía:

[1] E. Abajo, C. Balbuena, G. Araujo-Pardo, M. Bendala. New small regular graphs of girth 5,

Discrete Math. 340(8) (2017) 1878-1888.

[2] E. Abajo, C. Balbuena, M. Bendala, X. Marcote. Improving bounds on the order of regular

graphs of girth 5, Discrete Math. 342(10) (2019) 2900-2910.

[3] E. Abajo, M. Bendala. Amalgamation into elliptic semiplanes and families of (k,5)-graphs.

[4] M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate. Families of small regular graphs of

girth 5, Discrete Math 312(18) (2102) 2832-2842.

[5] M. Funk, Girth 5 Graphs from elliptic semiplanes, Note di Matematica 29 (suppl. 1) (2009)

91-114.

[6] L.K. Jørgensen. Girth 5 graphs from relative difference sets. Discrete Math. 293(1-3)

(2005) 177-184.

k-METRIC DIMENSION IN SOME INFINITE GRAPHS AND ULTRAMETRIC

SPACES

SAMUEL G. CORREGIDOR(1)

Blumental introduced in [1] the metric dimension of a general metric space. This concept has severalapplications. For example, suppose there is a robot navigating on a network. If it need to calculate itslocation, then we can put some landmarks in certain vertices, but it is necessary that each vertex can belocated by the landmarks. Now, suppose there are two positions which are only distinguished by a singlelandmark and communication with this landmark is lost. Then, the robot will not be able to locate itself.Thus, in order to improve the accuracy of the detection or the robustness of the system, it may be interestingto have a family of detectors such that every pair of vertices is distinguished by at least k of them. This isthe concept of the k-metric dimension which appears in [3] and it is a natural extension of metric dimension.See also [4, 5, 6, 7].

Given a simple and connected graph G = (V,E), a set S ⊆ V is called a k-metric generator for G if andonly if any pair of different vertices of G is distinguished by at least k elements of S, i.e., for any pair ofdifferent vertices u, v ∈ V , there exist at least k vertices w1, w2, . . . , wk ∈ S such that

dG(u,wi) 6= dG(v, wi), for every i ∈ {1, . . . , k}.A k-metric basis is a k-metric generator of the minimum cardinality in G. Finally, G is said to be a k-metricdimensional graph if k is the largest integer such that there exists a k-metric basis for G.

In this sense, we study this problem in the context of some infinite graphs [2] and ultrametric space, whichcan be interpreted as the end space of a R-tree.

References

[1] L. M. Blumenthal, Theory and applications of distance geometry, Clarendon Press, Oxford, 1953.

[2] Samuel G. Corregidor, Alvaro Martınez-Perez, A Note on k-metric dimensional graphs, arXiv:1903.11890 (2019).

[3] A. Estrada-Moreno, J. A. Rodrıguez-Velazquez, I. G. Yero, The k-metric dimension of a graph, Applied Mathematics &

Information Sciences 9(6), (2015) 2829–2840.[4] A. Estrada-Moreno, I. G. Yero, J. A. Rodrıguez-Velazquez, The k-metric dimension of graphs: a general approach,

arXiv:1605.06709v2 (2016).[5] A. Estrada-Moreno, I. G. Yero, J. A. Rodrıguez-Velazquez, The k-metric dimension of the lexicographic product of graphs,

Discrete Mathematics 339(7), 1924–1934 (2016).[6] A. Estrada-Moreno, I. G. Yero, J. A. Rodrıguez-Velazquez, The k-Metric Dimension of Corona Product Graphs, Bulletin

of the Malaysian Mathematical Sciences Society 39, 135–156 (2016).

[7] I. G. Yero, A. Estrada-Moreno, J. A. Rodrıguez-Velazquez, On the complexity of computing the k-metric dimension of

graphs, arXiv:1401.0342v2 (2015).

(1) Facultad CC. Matematicas, Universidad Complutense de Madrid

1

Transversals, domination and the LS category on surfacess

Marıa-Jose Chavez, Antonio Quintero, Marıa-Trinidad Villar-Linan

Universidad de Sevilla. E-mail: mjchavez@us.es, quintero@us.es, villar@us.es

The Lusternik-Schnirelmann or LS category of a topological space X, cat(X) = n, isthe least integer n such that there exists an open covering U1, . . . Un+1 of X with each Ui

contractible to a point in the space X. If no such integer exists, cat(X) = ∞. It is knownthat cat(S2) = 2 and for any other closed surface X, cat(X) = 3, [2].

A hypergraph H = (V,E) with vertex finite set V is a family E = {E1, . . . , Em} of subsetsof V (the hyperedges of H) so that E 6= ∅ and V = ∪mi=1Ei. Two vertices are adjacent ifthey lie in a hyperedge. A hypergraph is said to be k-uniform if all its hyperedges are ofsize k. A subset of vertices is said to be a transversal of H if it meets every hyperedge inE. The transversal number τ(H) is the minimum cardinality of a transversal of H. A setof vertices D ⊂ V is dominating in H if each vertex of V − D is adjacent to some vertexin S. The domination number of H, denoted γ(H), is defined to be the cardinality of aminimum dominating set of H. Every triangulation T on any surface (possibly with non-empty boundary) can be considered a 3-uniform hypergraph and has domination numberγ(T ) ≤ |V |/3. See [1, 3].

Considering a triangulation of a surface S as a graph G = (VG, EG), the contractionof an edge of G consists of the identification of its vertices (removing multiple edges if theyappear). An edge is contractible if the resulting graph is still a triangulation of S. The inverseoperation of the edge contraction is called vertex splitting. A triangulation G is irreducibleif it has no contractible edges. It is immediate that for any irreducible triangulation G ofa closed surface S one has cat(S) ≤ τ(G). Moreover, the transversal number may increaseunder splitting vertices. This way the difference τ(G)− cat(S) can be arbitrarily large.

Problem Find a function α of the genus g = g(S) of the closed surface S such thatcat(S) ≤ τ(G) ≤ cat(S)+α(g) for any irreducible triangulation G of S. For all the irreducibletriangulations G of the torus S1, α(g(S1)) = g(S1) and 3 = cat(S1) ≤ τ(G) ≤ cat(S1) +g(S1) = 4.

New parameters for the class of surfaces are introduced in this work. The dominationnumber and the transversal number of a surface S, are defined as

γ(S) = max{γ(G) : G is an irreducible triangulation of S},τ(S) = max{τ(G) : G is an irreducible triangulation of S}, respectively.Examples: γ(S0) = 1; γ(S1) = 2; γ(N1) = 1; γ(N2) = 2.

Theorem 1. For any closed surface S with Euler-Poincare characteristic χ(S) ≤ 1,

γ(G) ≤ 22− 13χ(S)

3

[1] Chavez, M. J., Quintero, A. and Villar-Linan, M. T. Triangulated surfaces with a givendomination number. X Encuentro Andaluz de Matematica Discreta, La Lınea de la Con-cepcion, (Cadiz), 2017.[2] Cornea, O. Lupton, G., Oprea, J. Tanre, D. Lusternik-Schnirelmann Category. Mathe-matical Surveys and Monographs, vol. 103, Amer. Math. Soc. (2003).[3] Furuya, M., and Matsumoto, N. A note on the domination number of triangulations, J.of Graph Theory, (2014), 83-85.

s Partially supported by the Spanish Ministerio de Ciencia e Innovacion via grant MTM2015-65397-Pand Junta de Andalucıa via PAI FQM-189 and PAI FQM-164.

1

Dominacion Romana Triple en Grafos

(1)H. A. Ahangar, (2)M.P. Alvarez, (3)M. Chellali,

(5)S.M. Sheikholeslami and (4)J.C. Valenzuela-Tripodoro

(1) Babol Univ. of Technology (ha.ahangar@nit.ac.ir) (2) Univ. Cadiz (pilar.ruiz@uca.es)(3) Univ. of Blida (m chellali@yahoo.com) (4) Univ. Cadiz (jcarlos.valenzuela@uca.es)

(5) Azarbaijan Univ. (s.m.sheikholeslami@azaruniv.ac.ir)

En 2004, Cockaine et al. introducen el concepto de Dominacion Romana en grafos,inspirado en los trabajos de ReVelle y Rosing , y Stewart relacionados con una estrategiadefensiva del Imperio Romano decretada por Constantino I el Grande. Esta estrategiaestaba basada en dos hechos: el primer de ellos es que cualquier ciudad indefensa, esdecir, en la que no se asentara al menos una legion, debıa poder ser defendida por unaciudad vecina; y el segundo, que ninguna legion podıa acudir en defensa de una ciudadvecina atacada si con ello dejaba desguarnecida su ubicacion de origen. La dominacionRomana es una variante de la dominacion en grafos que ha sido bastante estudiada pormuchos autores y ha recibido una importante atencion en la literatura del area durantela ultima decada. Obviamente, el objetivo era minimizar los costes de asentamiento ymovilizacion de las legiones, garantizando la posibilidad de defensa de todas y cada unade las posiciones del imperio. Para ello, se podıan ubicar hasta dos legiones en cadaasentamiento militar.

Formalmente, una funcion f : V (G) → {0, 1, 2} es una funcion de dominacion Romana

(RDF) en G si cada vertice u ∈ V para el cual f(u) = 0 es adyacente a, al menos, unvertice v, tal que f(v) = 2. El peso de una RDF es el valor f(V (G)) =

∑u∈V (G) f(u). El

numero de dominacion Romana γR(G) es el peso mınimo de una RDF en G. Es evidenteque el conjunto de vertices con etiqueta positiva en una RDF es un conjunto de verticesdominante, por lo que γ(G) ≤ γR(G).

En este trabajo iniciamos el estudio de la dominacion Romana Triple, estableciendovarias cotas para el numero de dominacion Romana Triple en cualquier grafo. En par-ticular, demostramos que si G es un grafo de orden n ≥ 2, γ[3R](G) ≤ 7n

4, caracterizando

aquellos que alcanzan la cota superior. Tambien caracterizamos los grafos conexos G

con γ[3R](G) ∈ {3, 4, 5, 6, 7}. Ademas, se dan valores exactos del numero de dominacionRomana Triple para algunas familias de grafos y se aborda el tema de la complejidadalgorıtmica del problema.

1

DOMINATION ON HYPERBOLIC GRAPHS

ROSALIO REYES(1), JOSE M. RODRIGUEZ(1), JOSE M. SIGARRETA(1), AND MARIA VILLETA

Abstract. If k ≥ 1 and G = (V,E) is a finite connected graph, S ⊆ V is said a distance k-dominating set

if every vertex v ∈ V is within distance k from some vertex of S. The distance k-domination number γkw(G)is the minimum cardinality among all distance k-dominating sets of G. A set S ⊆ V is a total dominating

set if every vertex v ∈ V satisfies δS(v) ≥ 1 and the total domination number, denoted by γt(G), is the

minimum cardinality among all total dominating sets of G. The study of hyperbolic graphs is an interestingtopic since the hyperbolicity of any geodesic metric space is equivalent to the hyperbolicity of a graph related

to it. In this paper we obtain relationships between the hyperbolicity constant δ(G) and some domination

parameters of a graph G. The results in this work are inequalities, such as γkw(G) ≥ 2δ(G)/(2k + 1) andδ(G) ≤ γt(G)/2 + 3.

Keywords: Graphs; domination theory; total domination; Gromov hyperbolicity.

2010 AMS Subject Classification Numbers: 05C69; 05A20; 05C12.

Departamento de Matematicas, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911 Leganes,

Madrid, SpainEmail address: rreyes@math.uc3m.es

Departamento de Matematicas, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911 Leganes,Madrid, Spain

Email address: jomaro@math.uc3m.es

Facultad de Matematicas, Universidad Autonoma de Guerrero, Carlos E. Adame No.54 Col. Garita, 39650Acalpulco Gro., Mexico, and Instituto de Fısica, Benemerita Universidad Autonoma de Puebla, Apartado Postal

J-48, Puebla 72570, MexicoEmail address: josemariasigarretaalmira@hotmail.com

Departamento de Estadıstica e Investigacion Operativa III, Facultad de Estudios Estadısticos,, Universidad

Complutense de Madrid, Av. Puerta de Hierro s/n., 28040 Madrid, SpainEmail address: mvilleta@estad.ucm.es

(1) Supported in part by two grants from Ministerio de Economıa y Competitividad, Agencia Estatal de Investigacion (AEI)and Fondo Europeo de Desarrollo Regional (FEDER) (MTM2016-78227-C2-1-P and MTM2015-69323-REDT), Spain.

1

Wiener index and average eccentricity for some

families of graphs and products

Rocıo M. Casablanca, Peter Dankelmann ∗

This talk is concerned with the strong product G⊠H of two graphs, G and H ,and bounds on the Wiener index, Hosoya polynomial and the average eccentricity inthis product of graphs and other families. We first introduce the distance sequenceof a connected graph. It is defined as the sequence of the distances between allunordered pairs of vertices. We prove that the distance sequence of any connectedgraph of given order and size is dominated by the distance sequence of the so-calledpath-complete graph. This is the main tool to prove general results as, among others,that, if G is a connected graph of given order and size, then the Wiener index ofG ⊠ H , for every fixed connected graph H , and the Hosoya polynomial W (G, x),for every x ∈ R with x ≥ 1, are maximised if G is a path-complete graph. We alsoinvestigate the average eccentricity of G ⊠ H . We show that for fixed H , and G

chosen from among all connected graphs of given order n, it is maximised if G is apath of the same order. We also determine a graph Gn,δ of order n and minimumdegree δ such that for every connected graph G of order n and minimum degree δ,the average eccentricity of G⊠H never exceeds the average eccentricity of Gn,δ ⊠H

by more than 3.

Keywords.

Wiener index; average distance; average eccentricity; Wiener polynomial; Hosoyapolynomial, strong product, distance sequence, distance distribution.

References.

[1] R.M. Casablanca, O. Favaron, M. Kouider, Average distance in the strongproduct of graphs. Util. Math., 94 (2014), 31-48.

[2] I. Gutman, L. Soltes, The range of the Wiener index and its mean isomerdegeneracy. Zeitschrift fur Naturforschung A, 46, no. 10 (1991), 865-868.

[3] L. Lesniak, Eccentric sequences in graphs. Periodica Math. Hungarica, 6, no.4 (1975), 287-293.

[4] L. Soltes, Transmission in graphs: A bound and vertex removing. Math.Slovaca, 41 (1991), 11-16.

∗University of Huelva, Spain (rociomc@uhu.es), University of Johannesburg, South Africa(pdankelmann@uj.ac.za).

1

SOBRE EL CONCEPTO DE JERARQUÍA DE GRAFOS

Francisco J. Cruz, Abraham Del Valle, Juan Núñez-Valdés, Manuel Pena

Departamento de Geometría y Topología. Universidad de Sevilla

francz97@hotmail.com abraham.dvr@gmail.com

jnvaldes@us.es manu.pena21@gmail.com

RESUMEN:

El objetivo principal de esta comunicación es abordar el concepto de jerarquía de grafos

a partir de algunos resultados sobre jerarquía de álgebras. En la actualidad, no hay

muchas referencias en la literatura sobre jerarquía de álgebras y los que hay tratan con

la jerarquía de tipos particulares de álgebras, pero no con la jerarquía de álgebras en

general. Por otra parte, tampoco hay muchas referencias sobre la jerarquía de grafos, a

pesar de que este concepto sea muy interesante, tanto por tener varias aplicaciones como

por facilitar el estudio general de las estructuras algebraicas o discretas sobre las que se

aplica. Así, con el objetivo de generalizar a cualquier tipo de álgebras el concepto de

jerarquía que Tian introdujo en 2008 para un tipo particular de ellas, las álgebras de

evolución [J.P. Tian, Evolution Algebras and their Applications. Lecture Notes in

Mathematics, Vol 1921. Springer-Verlag, Berlín, 2008], los autores han obtenido

últimamente algunos resultados sobre este concepto a partir de los de ocurrencia y

persistencia. Entre estos resultados se encuentra la introducción de este concepto de

jerarquía para cualquier tipo de álgebras y la generalización a las mismas del Teorema

de Descomposición de álgebras de evolución de Tian. Los autores han probado también

que el concepto de jerarquía que han introducido para un álgebra genérica es invariante

bajo isomorfismos de álgebras, lo cual implica la obtención de una condición necesaria

para que dos álgebras genéricas sean isomorfas. Como problema abierto al respecto se

encuentra el procedimiento para encontrar explícitamente la jerarquía de un álgebra

dada, tarea que está siendo abordada actualmente por los autores mediante el

procedimiento de asociarle un cierto tipo de grafo a dicha álgebra, lo que permite a su

vez introducir este concepto de jerarquía para grafos en general. Por tanto, uno de los

fines de esta comunicación es plantear este problema de la jerarquía de grafos como

pendiente y susceptible de ser conocido y tratado por todos los participantes a fin de

fomentar futuras colaboraciones.

Palabras clave: Jerarquía; ocurrencia; persistencia; álgebra de evolución; grafo simple;

subgrafo cerrado completo.

Recent progress on cocyclic matrices

V. Alvarez, J.A. Armario, R.M. Falcon, M.D. Frau, F. Gudiel, M.D. Guemesand A. Osuna

Dpto. Matematica Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s/n41012 Sevilla, Spain.

{valvarez,armario,rafalgan,mdfrau,gudiel,bguemes,aosuna}@us.es

1 Abstract

About twenty-five years ago, Horadam and de Launey introduced the cocyclicdevelopment of designs, from which the notion of cocyclic Hadamard matricesdeveloped over a group (of order a multiple of 4) was straightforwardly derived.Furthermore, they showed that the cocyclic framework could provide a structuralapproach in order to resolve the Hadamard conjecture.

In this talk, we will explain our main progress in this field in the last 10 years,and pose some open problems. Concretely, we will show how we have extendedthis notion in two directions:

1. Spite of the asymptotic existence results supporting the cocyclic Hadamardconjecture and that many families have revealed to be cocyclic, two of themost prolific constructions of Hadamard matrices have failed to be cocyclic.As an attempt to encompass these families in the cocyclic world, we decidedto generalize the theory to cover the wider framework of quasigroups [3, 1].

2. Hadamard matrices can be seen as the solution of the Maximal Determi-nant Problem (MDP) in a particular case. We have explored to apply thecocyclic approach to the other cases of MDP, considering groups G withorders different from a multiple of 4 [2, 4].

References

1. Alvarez, Armario, J.A., V.; Falcon, R.M., Frau, M.D., Gudiel, F., Guemes, M.B.,Osuna, A.: On cocyclic Hadamard matrices over Goethals-Seidel loops. Submitted.

2. Alvarez, V., Armario, J.A., Frau, M.D., and Gudiel, F.: The maximal determinantof cocyclic (−1, 1)-matrices over D2t. Linear Algebra Appl. 436 (2012), 858–873.

3. Alvarez, V., Falcon, R.M., Frau, M.D., Gudiel, F., Guemes, M.B.: CocyclicHadamard matrices over Latin rectangles. Eur. J. Comb. 79 (2019), 74–96.

4. Armario, J. A. and Flannery, D. L.: On quasi-orthogonal cocycles. J. Combin.Des. 26 (2018), no. 8, 401–411.

Complejidad de estados cuanticos de

Fibonacci

Jesus LacalleMat. Aplicada TIC, Universidad Politecnica de Madrid, jlacalle@etsisi.upm.es

Rafael Mantın-CuevasAI & Quantum Computing, Accenture Digital, rafael.martin-cuevas@accenture.com

En [1] se introduce el primero y hasta ahora unico modelo de computacioncuantica discreta. Es un modelo que, manteniendo las propiedades esencialesdel modelo estandar de computacion cuantica, es especialemnte sencillo desde elpunto de vista matematico. Las coordenadas de los estados cuanticos discretos,respecto de la base de computacion, son enteros de Gauss (a+bi tal que a, b ∈ Z),salvo por un factor de normalizacion comun a todas las coordenadas de la forma√

2−k, donde k ∈ N.El modelo tiene propiedades especiales que lo relacionan con muchas areas

de las matematicas. En [1] se demuestra que las mismas puertas cuanticas ele-mentales que generan los estados discretos, a partir de la base de computacion,generan tambien todas las puertas cuanticas discretas de 2 qubits, y se con-jetura que generan asımismo las puertas cuanticas discretas de n qubits paratodo n ≥ 3. Esta conjetura esta estrechamente relacionada con el problema dela compleccion de bases de estados discretos que se estudia en [2] y que planteaun problema muy difıcil de teorıa de numeros con implicaciones muy profundasen otras ramas de las matematicas.

Por otro lado, el modelo de computacion cuantica discreta permite abordar,en un contexto sencillo, otro problema esencial en ciencias de la computacion. Setrata de determinar familias de estados cuanticos discretos cuya construccion re-quiere un numero exponencial de puertas cuanticas elementales. Aunque se sabeque la mayorıa de los estados cuanticos tienen complejidad exponencial, nadieha conseguido demostrar este hecho para ninguno de ellos. Nuestro objetivo eneste trabajo es estudiar la complejidad de los estados cuanticos de Fibonacci.La eleccion de esta familia de estados discretos se debe a que nuestra conjeturaes que van a tener complejidad exponencial.

References

[1] Gatti, L.N., Lacalle, J., A model of discrete quantum computation, Quan-tum Information Processing 17, 192 (2018).

[2] Lacalle, J., Gatti, L.N., Discrete quantum computation and Lagrange’sfour-squared theorem, Quantum Information Processing 19, 34 (2020).

1

Grafos prohibidos y logica cuantica

Jose Ra. Portillo

Universidad de Sevilla, Espana

Se definen los siguientes tipos de conjuntos de proposiciones logicas (re-presentadas en teorıa cuantica por operadores de proyeccion de rango 1 opor vectores de Cn): (i) conjunto verdad-implica-falso (true-implies-false set)(tifs), (ii) conjunto verdad-implica-verdad (true-implies-true set) (tits) y(iii) conjunto no separable (nonseparating set) (nss) como los conjuntos enlo que cuando se asume no contextualidad en el resultado (i) si la proposicionA ∈ S es verdad, entonces una proposicion no exclusiva B ∈ S debe ser falsa,(ii) si la proposicion A ∈ S es verdad, entonces una proposicion C ∈ S debeser verdad y (iii) si la proposicion A ∈ S es verdad, entonces una proposicionC ∈ S debe ser verdad y viceversa. Es decir, A y C no pueden ser separadaspor logicas clasicas. Estos conjuntos tifs, tits y nss se denominan crıti-cos si ningun subconjunto suyo es un tifs, tits o nss, respectivamente. Untifs/tits/nss puede ser representado mediante un grafo en el cual d-cliquesrepresentan contextos completos, los vertices representan vectores de Cn ydos vertices seran adyacentes si y solo si los vectores son perpendiculares.

En este trabajo utilizamos la teorıa de grafos para encontrar tifs, titsy nss crıticos en dimension 3. Para ello estudiamos los grafos realizables,(i.e.,correspondientes a un conjunto de vectores de S2 que sea representacionortonormal fiel del grafo) mostrando nuevos ejemplos de grafos prohibidos.

El proceso para encontrar estos conjuntos crıticos es el siguiente: en primerlugar, generamos todos los grafos no isomorfos de n vertice biconexos, libresde C4 y que contengan al menos dos C3 con n = 8, . . . , 17. Para cada grafoobtenido en el paso anterior, consideramos todos los pares de vertices noadyacentes y buscamos las posibles asignaciones de verdad correspondientes.Finalmente, comprobamos si los grafos obtenidos son realizables.

Se han encontrado nuevos conjuntos tifs y tits, ası como un metodoconstructivo de grafos crıticos tifs a partir de grafos crıticos conocidos. Sededuce que existen grafos crıticos tifs y tits para cualquier numero de verti-ces suficientemente alto. Tambien se proponen nuevos candidatos a conjuntonss mınimo.

Convexidad en grafos: una perspectiva personal

José Cáceres

Universidad de Almería

El propósito de esta charla es mostrar un panorama general de los trabajos relacionados

con convexidad en grafos de los que he sido autor. Éste es un campo extraordinariamente

fértil con conexiones computacionales, con la teoría de dominación, con reconstrucción

de grafos, con antimatroides, y otros. Al mismo tiempo se intentará dar una idea del estado

del arte actual y posibles líneas de trabajo futuro.

LA INVERSA DE GRUPO DE ALGUNAS MATRICESCIRCULANTES

A.M. ENCINAS Y M.J. JIMÉNEZ

Las matrices circulantes tienen un variado rango de aplicación en procesado deseñal, tratamiento de imágenes, diseño de imágenes digitales, estimación estadísticao teoría de códigos de corrección de errores. En los últimos año se han publicadodiversos documentos sobre matrices circulantes que tratan de dar expresiones efec-tivas de su determinante, sus valores propios y de la inversa de estas matrices.

En un trabajo anterior, los autores presentaron las condiciones necesarias ysuficientes para la invertibilidad de algunas matrices circulantes que dependende tres parámetros, a saber, las matrices circulantes de tipo Circ(a, b, c, . . . , c) yCirc(a, b, c, . . . , c, b), y además obtuvimos una fórmula cerrada para su inversa. Lastécnicas que utilizamos provienen de la solución de problemas de contorno asocia-dos a ecuaciones en diferencias de segundo orden, y nos permitieron reducir el costocomputacional de evaluar la inversa.

En este trabajo completamos el análisis de las matrices circulantes mencionadasdependiendo de tres parámetros, considerando el caso singular. Específicamente,calculamos su inversa de grupo usando las mismas técnicas que en el caso no singu-lar; es decir, resolviendo problemas de contorno para ecuaciones en diferencias desegundo orden.

Departamento de Matemàtiques, EEBE-UPC, Barcelona, SpainE-mail address: {andres.marcos.encinas, maria.jose.jimenez}@upc.edu

1

La constante de Kemeny de caminos aleatorios con barreras reflejantesA. Carmona and M. Mitjana

Universitat Politecnica de Catalunya, Barcelona, Spain.E–mail: angeles.carmona@upc.edu

The computation of the Kemeny’s constant is a classical problem in the theory ofMarkov chains and has multiple applications. The different ways to afford the problemgo from Linear Algebra to discrete Potential Theory. The mean first passage timeis closely related to other well–known metrics for graphs and Markov chains. First,the Kirchhoff index, also known as the effective graph resistance, is a related metricquantifying the distance between pairs of vertices in an electric network. The relation-ship between electrical networks and random walks on graphs is well–known. For anarbitrary graph, the Kirchhoff index and the Kemeny constant can be calculated fromthe eigenvalues of the conductance matrix and the transition matrix, respectively. Itis known that there exists an eigenvector called stationary distribution, which giveslong-term information of the chain. The short term behavior, can be studied troughthe so-called mean first passage time from state i to state j; that will be denoted bymi,j. It is the expected number of steps to reach vertex j when starting form vertexi. The mean first passage time matrix can be obtained as the group inverse of theprobabilistic Laplacian and some more known date. It is known that the expectedtime to get any randomly chosen vertex from vertex i is constant and independent ofthe starting vertex. The common value is called Kemeny constant.Kemeny’s constant can also be written in terms of the eigenvalues for the ProbabilisticLaplacian and can be related to Poisson problems state in terms of this Laplacianoperator.Our group has been working during the last decades in this topic, by considering alsoDirichlet problems and Neumann problems for more general operators.When a Markov chain has absorbing states; that is, once the chain enters an absorb-ing state it can not left (Drunk’s walk), the mean first passage time is related withthe inverse of some submatrix of the Laplacian, and corresponds to solving Dirichletproblems where the boundary nodes are the absorbing states.If we want to consider a more safe walk for the Drunk, we need to introduce reflectingbarriers. Meaning that if the chain enters the bar with probability one you leave thebar, which represents a reflecting barrier. In terms of operator, this is a Neumannproblem; and we investigate which matrix give the mean first passage time. We canalso compute M for different families of structured networks; like wheels, paths, fansor ladders.

Particiones en un submonoide de un grupo abelianos

Miguel V. Carriegos

Departamento de Matematicas, Universidad de Leon.

E-mail: miguel.carriegos@unileon.es

El resultado clasico de Kalman y Brunovsky (1971) caracteriza el conjuntode sistemas de control lineales modulo acciones de realimentacion con el conjuntode particiones de enteros en N. Posteriormente (2012) se prueba que el mismoresultado es valido para sistemas lineales regulares sobre un anillo conmutativoA. Ahora el conjunto de representantes viene dado por el conjunto de particionesen el monoide abeliano P(A) de A-modulos proyectivos finitamente generados.

Los primeros resultados (2019) se obtienen para el caso que P(A) ∼= N×H conH un grupo abeliano finito. El conjunto de particiones se describe resolviendo unaecuacion diofantica e introduciendo y estudiando un tipo especial de particionesde los enteros.

Resulta tambien interesante estudiar las particiones de elementos del sub-monoide imagen de P(A) en el grupo abeliano K0(A). Ası, el problema se trans-forma en: dado G = (G,+, 0) un grupo abeliano y M = (M,+, 0) un submonoidede G, encontrar las particiones de m ∈M como suma de elementos de M .

Notamos que los submonoides de G estan en correspondencia biyectiva conlos preordenes de G. Ası fijado un grupo abeliano preordenado (G,+, 0,≺) y elsubmonoide G+ = {g : 0 ≺ g}, se estudian las particiones de elementos de G+.

s Grupo CAFE. Universidad de Leon

Numeros de Schur debiles no diagonales

L. Boza, M. P. Revuelta, M. I. Sanz

Departamento de Matematica Aplicada I, Universidad de Sevilla.

Denotemos [a, b] como el conjunto de enteros n tales que a ≤ n ≤ b. Para enteros k, r ≥ 2,sea Ek la ecuacion

∑ki=1 xi = xk+1 con xi < xi+1 para 1 ≤ i ≤ k − 1 y sean a1, . . . , ar ∈ N

con 2 ≤ a1 ≤ a2 . . . ≤ ar. Se define el numero de Schur debil WS(a1, . . . , ar) como el menorentero n tal que para toda r-coloracion de [1, n] existe s con 1 ≤ s ≤ r de manera que hayuna solucion en el color s-esimo de la ecuacion Eas . Si ar = a1 se dice que el numero deSchur debil es diagonal y se denota como WSr(a1).

En este trabajo se presentan los siguientes 31 valores no diagonales exactos, de los que17 corresponden al caso r = 2, 13 al r = 3 y 1 al r = 4:

WS(2, 3) = 16, WS(2, 4) = 23, WS(2, 5) = 37, WS(2, 6) = 53, WS(2, 7) = 71,WS(2, 8) = 93, WS(2, 9) = 119, WS(3, 4) = 39, WS(3, 5) = 49, WS(3, 6) = 66,WS(3, 7) = 87, WS(3, 8) = 111, WS(4, 5) = 76, WS(4, 6) = 93, WS(4, 7) = 118,WS(5, 6) = 130, WS(5, 7) = 156.

WS(2, 2, 3) = 42, WS(2, 2, 4) = 64, WS(2, 2, 5) = 102, WS(2, 2, 6) = 148, WS(2, 3, 3) =64, WS(2, 3, 4) = 105, WS(2, 3, 5) = 138, WS(2, 3, 6) = 194, WS(2, 4, 4) = 151,WS(2, 4, 5) = 204, WS(3, 3, 4) = 127, WS(3, 3, 5) = 188, WS(3, 4, 4) = 189.

WS(2, 2, 2, 3) = 117.

Ademas se prueban varias cotas inferiores generales para el caso r = 2, que coinciden conlos valores exactos para valores pequenos de a1 y a2.

Pascal automata and matroids

Jose Caceres∗ Marıa A. Garrido-Vizuete† Alberto Marquez‡

Let G be a finite set with a binary operator ∗, called product, such that (G, ∗) forms an abelian group, and let hdenote its exponent. Given N and s two natural numbers such that 2 ≤ s ≤ N , we define the following one–dimensionalfinite cellular automaton, or CA (see [3]): The initial cell set (first row which corresponds with time t = 0 ) is an orderedlinear array of N cells which are denoted by (0, i), 1 ≤ i ≤ N . The evolution of the CA throughout the time gives riseto linear arrays (rows) of different length, whose cells are designed as (t, i), with (t, i) ∈ N2, where t refers to the timeperiod and i is the cell position in the array. The state set of the CA is the group G and, in general, gti denotes thestate of the i-th cell of the row obtained at time t. The neighborhood of the cell (t, i) consists of s cells belonging tothe (t− 1)-th row, according to the following CA’s local evolution rule:

gti = gt−1i ∗ gt−1i+1 ∗ . . . ∗ gt−1i+s−1. (1)

Note that this rule involves s+ 1 elements of G: s states of adjacent cells in the same row and another state of a cell inthe next row or time period, such that this state is the product of those ones. The underlying abelian group structure ofG implies that knowledge of any s elements of this configuration, called a cell basic configuration, uniquely determinesthe state of the remaining cell.

Then, the orbit of the CA, starting from the states of the N initial cells, is a two–dimensional arrangement of elementsgti of G, ordered in rows and columns, called a triangle, and it is straightforward to see that it is uniquely determinedby the values of N and s, and the states of the cells (0, i), with 1 ≤ i ≤ N .

The set made up of all triangles is denoted by ∇N (G, s). Then, ∇N (G, s) should be seen under two perspectives:On one hand, it collects all triangles according to the above definition. On the other hand, ∇N (G, s) can be consideredas an ordered set of empty cells, which are connected by the cell basic configuration. We would like to stress that it ispossible to unambiguously identify triangles of ∇N (G, s) from the states of other cells different to the collection of Nentries of the first row, following the above–mentioned property of cell basic configurations, stated in Equation 1. Inparticular, we are interesting in characterizing the cell sets whose states determine an unique triangle of ∇N (G, s).

A cell c is generated by a cell subset A of ∇N (G, s), or A generates c, if the states of the cells of A uniquely determinethe state of c applying the CA’s local evolution rule of cell basic configurations.

A cell subset A of ∇N (G, s) is independent if, for any assignment of states to its cells, there exists at least a triangleof ∇N (G, s) containing these states for the cells of A. On the contrary, a cell subset A of ∇N (G, s) is dependent if thereexists an assignment of states to its cells for which there is no triangle of ∇N (G, s) including these states for the cellsof A.

It is straightforward to check that none cell of an independent set can be generated by its remaining cells. Conversely,any cell of a dependent set is generated by its remaining cells.

Given an independent set A of ∇N (G, s), let GA be the set of cells generated by A. Then, a cell independent set A of∇N (G, s) is a generating set of ∇N (G, s) if ∇N (G, s) = A ∪ GA. Thus, one of our aims in this paper is to characterizeall generating sets of ∇N (G, s).

LetM(∇N (G, s)) be the ordered pair (∇N (G, s), I) where I is the collection of independent sets of ∇N (G, s). Thenit can be proved that M(∇N (G, s)) is a matroid that we call Pascal matroid. Depending on the values of parameterss,N and h, the obtained matroids have a great variety of structures, ranging from graphic to ternary [2].

The main result of this work is that operating with the elements of the matroid, it is simple to check for any subsetof cells of ∇N (G, s) whether or not they are independent, in the sense that one of them can be generated from theothers. Some other authors [1] have partially solved this problem by using a much more complicated construction.

References

[1] A. Barbe, F. von Haeseler, The Pascal matroid as a home for generating sets of cellular automata configurationsdefined by quasigroups. Theor. Comput. Sci. 325 (2004) 171–214.

[2] J.G. Oxley, Matroid Theory. Oxford Science Publications, The Clarendon Press, Oxford University Press, NewYork, 1992.

[3] Wolfram, S. A New Kind of Science. Champaign, IL, Wolfram Media, 2002.

∗Dept. Matematicas. Universidad de Almerıa. Email: jcaceres@ual.es.†Dept. Matematica Aplicada I. Universidad de Sevilla. Email: vizuete@us.es.‡Dept. Matematica Aplicada I. Universidad de Sevilla. Email: almar@us.es.

1

Sobre el problema del 3-coloreado de un grafo

utilizando sistemas de ecuaciones polinomiales

Marıa Isabel Hartillo HermosoJose Manuel Jimenez Cobano

Jose Marıa Ucha Enrıquez

Dpto. Matematica Aplicada IInstituto Matematicas Antonio de Castro Brzezicki

Universidad de Sevilla

Resumen

La propiedad de ser 3-coloreable de un grafo G es equivalente a que elsistema

x3i − 1 = 0 ∀i ∈ V (G), x2

i + xixj + x2j = 0 ∀(i, j) ∈ E(G) (?)

tenga alguna solucion1 (compleja, aunque tambien puede estudiarse enF2). Este camino para buscar posibles 3-coloreados no es manejable paragrafos de gran tamano usando bases de Grobner.

Sin embargo, para certificar que un cierto grafo no es 3-coloreablepuede tomarse un atajo: basta con demostrar que 1 esta en el ideal de lospolinomios que definen el sistema (?) y para eso se puede usar AlgebraLineal (existe incluso un software especializado en esta tarea, NulLA).

Problema: ¿Serıa posible demostrar el caracter NP-completo del pro-blema del 3-coloreado de grafos mostrando una familia que necesitarapara obtener los certificados de no 3-coloreabilidad polinomios de gradoadecuado?

Palabras clave— 3-coloreado, bases de Grobner, Nullstellenstaz

1. J.A. De Loera, J. Lee, P.N. Malkin, and S. Margulies. Hilbert’s Nullstellensatz and an al-gorithm for proving combinatorial infeasibility. Proceedings of the Twenty-first InternationalSymposium on Symbolic and Algebraic Computation (ISSAC 2008).

1

VERTEX-MONOCHROMATIC CONNECTIVITY OFSTRONG DIGRAPHS

Mucuy-kak Guevara

Facultad de Ciencias

Universidad Nacional Autonoma de Mexico.

e-mail: mucuy-kak.guevara@ciencias.unam.mxCoautores: Diego Gonzalez-Moreno y Juan Jose Montellano

Caro and Yuster en 2011 introducen el concepto de conexidad monocromaticade una grafica coloreada en aristas. Una grafica coloreada en aristas G esmonocromaticamente conexa si existe una trayectoria monocromatica entrecualesquiera dos vertices de G. El estudio de la conexidad monocromaticasurge despues de estudiarse la conexidad arcorıris, en la cual trayectoriasarcoıris son consideradas. La conexidad monocromatica tambien se puedeextender a graficas orientadas ( [?]): una digrafica coloreada en flechas,D, es monocromaticamente conexa (SMC-coloreada) si para cada parejau, v ∈ V (D), existe una (u, v)- y una (v, u)-trayectoria monocromatica di-rigida. El numero de conexidad monocromatica de una digrafica fuertementeconexa D, smc(D), es el maximo numero de colores usados en una SMC-coloracion de D.

Cai, Li and Wu en 2017 definieron la version en vertices del conceptode conexidad monocromatica. Una trayectoria en una grafica coloreada envertices es vertex-monocromatica si sus vertices internos tienen el mismocolor. Una grafica coloreada en vertices es vertex-monocromatica conexa(VMC-coloreada) si existe una trayectoria vertex-monocromatica que unecualesquiera dos vertices. De nuevo podemos extender este concepto adigraficas. Una trayectoria dirigida en una grafica coloreada en vertices esvertex-monocromatica si sus vertices internos tienen el mismo color. Unadigrafica coloreada en vertices es vertex-monocromatica fuertemente conexa(SVMC-coloreada) si para cada pareja u, v de vertices en D existe una (u, v)-y una (v, u)-trayectoria dirigida vertex-monocromatica en D. El numero deconexidad vertex-monocromatico de una digrafica fuerte D, smcv(D), es elnumero maximo de colores usados en una coloracion de D para que resultefuertemente conexa vertex-monocromatica.

En este trabajo presentaremos cotas para smcv(D), nos enfocaremos enla familia de digraficas de lıneas y daremos resultados para el numero deconexidad vertex-monocromatica de torneos fuertemente conexos.

1

Familias consistentes y coloración total de grafos.

Abel R. García Lozano 1 2. Sérgio R. Pereira de Mattos1.Angelo Santos Siqueira . Priscila Cardoso Petito2.Marcele Câmara de Souza2. Poméia Genaio 3.

Definición 1 Considere un conjunto finito X y una familia {A1, . . . , An} de sub-conjuntos de X (no necesariamente distintos). Llamamos al conjunto {x1, ..., xn}un sistema de representantes distintos de {A1, . . . , An}, si para todos i, j ∈{1, . . . n}, xi ∈ Ai e xi 6= xj siempre que i 6= j, .

en 1935 Philip Hall, demostró lo seguinte:

Teorema 1 Sean {A1, . . . , An} una familia de subconjuntos de un conjunto finitoX , entonces existe un sistema de representantes distintos si y solamente si la uniónde cada m conjuntos de la familia contiene al menos m elementos, para todo1 ≤ m ≤ n.

Definición 2 Decimos que una familia {A1, . . . , An} de subconjuntos de un con-junto finito X es consistente si la unión de cada m conjuntos de la familia contieneal menos m+ 1 elementos, para 1 ≤ m ≤ n.

Definición 3 Dado G(V,E) un grafo, C = {c1, c2, c3, . . . , cp}, p ∈ N un con-junto de colores. Una aplicación f : V → C es una coloración de vértices conholgura 2 de G, si para todo v ∈ V :

• |c(N(v))| = d(v) si d(v) < 2;

• |c(N(v))| ≥ 2 si d(v) ≥ 2.

Donde |c(N(v))| es la cardinalidad del conjunto de colores usados en la vecindadde v

Presentamos una heurística eficiente para completar la coloración de un grafo Gcoloreado con holgura 2 para una coloración total, asociando a cada vértice unafamilia consistente de subconjuntos del conjunto de colores.

1Universidade do Grande Rio. UNIGRANRIO2Universidade do Estado de Rio de Janeiro. UERJ-DMAT (FFP).3Universidade Salgado de Oliveira. UNIVERSO

1

Un modelo para el aprendizaje de la Teorıa de Grafos

Antonio GonzalezUniversidad de Sevilla

(Trabajo conjunto con J.M. Gavilan Izquierdo y M.L. Puertas)

En esta charla, de corte poco frecuente en estos encuentros, presentareel trabajo que estoy desarrollando actualmente con investigadores del areade Didactica de la Matematica y del area de Matematica Aplicada. Nuestrotrabajo tiene como objetivo modelizar el proceso de aprendizaje de la Teorıade Grafos, para lo cual hemos adoptado la perspectiva de un modelo clasicoen el estudio del aprendizaje de la Geometrıa: el modelo de van Hiele [1]. Estemodelo establece cuatro niveles de razonamiento para los estudiantes a lahora de tratar con problemas geometricos: nivel 1 (reconocimiento visual),nivel 2 (analisis), nivel 3 (clasificacion) y nivel 4 (deduccion formal). Laidea de ampliar este modelo a la Teorıa de Grafos surge de la similitudque comparten grafos y figuras geometricas cuando son representados en elplano, pues los grafos se presentan frecuentemente como puntos unidos porlıneas (representacion pictorica), recordandonos ası a los vertices y los ladosde las figuras geometricas.

Los resultados que hemos obtenido hasta ahora son una propuesta teori-ca, articulada a traves de los procesos de razonamiento geometrico plantea-dos por Gutierrez y Jaime [2], y un instrumento para la recogida inicial dedatos basado en un cuestionario de preguntas de respuesta abierta disenadomediante dichos procesos. Estos resultados nos permitiran realizar experi-mentaciones que aporten la base empırica que, o bien valide el planteamientoteorico inicial que hemos formulado, o bien nos ayude a realizar correccionesen el mismo. Una vez caracterizado el proceso de aprendizaje de la Teorıade Grafos, podremos abordar el correspondiente proceso de ensenanza queaporte la base para elaborar trayectorias de aprendizaje eficientes para quelos estudiantes progresen de un nivel a otro.

Referencias

[1] A. Gutierrez y A. Jaime. On the assessment of the Van Hiele levels ofreasoning. Focus on Learning Problems in Mathematics, 20 (2/3): 27–46,1998.

[2] P.M. Van Hiele. Structure and Insight. A theory of mathematics educa-tion. Academic Press: Londres, 1986.

Charla XI Encuentro Andaluz de MatematicaDepartamento Matematica Aplicada I. Universidad de SevillaTema: Analisis Topologico de Datos: Aplicacion en Reconocimiento de EmocionesAutores: Guillermo Aguirre Carrazana - Rocıo Gonzalez Dıaz - Eduardo Paluzo Hidalgo

Resumen de la Charla

Reconocimiento de Emociones, proceso para detectar emociones humanas a partir de expresionesfaciales. Los humanos interactuan entre sı principalmente a traves del habla, pero tambien atraves de gestos corporales para enfatizar una cierta parte de la conversacion y exhiben emo-ciones. Comprender el estado emocional se ha convertido en un campo de investigacion queinvolucra a cientıficos especializados en diferentes areas, tales como inteligencia artificial, visionpor computadora, psicologıa, fisiologıa, entre otros. La necesidad de algoritmos eficientes paraentender las emociones humanas se hace inminente.

Nuestro principal objetivo es desarrollar un enfoque para el reconocimiento y clasificacion quecombine caracterısticas de referencia que ofrecen los videos y audios en sus respectivos espaciosde representacion. Nuestro desafıo es el empleo de herramientas del Analisis Topologico deDatos para obtener un enfoque diferente y competitivo en el area.

Resultados y trabajo futuro en Reconocimiento de Emociones

De manera introductoria necesitamos establecer las siguientes cuestiones para enfocar la inves-tigacion: ¿Que senales en el rostro y la voz revelan estados emocionales?. ¿Como podemosutilizar estas senales para entrenar y reconocer las emociones de audio-video?. ¿Utilizar unafusion audio-video permite obtener mayor eficiencia en el reconocimiento que utilizarlas de man-era individual?.

El grupo de investigacion tiene una amplia experiencia dentro del campo del Analisis Topologicode Datos. Dentro del area de reconocimiento de emociones se ha desarrollado un primer enfoqueutilizando solo senales de voz, bajo el tıtulo: “Towards Emotion Recognition: A Persistent En-tropy Application”. Un modelo basado en topologıa es aplicado para obtener un valor realde cada senal de audio, donde estos datos fueron utilizados como entrada de una maquina desoporte vectorial para clasificar las senales en 8 emociones diferentes.

Con el objetivo de enriquecer el analisis del conjunto de datos y disfrutar de las ventajas de lastecnicas topologicas utilizamos los complejos simpliciales como representacion topologica paralas informaciones audio-video y obtener resumenes topologicos con rasgos caracterısticos paracada informacion. Luego, una evaluacion de los dos esquemas por separado y encontrar unacombinacion optima desde el puntos de vista topologico de los dos tipos de informaciones.

Resultados esperados

En la literatura se conoce que la combinacion de caracterısticas visuales y audio permiten desar-rollar mejores predicciones que utilizarlas de forma separada. Nuestro proyecto espera respaldardicha conclusion mediante las herramientas que ofrece el Analisis Topologico de Datos. Obtenereficientes predictores para el reconocimiento de emociones por voz e imagenes faciales. Luego,ser capaces de combinar ambos predictores y obtener mejores resultados en la clasificacion.

1

Topological data analysis for the study of self-organization of cellsin a biological tissue?

N. Atienza1, L.M. Escudero2,3, M.J. Jimenez1, and M. Soriano-Trigueros1

1 Departamento Matematica Aplicada I, Universidad de Sevilla,{natienza,majiro,msoriano4}@us.es

2 Departamento de Biologia Celular, Universidad de Sevilla3 Instituto de Biomedicina de Sevilla (IBiS), Hospital Univ. Virgen del Rocio, CSIC, Universidad de Sevilla,

lmescudero-ibis@us.es

1 Extended abstract

In this communication, we want to present our ongoing work on topological analysis of images of segmentedcells in a biological tissue.

Topological Data Analysis (TDA) studies the shape of data from a topological viewpoint, having persistenthomology [3, 6] as its main tool. Persistent homology studies the evolution of homology classes and theirlife-times (persistence) in an increasing nested sequence of spaces (that is called a filtration). The outputof persistent homology computation can be codified under the form of a set of intervals (barcode) encodingthe birth and death times of each homology class {(xi, yi)}ni=1 arising in the increasing sequence of spaces.Persistent entropy is a simple parameter that can be calculated from the lengths of these intervals and canbe statistically studied later. The concept first arose in [2] and can be described as an adaptation of Shannonentropy to this context: E = −

∑ni=1

`iL log( `i

L ), where `i = yi − xi and the total length L = `1 + . . . + `n.In [1], the authors proved that persistent entropy is robust to noise.Now, we are exploring the power of persistent entropy in a biological context to test if it is able to detect

topological differences in cell arrangements in images of biological tissues. In [4], we first applied persistenthomology, looking for other organizational traits that could improve the characterization of epithelia. Someinitial experiments were described, working on two types of tissues: chick neuroepithelium (cNT) from chickenembryos and wing imaginal disc in the prepupal stage (dWP) from Drosophila. However, it is importat also tocompare the latter (dWP) with middle third instar wing discs (dWL), which are two proliferative stages sepa-rated by 24h development (and hence, with very similar organization). We have already got initial good resultsin the study of the discriminative ability of persistent entropy, discovering statistically significant differencesbetween images of the three tissues. These results may open a door to the inclusion of persistent entropy as animportant parameter to be taken into account in analysis tools like [5].

References

1. Atienza, N., Gonzalez-Diaz, R., Soriano-Trigueros, M.: On the stability of persistent entropy and new summaryfunctions for TDA. Preprint: https://arxiv.org/abs/1803.08304

2. Chintakunta, H., Gentimis, T., Gonzalez-Diaz, R., Jimenez, M.J., Krim, H.: An entropy-based persistence barcod.Pattern Recognition 48 (2) 391–401 (2015)

3. Edelsbrunner H., Letscher D., Zomorodian A.: Topological persistence and simplification. In: FOCS ’00, IEEEComputer Society, 454–463 (2000)

4. Jimenez, M.J., Rucco, M., Vicente-Munuera, P., Gomez-Galvez, P., Escudero, L.M.: Topological Data Analysis forSelf-organization of Biological Tissues. In: Brimkov V., Barneva R. (eds) Combinatorial Image Analysis. IWCIA2017. Lecture Notes in Computer Science, 10256, 229–242 (2017)

5. Vicente-Munuera, P., Gomez-Galvez, P., Tagua, A., Letran, M., Mao, Y., Escudero, L.M.: EpiGraph: an open-sourceplatform to quantify epithelial organization. BioRxiv 217521; doi: https://doi.org/10.1101/217521

6. Zomorodian A., Carlsson G.: Computing persistent homology. Discrete and Computational Geometry 33 (2), 249-274 (2005)

? Author names listed in alphabetical order.

Estructura modular de las enzimas como punto de partidapara la sıntesis de nuevos biocatalizadores

N. Birkelanda, A. Dianez Martınezb∗, A. Garcıa Moyanoa,

P. Garcıa Vazquezb, M.A. Gonzalez del Vallec y J.M. Gonzalez Graud

aDepartment of Biological Sciences, University of Bergenb Departamento de Matematica Aplicada I, Universidad de Sevillac Bioavan S.L.d Instituto de Recursos Naturales y Agrobiologıa de Sevilla

Resumen.La busqueda de procesos biologicos mas limpios y verdes en los procesos de produccion quımica

impulsa el interes de profundizar en el conocimiento de las enzimas como biocatalizadores naturales.Las enzimas son proteınas y, por tanto, tienen una estructura tridimensional. Inicialmente, pode-

mos pensar una enzima como una secuencia lineal de aminoacidos que interactuan entre sı de formaconsecutiva, esta serıa su estructura primaria. Pero lo realmente interesante son las interacciones,denominadas de cadena lateral, que se producen entre aminoacidos no consecutivos. Estas interac-ciones son las que conducen a su estructura tridimensional y a su funcionalidad. De hecho, una mismasecuencia primaria puede dar lugar, en funcion de sus interacciones de cadena lateral, a enzimas condistinta funcionalidad.

Las enzimas son biocatalizadores eficientes pero muy especıficos, reaccionan con sustratos con-cretos. Cada enzima es apropiada para catalizar un numero limitado de transformaciones. De ahıel interes que suscita analizar lo que supondrıa introducir pequenos cambios en la secuencia de unaenzima, estos cambios podrıan dar como resultado nuevas funcionalidades de potencial interes enbiotecnologıa.

En la naturaleza podemos encontrar microorganismos que se han adaptado a vivir en condicionesextremas: altas temperaturas (termofilos), bajas temperaturas (psicrofilos), altas concentraciones desal (halofilos). . . Las enzimas de estos microorganismos no cambian significativamente en su com-posicion de aminoacidos de otros organismos, sin embargo son capaces de soportar condiciones ex-tremas. Por tanto, resulta de especial interes analizar tales enzimas con el objetivo de disenar yproducir enzimas con la especificidad deseada y capaces de funcionar en las condiciones requeridas.Pero las enzimas son redes complejas en las que se producen una gran cantidad de interacciones, loque dificulta su analisis.

En este trabajo se presenta una metodologıa para la modelizacion de la enzima basada en ladeteccion de comunidades y en el analisis de la posicion de los centros activos. Estas comunidadesservirıan como punto de partida para la experimentacion en laboratorio de la busqueda de nuevosbiocatalizadores.

∗anadianez@us.es

Escutoides: pasado, presente y futuro (?)

S. Ambari (1), J. Buceta (1), L.M. Escudero (2), P. Gomez-Galvez (2), C.I. Grima (2),A. Marquez (2), R. Robles (2), A. Tagua (2), and P. Vicente-Munuera (2)

(1) Lehigh University (2) Universidad de Sevilla

En el artıculo [1] algunos de los autores de este trabajo describieron la figura del Es-cutoide y demostraron que la forma que adoptan las celulas de los tejidos epitelialeses justamente la de esa figura (en contra de lo que aparecıan en todas las referenciasde biologıa celular en los que siempre eran representadas dichas celulas como prismas opiramides truncadas).

Para llegar a la descripcion del escutoide fue necesario el trabajo conjunto de un equipomultidisciplinar de biologos, informaticos, fısicos y matematicos. Presentamos en estacomunicacion los aspectos mas matematicos del trabajo y anunciamos algunos de losresultados recientes que son una continuacion de los aparecidos en [1].

A modo de resumen, mencionemos aquı las herramientas matematicas basicas usadas:para la descripcion del escutoide se requiere de superficies paralelas y proyecciones asıcomo el diagrama de Voronoi en superficies. Los algoritmos para la generacion de losdiagramas de Voronoi en superficies fueron necesarios para la comprobacion computa-cional de las propiedades de los modelos generados. En la actualidad, estamos estudiandopropiedades relacionadas con la Teorıa de Grafo, como el crecimiento del numero de ve-cinos en mediapara cada celula en funcion del ratio entre las curvaturas de las distintascapas que constituyen el tejido epitelial.

References

[1] Pedro Gomez-Galvez, Pablo Vicente-Munuera, Antonio Tagua, Cristina Forja, Ana M.Castro, Marta Letran, Andrea Valencia-Exposito, Clara Grima, Marina Bermudez-Gallardo, Oscar Serrano-Perez-Higueras, Florencia Cavodeassi, Sol Sotillos, Marıa D.Martın-Bermudo, Alberto Marquez, Javier Buceta, and Luis M. Escudero. Scutoidsare a geometrical solution to three-dimensional packing of epithelia. Nature Commu-nications, 9(1):2960, 2018.