Resúmenes

Matemática Discreta

Ordenados alfabéticamente por título.
Por modificaciones, comunicarse al correo del Noticiero UMA (uma.noticiero@gmail.com).

Álgebra de Terwilliger asociada a Geometrías Parciales

Ana Carolina Maldonado (FCEFyN-UNC. , ana.carolina.maldonado@unc.edu.ar); Blas Fernández (CMaLP, UNLP y CONICET, bfernandez@mate.unlp.edu.ar)

En este trabajo en conjunto con Blas Fernández (CMaLP, UNLP y CONICET) describimos el álgebra de Terwilliger del grafo asociado a una Geometría Parcial $\mathcal{PG}$.

El caso $t=1$ esta descripto en $\left[ 1 \right]$. En esta charla mostramos los avances sobre el caso general.

Geometrías Parciales

Una geometría parcial $\mathcal{PG}$ consta de un sistema de puntos y líneas, y una relación de incidencia, que satisface los siguientes axiomas $A_1$ - $A_4$. Si un punto es incidente con una línea diremos que el punto cae en ella y que la línea pasa por el punto. Si dos líneas son incidentes con el mismo punto, diremos que se intersectan:

$A_1.$ Dos puntos cualesquiera son incidentes con a lo sumo una sola línea.

$A_2.$ Cada punto es incidente con $r$ líneas.

$A_3.$ Cada línea es incidente con $k$ puntos.

$A_4.$ Si un punto $P$ no es incidente con una línea $l$, por $P$ pasan exactamente $t$ líneas $(t\geq 1)$ que se intersectan entre ellas.

Grafo asociado a una Geometría Parcial

El grafo $G=\left(X,E(G) \right)$ asociado a una $\mathcal{PG}$ $(r, k ,t)$ se define como el grafo cuyo conjunto de vértices $X$ se corresponden con los puntos de la geometría, y en el cual dos vértices están o no unidos si los correspondientes puntos de la geometría caen o no en una misma línea.

Algebra de Terwilliger asociada a un grafo.

Dado un grafo conexo $G=\left( X, E(G) \right) $ y $x \in X$. Para cada entero $i$, $0 \leq i \leq d$, donde $d$ es la excentricidad del vértice $x$; el $i$-ésimo dual idempotente de $G$ con respecto a $x$ es la matriz diagonal $E_i^{*}:=E_i^{*}(x) \in Mat_{X}(\mathbb{C})$ donde, para cada $y \in X$, la $(y,y)$-entrada es igual a $1$ si $\partial(x,y)=i$ y $0$, en caso contrario.

El álgebra de Terwilliger de $G$ con respecto a $x$ es la subálgebra
$\mathcal{T}$:=$\mathcal{T}(x)$ de $Mat_{X}(\mathbb{C})$ generada por la matriz de adyacencia $A$ de $G$ y las duales idempotentes de $G$ con respecto a $x$.

Referencias

  1. Levstein, F.; Maldonado. Generalized quadrangles and subconstituent algebra. CUBO A Mathematical Journal. Vol.12, No 02, 53-75. (2010).
  2. Wang, Kaishun; Maldonado, Ana Carolina; Lv, Benjian; More on the Terwilliger algebra of Johnson schemes; Elsevier Science; Discrete Mathematics; 328; 54-62 (2014).
  3. Terwilliger, P. The subconstituent algebra of an association scheme, (part i). Journal of Algebraic Combinatorics 1, 4 (1992), 363-388.

Resumen en PDF

Aplicaciones de Índices de poder en los distintos órganos de cogobierno de la Universidad Nacional de San Luis.

Patricia Lucía Galdeano (UNSL, patriciagaldeano@gmail.com); Adriana Amieva Rodriguez (UNSL, adry.91101@gmail.com)

En este trabajo se analizará el poder que tienen las mujeres en los distintos órganos de cogobierno de la Universidad Nacional de San Luis. La universidad argentina posee características que la distinguen entre las otras universidades del mundo. Su gratuidad, el ingreso irrestricto, el cogobierno y las actividades de extensión. Este sistema público de educación superior es claramente mayoritario en cantidad de estudiantes, egresados, desarrollo de la investigación, posgrado y extensión, esto se expresan en números contundentes en nuestro país. La inclusión de la mujer en la universidad ha llevado un largo proceso, desde los albores de la reforma universitaria en el siglo pasado (1), donde el hecho de que la mujer que se matriculaba en una carrera universitaria era todo un hito y por ello las mujeres representaban una minoría dentro del padrón estudiantil. A pesar de esto, con el pasar de los años la mujer ha sabido ganar su espacio dentro de la universidad argentina. Según datos del Instituto de la Mujer (2), en el año 1999 la mujer representaba el 53 Sin embargo, esta mayoría femenina no se ha extendido a todas las carreras de forma homogénea, ya que actualmente el mayor número de mujeres egresadas son de carreras de las ramas de las ciencias Sociales y la salud. Mientras que en las carreras relacionadas a las ingenierías y las ciencias duras predominan los egresados masculinos. Esta tendencia se ve reflejada también en los cargos docentes y espacios de poder en la universidad. Si bien hay mayor presencia de mujeres en el plantel docente universitario, estas desempeñan los cargos de menor jerarquía como son los auxiliares, mientras que los varones predominan en los cargos de mayor jerarquía como son los profesores titulares. En cuanto a los espacios de poder conseguidos por la mujer podemos decir que no existe equidad en la participación. Según (4), en el gobierno universitario argentino uno de cada 10 rectores universitarios en el país son mujeres. De la misma manera, también se menciona, que solo 3 de cada 10 decanos en las universidades son mujeres. Vemos también como solo en las facultades relacionadas a las ciencias humanas encontramos mayor número de decanas, mientras que en el resto de las facultades vinculadas a otras ramas de las ciencias son gobernadas ampliamente por los hombres. En concordancia con esto podemos destacar que en la Universidad Nacional de San Luis, desde la vuelta de la democracia, ha tenido 9 rectores electos, de los cuales solo uno de ellos ha sido de sexo femenino.Además, en la mayoria de los casos las fórmulas estaban conformadas por dos por candidatos masculinos y solo en cuatro ocaciones han resultado electas fórmulas de ambos sexos. La importancia de todo esto radica en que de las universidades saldrán los futuros dirigentes de nuestro país y no se le está dando, a la mujer, la equidad de asumir las riendas del destino colectivo. Usamos la teoría de juegos Cooperativos que es una rama de la matemática que modelar situaciones de conflicto (juegos) donde intervienen dos o más agentes (jugadores). Esta teoría es útil para modelar diferentes tipos de situaciones (políticas, económicas, sociales, etc.) donde el desenlace de la situación depende de las decisiones de los agentes que intervienen en el problema.Usaremos las soluciones del tipo puntual como el Valor de Shapley (Shapley 1953) y el índice de Banzhaf-Coleman (Coleman 1971; Banzhaf 1965, Banzhaf 1968), estos índices de poder son valores numéricos que pretenden evidenciar el poder que posee cada coalición. Teniendo en cuenta esto, en este trabajo utilizaremos dichos índices para estudiar la distribución de poder de las mujeres dentro de los diferentes órganos de gobierno de la Universidad Nacional de San Luis en las elecciones 2013, 2014, 2016 y 2017.

Resumen en PDF

Asignaciones descentralizadas con compromiso de las empresas

Nadia Cecillia Guiñazú (Instituto de Matemática Aplicada San Luis-UNSL, nadia_cecilia@hotmail.com.ar); Jorge Armando Oviedo (Instituto de Matemática Aplicada San Luis-UNSL, joviedo@unsl.edu.ar)

En este trabajo estudiamos juegos de asignación dinámicos, en el que las empresas y los trabajadores, interactúan repetidamente en un mercado de trabajo descentralizado. En cada etapa, las empresas, quienes tienen una posición vacante, realizan ofertas a los trabajadores, quienes luego deciden en forma individual que oferta aceptar; estas ofertas y respuestas dependen del compromiso y paciencia de los agentes. El juego de asignación se desarrolla en un entorno dinámico y no cooperativo; donde todos los agentes derivan su pago de su asignación en cada periodo.

En nuestro modelo consideramos que, las empresas asumen compromisos (ofrecen un puesto laboral permanente), mientras que los trabajadores no lo hacen, es decir que ellos pueden renunciar pero no pueden ser despedidos.

Obtenemos una caracterización de qué tipo de asignaciones estables son resultado de un equilibrio estacionario (equilibrios de Nash perfecto en subjuegos, donde las estrategias son estacionarias). Para probar esto, utilizamos el concepto de ciclo (Irving R. W. y Leather P., 1986) y desarrollamos un Algoritmo de Re-estabilización Acelerada, basado en el algoritmo de (Blum, Y., Roth A., Rothblum, U., 1997), con el cual calculamos la cantidad mínima de periodos necesarios para que un trabajador obtenga un puesto laboral. Podemos interpretar cada iteración del Algoritmo de Re-estabilización Acelerada como una etapa del juego de asignación con compromiso de las empresas.

Resumen en PDF

Caracterización de los grafos $B_0$--VPG de contacto dentro de la clase de los grafos arco-circulares

Flavia Bonomo (Universidad de Buenos Aires - CONICET, fbonomo@dc.uba.ar); Esther Galby (University of Fribourg, esther.galby@unifr.ch); Carolina Lucía González (Universidad de Buenos Aires - CONICET, cgonzalez@dc.uba.ar)

Dados un conjunto de elementos $A$ y una familia $\mathcal{F}$ finita de subconjuntos de $A$, el grafo intersección de $\mathcal{F}$ es aquel cuyos vértices están en una correspondencia uno a uno con los elementos de $\mathcal{F}$ y además dos vértices son adyacentes si y solo si sus correspondientes elementos de $\mathcal{F}$ tienen intersección no vacía. Un grafo es arco-circular si es el grafo intersección de alguna familia finita de arcos de una misma circunferencia. Un grafo se dice $B_0$--VPG de contacto si es el grafo de intersección de una familia de segmentos horizontales y verticales en una grilla, los cuales se pueden tocar pero no cruzar ni superponer. En [CPG] se muestra que el problema de reconocimiento de esta última clase de grafos es NP-completo, sin embargo existen algoritmos polinomiales de reconocimiento y caracterizaciones por subgrafos inducidos prohibidos minimales para algunas clases de grafos, como cordales, $P_4$--tidy y bipartitos planares (ver [variosCPG]).

En este trabajo presentamos una caracterización por subgrafos inducidos prohibidos minimales de los grafos $B_0$--VPG de contacto dentro de la clase de los grafos arco-circulares y además proveemos un algoritmo de tiempo polinomial para reconocer dichos grafos.

Bibliografía

[variosCPG] F. Bonomo, M. P. Mazzoleni, M. L. Rean y B. Ries. On some special classes of contact $B_0$-VPG graphs. arXiv:1807.07372. Manuscrito (2018).

[chordalCPG] F. Bonomo, M. P. Mazzoleni, M. L. Rean y B. Ries. Characterising Chordal Contact $B_0$--VPG Graphs. Lecture Notes in Computer Science (ISCO 2018)

[CPG] Z. Deniz, E. Galby, A. Munaro y B. Ries. On contact graphs of paths on a grid. Graph Drawing and Network Visualization, 317--330 (2018).

[planarCPG] H. de Fraysseix, P. Ossona de Mendez y J. Pach. Representation of planar graphs by segments. Intuitive Geometry 63, 453--463 (1991).

Resumen en PDF

Determinante e inversa de matrices circulantes a bloques

Cristian Panelo (Facultad de Ciencias Físico Matemáticas y Naturales UNSL, cristian.panelo.tag@gmail.com); Daniel Alejandro Jaume (Facultad de Ciencias Físico Matemáticas y Naturales UNSL, daniel.jaume.tag@gmail.com)

Definición 1: Sean \(n,r,s\) y \(t\) enteros no negativos tales que \(0\leq t < s\leq n-1\). Sean \(A\) y \(B\) matrices cuadradas de orden \(r\). Con \(C_{n,t,s}(A,B)\) denotamos la matriz circulante a bloques \(Circ\left(C_{0},C_{1},…,C_{n-1} \right)\), donde \(C_{t} =A\), \(C_{s} = B\), y para todo \(h\ne s,t\), \(C_{h}=O_{r}\) es la matriz de ceros de orden \(r\).

Usualmente trabajamos con \(t=0\), en este caso sólo escribimos \(C_{n,s}(A,B)\) en lugar de \(C_{n,0,s}(A,B)\).

Sean \(n\) y \(s\) dos enteros. Su máximo común divisor es denotado con $\gcd(n,s)$. Además denotamos $n \backslash s : = \frac{n}{\gcd(n,s)}$. Con \(\left[s \right]_{n}\) denotaremos la primer solución no negativa de la ecuación \(s = x \mod n\).

Teorema 2: Sean \(n\) y \(s\) enteros no negativos tales que \(0<s\leq n-1\). Sean \(A\) y \(B\) matrices cuadradas de orden \(r\) tales que \(AB=BA\) y \(A\) es no singular. Entonces

\(\det\left(C_{n,s}(A,B) \right) = \left(\det(A) \right)^{n} \left(\det\left(I_{r} - \left(-A^{-1} B \right)^{n\backslash s} \right) \right)^{\gcd(n,s)}.\)

Definición 3: Sean \(n\) y \(s\) enteros no negativos tales que \(0<s\leq n-1\). Sean \(A\) y \(B\) matrices cuadradas de orden \(r\) tales que \(A^{n\backslash s} - (-B)^{n \backslash s}\) es no singular. Para cada \(i\in\{0,…,n-1\}\), definimos

$\Omega(i) = \begin{cases} A^{\alpha_{i}}B^{\beta_{i}} \left(A^{n\backslash s} - (-B)^{n \backslash s} \right)^{-1}, & \text{si } i \in R(n,s),\\ O_{r}, & \text{ en otro caso}. \end{cases}$

donde $\alpha_{i}= n\backslash s- \vec{d}(i)-1$ y $\beta_{i}=\vec{d}(i)$ y \(\vec{d}(i)\) es tomado del digrafo \(D\left(C_{n,s}(1,1) \right)\), asociado a la matriz \(C_{n,s}{1}{1}\), y

\(R(n,s) := \{ \left[0.s \right]_{n}, \left[1.s \right]_{n},…, \left[((n\backslash s) -1).s \right]_{n} \},\)

También definimos la siguiente matriz circulante a bloques

\(D_{n,s}^{M}(A,B) := Circ \left((-1)^{\beta_{0}}\Omega(0), …, (-1)^{\beta_{n-1}}\Omega(n-1) \right),\)

donde \(\beta_{i}\) y \(\Omega(i)\) están dados en la Definición 3.

Teorema 4: Sean $n$ y $s$ dos enteros no negativos tales que $0< s \leq n-1$, y sean $A$ y $B$ dos matrices cuadradas de orden \(r\). Si \(B\ne \pm A\) y \(A^{n \backslash s}-(-B)^{n \backslash s}\) es no singular, entonces \(C_{n,s}(A,B)\) es invertible y su inversa es \(D_{n,s}^{M}(A,B)\).

Resumen en PDF

El espectro de grafos de Paley generalizados y códigos cíclicos irreducibles asociados

Ricardo Podestá (Universidad Nacional de Córdoba, podesta@famaf.unc.edu.ar); Denis E. Videla (Universidad Nacional de Córdoba, devidela@famaf.unc.edu.ar)

Los grafos de Paley generalizados son ciertos grafos de Cayley $\Gamma(k,q)=Cay(\mathbb{F}_q,R_k)$ cuyo conjunto de vértices es un cuerpo finito de $q$ elementos $\mathbb{F}_q$ y su conjunto de conexión está dado por $R_k=\{x^k : x\in \mathbb{F}_q^*\}$.

\

En esta charla, primero daremos el espectro del grafo en términos de períodos Gaussianos. Para el caso en que $\Gamma(k,q)$ es semiprimitivo, damos su espectro explícitamente y deducimos propiedades estructurales de los grafos a través de dicho espectro. En segundo lugar consideraremos ciertos códigos cíclicos irreducibles asociados $C(k,q)$ y mostramos que los espectros de $C(k,q)$ y de $\Gamma(k,q)$ se determinan mutuamente. Con esto es posible calcular los espectros de $\Gamma(3,q)$ y $\Gamma(4,q)$.

\

Por último, si quedara tiempo, usando grafos $\Gamma(k,q)$ producto-descomponibles mostraremos cómo se pueden calcular los espectros de nuevos códigos cíclicos irreducibles construidos a partir de otros menores de espectro conocido. Esto tiene aplicaciones al conteo de puntos racionales de curvas de Artin-Schreier en extensiones de cuerpos y a la reduccion del cálculo de períodos de Gauss de parámetros grandes en términos de otros menores y conocidos.

\

Esta charla se basa en un trabajo conjunto en curso con Denis Videla.

Resumen en PDF

El Modelo del Matrimonio con Indiferencias: Un enfoque desde la Programación Lineal

Noelia Juarez (IMASL UNSL, noemjuarez@gmail.com); Pablo Neme (IMASL UNSL, pabloneme08@gmail.com); Jorge Armando Oviedo (IMASL UNSL, joviedo@unsl.edu.ar)

En este trabajo estudiamos el modelo de asignación bilateral (matching) uno-a-uno con indiferencias. Últimamente han surgido problemas donde se muestra la necesidad de estudiar el modelo con indiferencias. Un ejemplo es el ingreso de alumnos de nivel inicial (o medio) a las escuelas (ver Referencias), estas priorizan a los alumnos con algún criterio (cercan ía o zona de influencia, notas, etc.) sin embargo puede haber indiferencias en estos ordenes de prioridad, mientras que los estudiantes tienen un orden de preferencia (estricto) sobre las escuelas a las que quieren asistir. El objetivo es asignar estudiantes (en forma estable o robusta) a las escuelas.

El modelo con indiferencias es una generalización del modelo sin indiferencias o modelo clásico, este último ha sido muy estudiado. Hay ejemplos del modelo con indiferencias donde no se pueden generalizar los resultados del modelo clásico.

Vande Vate (1989) y Rothblum (1992) estudiaron el modelo de asignación bilateral uno-a-uno con preferencias estrictas utilizando como herramienta programación lineal. Introdujeron un sistema de inecuaciones lineales que generaron un poliedro convexo. Demostraron que las asignaciones estables del modelo uno-a-uno eran exactamente los puntos extremos de este poliedro convexo.

En este trabajo, caraterizamos las asignaciones estables del modelo con indiferencias, como soluciones enteras de un sistema de inecuaciones lineales generalizando así el resultado de Vande Vate (1989) y Rothblum (1992).

En el modelo de asignación uno-a-uno con preferencias estrictas , Gale y Shapley (1962) mostraron la existencia de las asignaciones estables ó ptimas para el conjunto de hombres y de mujeres $\mu _{M}$ y $\mu _{W}$ respectivamente. Al permitir indiferencias en las preferencias las asignaciones estables óptimas podrían no ser únicas. Mostramos, un programa lineal entero que calcula una asignaci ón estable optimal para el conjunto de hombres (mujeres).

\thispagestyle{empty}

Expositor: { Juarez Noelia Mariel}

Autor/es: { Juarez Noelia (; noemjuarez@gmail.com), Pablo Neme, Jorge Oviedo }



Referencias10pt

Erdil, A. y Ergin,H. (2008), What's the Matter with Tie-Breaking? Improvement efficiency in school choice, American Economic Review, 98(3), 669-89.

Gale, D., y Shapley, L. (1962), College admissions and the stability of marriage, American Mathematical Monthly, 69, 9-5.

Roth, A., Rothblum, U. y Vande Vate J. (1993) Stable matchings, optimal assignments and linear programming. Mathematical Operation Research, 18:803--828 .

Rothblum, U. (1992), Characterization of stable matching as extreme proint of a polytope, Mathematical Programming North-Holland 54: 57-67 . Cambriage University Press, Cambridge, England. Econometric Society Monographs .18.

Resumen en PDF

El problema de mínima violación cromática: nuevas familias de facetas.

Diego Delle Donne (Université Paris 13, Sorbonne Paris Cité - ICI, Universidad Nacional de General Sarmiento, diegodd@gmail.com); Mariana Silvina Escalante (FCEIA, Universidad Nacional de Rosario - CONICET, mariana@fceia.unr.edu.ar); María Elisa Ugarte (FCEIA, Universidad Nacional de Rosario, mariel_ugarte@yahoo.com)

Un $k$-coloreo en un grafo es una partición del conjunto de vértices en $k$ conjuntos estables. El problema clásico de coloreo de vértices (VCP) tiene como objetivo encontrar el menor $k$ necesario para que el grafo sea $k$-coloreable.

Continuamos nuestro estudio de una generalización del VCP, llamado el problema de la mínima violación cromática (MCVP), en el cual, dado un grafo $G=(V,E)$, un conjunto de colores $\mathcal{C}$ y un subconjunto de aristas débiles $F \subseteq E$, se busca un $|\mathcal{C}|$-coloreo de $G'=(V,E\setminus F)$ que minimice el número de aristas de $F$ con ambos extremos en la misma clase de color. Cuando $F = \emptyset$, entonces el MCVP es el problema de $k$-coloreo, y por lo tanto el MCVP es NP-Difícil. Más aún, el MCVP también generaliza el problema de $k$-partición, cuando $F = E$. Aunque ya se conocen resultados poliedrales del problema de $k$-partición [Chopra95], existen diferencias significativas entre estos politopos y el caso general del MCVP.

Basándonos en una formulación del MCVP presentada en [BDDEMUV] como problema de programación entera relacionada con la formulación estándar del VCP [DDM2016], en este trabajo avanzamos en el estudio poliedral de la cápsula convexa de las soluciones factibles del mismo.

En [BDDEMUV] presentamos dos procedimientos generales de lifting que permiten generar desigualdades válidas (las cuales inducen facetas bajo ciertas hipótesis) a partir de desigualdades válidas genéricas y presentamos distintas familias de facetas, generadas por estos procedimientos.

En este trabajo presentamos nuevas familias de desigualdades válidas, obtenidas mediante los mencionados procedimientos de lifting, y estudiamos su facetitud basados en la estructura particular del subgrafo a la que están asociadas.

Bibliografía

[BDDEMUV] Braga M., Delle Donne D., Escalante M., Marenco J., Ugarte M. E., Varaldo M. C. The minimum chromatic violation problem: a polyhedral approach. Dicrete Applied Mathematics (En prensa) (2019)

[DDM2016] Delle Donne D., Marenco J. Polyhedral studies of vertex coloring problems: The standard formulation. Discrete Optimization 21 (2016) 1--13.

[Chopra95] S. Chopra and M. R. Rao, Facets ok The $k$-partition polytope. Discrete applied mathematics 61-1 (1995) 27--48.

Resumen en PDF

Energía de randić y grafos $TB$

Adrián Pastine (Universidad Nacional de San Luis, adrian.pastine.tag@gmail.com); Luiz Emilio Allem (Universidade Federal do Rio Grande do Sul, emilio.allem@ufrgs.br); Gonzalo Molina (Universidad Nacional de San Luis, lgmolina@unsl.edu.ar)

La matriz de randić de un grafo $G$ está dada por \[ r_{ij}=\begin{cases} \frac{1}{\sqrt{\deg(i)\deg(j)}}&\text{si }\{i,j\} \text{ es una arista de }G\\ 0 & \text{si no}, \end{cases} \] donde $\deg(i)$ es el grado del vértice $i$. La energía de randić, $RE(G)$, es la suma de los valores absolutos de los autovalores de $R$. En el 2014, Gutman, Furtula y Bozkurt conjeturaron que los grafos conexos de $n$ vértices que tienen mayor energía de randić son el sol (si $n$ es impar) y el sol doble balanceado (si $n$ es par).

Un grafo $TB$ es un grafo bipartito con bipartición $A,B$ que satisface que para todo vértice $b\in B$, $\deg(b)\leq 2$. En este trabajo demostramos que los grafos $TB$ satisfacen la conjetura de Gutman, Furtula y Bozkurt.

Resumen en PDF

Estabilidad en Juegos de Asignación en Redes

Alejandra Daniela Garcés Pósleman (Facultad de Ingeniería, Universidad Nacional de San Juan, aleposleman@yahoo.com)

Se considera el modelo de asignación muchos a muchos en redes con contratos. Un ejemplo de éste es un proceso industrial donde intervienen agentes, como trabajadores, productores, distribuidores, minoristas, etc. Algunos suministran insumos básicos para la industria y no consumen ningún producto final. Otros compran los productos finales. El resto son los intermediarios, que reciben insumos de algunos agentes en la industria, los convierten en productos finales a un determinado precio y luego los venden. Hatfield y Kominers (2012) introdujeron este modelo en contratos y demostraron que existe una biyección entre el conjunto de todos los puntos fijos de un determinado operador isótono y el conjunto de todas las asignaciones estables de este modelo, considerando sólo las propiedades de aciclicidad sobre el conjunto de contratos y sustituibilidad sobre las preferencias de los agentes; lo cual es erróneo. Dado esto, primero se presentan ejemplos sustentando esta afirmación. Luego se introduce una propiedad sobre las preferencias de los agentes, llamada regularidad, que junto a las dos propiedades antes mencionadas, permite recuperar la estructura de reticulado en el conjunto de asignaciones estables. Además, se definen dos relaciones de orden parcial, basadas en las preferencias de todos los agentes que actúan como compradores y/o vendedores, respectivamente. Se demuestra que, bajo las suposiciones de aciclicidad, sustituibilidad y regularidad, cada una de esas relaciones de orden proporciona una estructura de reticulado al conjunto de asignaciones estables. Finalmente se prueba que dichos reticulados son duales, lo que muestra la existencia de una intuitiva contraposición de intereses entre compradores y vendedores.

Resumen en PDF

Factorización de enteros con hipérbolas modulares

Juan Di Mauro (ICC-UBA, jdimauro@dc.uba.ar)

El problema de factorización de enteros tiene una gran importancia práctica y teórica. En la práctica, el uso extendido del criptosistema RSA ha estimulado la investigación en algoritmos de factorización eficientes y por eso, el caso que se tratará es $n=pq$ con $p,q$ primos de mangitud $\sqrt{n}$ y $|p-q|$ lo suficientemente grande.

Este trabajo tiene origen en la observación hecha por H. Scolnik, de que para ciertos enteros $c$ la ecuación diofántica $n+x^2=y^2$ módulo $c$ tiene solución única. Se define como target de $n$ a una terna representando la solución. El conjunto de targets guarda una relación estrecha con las hipérbolas modulares y algunas propiedades entre ambos se corresponden directamente.

Por otra parte, las soluciones modulares dan información sobre los factores de $n$ en $\mathbb{Z}$ y pueden ayudar a atacar el problema de factorización. Aunque para casi todos los enteros hay más de una solución, se prueba un resultado de interes en sí mismo: para enteros cumpliendo ciertas condiciones, el cociente entre la cantidad de soluciones módulo $c$ y $c$ tiende asintóticamente a $0$. Un nuevo algoritmo de factorización es construido a partir de eso y se estima su tiempo de ejecución. Instancias de prueba de la implementación del algoritmo corroboran el tiempo de ejecución estimado.

Resumen en PDF

Geometrías no hereditarias

Silvia Tondato (CeMaLF, Dto. de Matemática Facultad de Ciencias Exactas UNLP., tondato@mate.unlp.edu.ar); Marisa Gutierrrez (Conicet, CeMaLF, Dto. de Matemática Facultad de Ciencias Exactas UNLP., marisa@mate.unlp.edu.ar); Fábio Protti (Instituto de Computación, Universidad Federal Fluminense., fabio@ic.uf.br)

Un espacio de convexidad de un grafo es un par $(G,\mathcal{M})$ siendo $G$ un grafo conexo con $V(G) \neq \emptyset$ y $\mathcal{M}$ una colección de subconjuntos de $V(G)$, conteniendo a $\emptyset$ y $V$, cerrada por intersecciones y cumpliendo: si $\mathcal{D} \subseteq \mathcal{M}$ ordenado por inclusión $\bigcup_{D \in \mathcal{D}}D \subseteq \mathcal{M}$. Cada elemento de $\mathcal{M}$ se denomina convexo e induce un subgrafo conexo de $G$.

Una geometrí a convexa es un espacio de convexidad que satisface: Cada convexo es cápsula convexa de sus extremos.

Las convexidades más naturales definidas en un grafo $G$ son aquellas que surgen de un sistema de caminos $\mathcal{P}$ en el grafo $G$.

Un $A \subseteq V(G)$ es $\mathcal{P}-convexo$ si para todo par de vértices $u$ y $v$ de $A$ resulta $\mathcal{P}(u,v) \subseteq A$, siendo $\mathcal{P}(u,v) $ el conjunto de todos los vértices de caminos de $\mathcal{P}$ uniendo $u$ y $v$.

Se sabe que los grafos cordales son una geometrí a respecto de la convexidad definida por los caminos inducidos, que los grafos Ptomatic son una geometrí a respecto de la convexidad definida por caminos mí nimos, que los grafos de intervalos son una geometrí a respecto de la convexidad definida por los caminos toll, que los grafos de intervalos propios son una geometrí a respecto de la convexidad definida por los caminos toll débiles y que los grafos débilmente bipolarizables(grafos libres de el grafo casa, el grafo A, el grafo domino, y los ciclos inducidos de longitud mayor o igual a 5) son una geometrí a respecto de caminos inducidos de longitud mayor o igual a 3.

Todas las clases de grafos antes mencionadas son hereditarias. De esta última observación surge naturalmente la siguiente pregunta: toda convexidad definida por un sistema de caminos define una clase de grafos hereditaria?

En este trabajo se presentan resultados sobre geometrí as respecto de la convexidad definida por caminos inducidos de longitud menor o igual a $k$ siendo $k$ un número natural mayor a 2. En particular, se prueba que esas geometrí as no son heriditarias y que si $G$ es una geometrí a respecto de caminos inducidos de longitud menor o igual a $k$ entonces $G$ es cordal de diámetro menor o igual a $k$.

Resumen en PDF

Hamiltonicidad de grafos estables de Kneser

Agustina Victoria Ledezma (Universidad Nacional de San Luis, agustinaledezma@gmail.com); Adrián Pastine (Universidad Nacional de San Luis, adrian.pastine.tag@gmail.com)

El grafo de Kneser $KG(n,k)$ tiene como vértices los subconjuntos de cardinalidad $k$ de el conjunto $\{1,\ldots,n\}$, y como aristas $\{A,B\}$ si $A$ y $B$ son disjuntos. El subgrafo de Kneser $s$-estable, $KG_{s-stab}(n,k)$ se obtiene al eliminar los vértices con elementos cuya distancia cíclica sea menor o igual a $s$. Muchas propiedades de los grafos estables de Kneser han sido estudiadas en los últimos años, por ejemplo su número cromático, número de independencia, y grupo de automorfismos. En este trabajo estudiaremos la existencia de ciclos hamiltonianos en los grafos $s$-estables de Kneser, es decir la existencia de un ciclo que pase por todos los vértices del grafo.

Resumen en PDF

Independence and Matching Numbers of Unicyclic Graphs from Null Space

Gonzalo Molina (Universidad Nacional de San Luis, lgmolina@unsl.edu.ar); Daniel A. Jaume (Universidad Nacional de San Luis, djaume@unsl.edu.ar); Maikon Machado Toledo (Universidade Federal do Rio Grande do Sul, maikon.toledo@ufrgs.br); Luiz Emilio Allem (Universidade Federal do Rio Grande do Sul, emilio.allem@ufrgs.br); Vilmar Trevisan (Universidade Federal do Rio Grande do Sul, trevisan@mat.ufrgs.br)

Let $G$ be a graph with $n$ vertices. The support of the null space of $A(G)$ is denoted by $Supp(G)$. Let $T$ be a tree. The $S$-forest of $T$, denoted by $\mathcal{F}_S(T)$, is defined as the subgraph induced by the closed neighborhood of $Supp(T)$. The $N$-forest of $T$, denoted by $\mathcal{F}_N(T)$, is defined as $\mathcal{F}_N(T):=T-\mathcal{F}_S(T)$. The core of $G$, denoted by $Core(G)$, is the set of all the neighbors of the supported vertices of $G$.

A unicyclic graph $G$ is a connected graph containing exactly one cycle. The induced cycle in $G$ is denoted by $C$. A pendant tree of $G$ at $v\in V(C)$, denoted $G\{v\}$, is the induced connected subgraph of $G$ with maximum possible number of vertices, which contains the vertex $v$ and no other vertex of $C$.

A unicyclic graph $G$ is of Type $I$ if and only if there exists at least one pendant tree $G\lbrace{v}\rbrace$ such that $v\notin{Supp(G\lbrace{v}\rbrace)}$. A unicyclic graph $G$ is of Type $ II $ if and only if every pendant tree $G\lbrace{v}\rbrace$ is such that $v\in{Supp(G\lbrace{v}\rbrace)}$.

Let $G$ be a unicyclic graph and $C$ its cycle. Let $G-C=\bigcup\limits^{k}_{i=1} {T_i}$, where $T_i$ is a connected component of $G-C$.

We show that, if $G$ is a unicyclic graph of Type $I$ and $G\lbrace{v}\rbrace$ its pendant tree such that $v\notin{Supp(G\lbrace{v}\rbrace)}$, then \[ \alpha{(G)}=\vert{Supp(G\lbrace{v}\rbrace)}\vert+\vert{Supp(G-G\lbrace{v}\rbrace)}\vert{+}\frac{\vert{V(\mathcal{F}_N(G\lbrace{v}\rbrace))}\vert{+}\vert{V(\mathcal{F}_N(G-G\lbrace{v}\rbrace))}\vert}{2},\]
\[ \nu(G)=\vert{Core(G\lbrace{v}\rbrace)}\vert{+}\vert{Core(G-G\lbrace{v}\rbrace)}\vert{+}\frac{\vert{V(\mathcal{F}_N(G\lbrace{v}\rbrace))}\vert+\vert{V(\mathcal{F}_N(G-G\lbrace{v}\rbrace))}\vert}{2},\] and if $G$ is a unicyclic graph of Type $II$, then \[ \alpha{(G)}=\left\lfloor{\frac{\vert{V(C)}\vert}{2}}\right\rfloor+\sum\limits^{k}_{i=1}\vert{Supp(T_i)}\vert{+} \frac{\vert{V(\mathcal{F}_N(T_i))}\vert}{2},\] \[ \nu(G)=\left\lfloor{\frac{\vert{V(C)}\vert}{2}}\right\rfloor+\sum\limits^{k}_{i=1}\vert{Core(T_i)}\vert+\frac{\vert{V(\mathcal{F}_N(T_i))}\vert}{2}.\]

Resumen en PDF

Inmersiones completas y número de independencia

Sebastián Bustamante (Universidad de Chile, sebustam@gmail.com); Daniel Quiroz (Universidad de Chile, dquirozb@gmail.com); Maya Stein (Universidad de Chile, mstein@dim.uchile.cl); José Zamora (Universidad Andrés Bello, josezamora@unab.cl)

La versión análoga a la conjetura de Hadwiger para el orden de las inmersiones nos dice que todo grafo $G$ contiene a $K_{\chi(G)}$ como inmersión. De ser cierta, implicaría que todo grafo con $n$ vértices y número de independencia $\alpha$ contiene a $K_{\lceil \frac{n}{\alpha} \rceil}$ como inmersión.

El mejor resultado conocido para esta conjetura se debe a Gauthier, Le y Wollan, quienes probaron que todo grafo contiene una inmersión de un completo en $\lceil \frac{\chi(G)-4}{3.54} \rceil$ vértices. Esto implica que todo grafo con $n$ vértices y número de independencia $\alpha$ contiene una inmersión de un completo en $\lceil \frac{n}{3.54\alpha} -1.13 \rceil$ vértices.

En la charla discutiremos como mejorar este último resultado para todo $\alpha \ge 3$ y esbozaremos la historia de estos problemas.

Resumen en PDF

Isometrías, grupos finitos y teoría de códigos

Maximiliano Vides (Universidad Nacional del Litoral, mvides@famaf.unc.edu.ar); Ricardo Podestá (Universidad Nacional de Córdoba, podesta@famaf.unc.edu.ar)

\indent En este trabajo estudiaremos la existencia y construcción de isometrías entre grupos finitos. Dados $G$ y $H$, dos grupos finitos del mismo cardinal ¿Existe alguna métrica $d$ tal que $(G,d) \leftrightarrow (H,d)$ sea una isometría y $d$ sea invariante por traslaciones de ambos grupos? Veremos que la respuesta es afirmativa, ademas del caso trivial, explicando como extender isometrías entre subgrupos de $G$ y $H$.

Estudiando los grupos de simetrías de métricas, podemos discernir la existencia o no de isometrías entre grupos finitos. Obtendremos generalizaciones del conocido mapa de Gray, consiguiendo isometrías de grupos cíclicos en espacios con la métrica de Rosenbloom-Tsfasman. También extendemos esta isometría para grupos no necesariamente cíclicos (o abelianos). Esta charla es parte de un trabajo en curso con Ricardo Podestá.

Resumen en PDF

Los problemas de códigos de identificación, localización-dominación, localización-dominación abierta y localización-dominación total bajo ciertas operaciones en grafos

Yanina, P. Lucarini (FCEIA-UNR, lucarini@fceia.unr.edu.ar); Silvia Bianchi (FCEIA-UNR, sbianchi@fceia.unr.edu.ar); Gabriela Argiroffo (FCEIA-UNR, garua@fceia.unr.edu.ar)

En este trabajo estudiamos $4$ problemas que son variantes del clásico problema del mínimo conjunto dominante en un grafo $G=(V,E)$ y que han sido estudiados activamente durante las últimas décadas (ver Lobstein [Lobstein-Lib]).

Un conjunto $C \subseteq V$ es un:

Aquí, analizamos los cambios que se producen sobre el mínimo cardinal de los conjuntos mencionados cuando aplicamos ciertas operaciones en grafos: la adición de un vértice universal, la corona generalizada de un grafo y el cuadrado de un grafo.

Bibliografía

[hhh] T.W. Haynes, M. A. Henning, J. Howard, Locating and total-dominating sets in trees, Discrete Applied Mathematics 154, (2006), 1293--1300.

[kcl] M. G. Karpovsky, K. Chakrabarty, L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 44 (1998), 599--611.

[Lobstein-Lib] A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs, https:/www.lri.enst.fr/ lobstein/debutBIBidetlocdom.pdf

[ss] S.J. Seo, P.J. Slater, Open neighborhood locating dominating sets, Australasian Journal of Combinatorics, 46, (2010), 109--119.

[slater1] P. J. Slater, Dominating and reference sets in a graph, J. Math. Phis. Sci. 22(1988) 445--455.

Resumen en PDF

Mínimo número de consultas necesarias para encontrar un árbol generador de peso mínimo bajo incertidumbre

José Soto (Universidad de Chile, jsoto@dim.uchile.cl); Arturo Merino (Universidad de Chile, amerino@dim.uchile.cl)

Sea $G=(V,E)$ un grafo conexo para el cual se desconoce el tpeso exacto de sus aristas. Sin embargo, para cada elemento $e\in E$ se conoce un conjunto no vacío, llamado área de incertidumbre, que contiene los posibles pesos que la arista $e$ puede tener. Decimos que un conjunto $X\subseteq E$ es una consulta factible para el problema si al revelar simultáneamente los pesos reales de los elementos de $X$, tenemos información suficiente para calcular un árbol generador de peso mínimo de $E$, independiente del valor preciso de las aristas no reveladas. El objetivo del problema es determinar el conjunto factible de menor tamaño/costo.

El problema anterior puede ser generalizado a matroides, donde el objetivo es encontrar la consulta de tamaño/costo mínimo que permite calcular una base de peso mínimo. Este problema es de especial interés para aplicaciones donde obtener datos exactos es costoso, pero datos vagos son de fácil acceso.

En este trabajo proveemos una caracterización de las consultas factibles de tamaño/peso mínimo para cualquier matroide con incertidumbre y encontramos un algoritmo polinomial para determinar dicha consulta. Nuestros algoritmos funcionan para cualquier tipo de incertidumbre, es decir las áreas de incertidumbre pueden ser conjuntos de números reales arbitrarios, no necesariamente intervalos o conjuntos finitos.

Resumen en PDF

(Non-)Convergence in Coalition Formation Games

Pablo Neme (IMASL-UNSL, pabloneme08@gmail.com); Elena Iñarra (Universidad del Pais Vasco, elena.inarra@ehu.eus); Agustín Bonifacio (IMASL-UNSL, agustinbonifacio@gmail.com)

In models of multi-agent interactions, deviations by coalitions of agents from one outcome to another may lead to situations in which a stable solution cannot be reached. This problem becomes especially significant when convergence to efficient markets is at stake. If a market is efficient and agents' preferences clear the market, there is no need for intervention. By contrast, when preferences are unable to clear an efficient market an arbitrator, perhaps using an algorithmic technique, is required for the efficient solution to be implemented. Hence, it is essential to distinguish in which of these two situations a market may be.

In searches for stability in coalition formation games there are many studies that restrict the domain of preference profiles by skipping circularity among coalitions (rings): See for instance Chun (2000), Pycia (2012), and Inal (2015). However, there are coalition formation games with rings coexisting with stable partitions and it is precisely in such situations that our research question becomes relevant, i.e. what coalition formation games induce convergence to stability.

As we show in this paper, rings are the only source that precludes convergence to stability but their mere presence is not sufficient to generate lack of convergence to stability, so our study focuses analyzing preferences with rings in order to discern which ones perform this task. The rings that preclude convergence to stability are called effective.

Our approach to the study of convergence comes from the observation that in coalition formation games stable partitions and dead-end cycles(absorbing sets) of partitions coexist, and such coexistence is what precludes convergence to stability. In this paper, we show that the existence of an effective ring is a necessary and sufficient condition to induce an absorbing set of cardinality of 3 or more. In turn, this absorbing set generates rotations among coalitions in such a way that convergence to stability is impeded. To illustrate the importance of our results we present several economic examples in which convergence to stability is not possible and therefore there is a need for an arbitrator if a stable solution is the goal to be achieved.

Resumen en PDF

Nulidad Mínima y Máxima de una secuencia de grados de unicíclicos.

Daniel Alejandro Jaume (Universidad Nacional de San Luis, daniel.jaume.tag@gmail.com); Maikon Machado Toledo (Universidade Federal de Rio Grande do Sul, maikon.toledo@ufrgs.br); Gonzalo Molina (Universidad Nacional de San Luis, lgonzalomolina@gmail.com); Marco Puliti Lartigue (Universidad Nacional de San Luis, marco.puliti@gmail.com)

Un grafo unicíclico es un grafo conectado que contiene un único ciclo inducido. La sucesión finita no decreciente $s=(d_1,d_2,\ldots, d_n)$ se dice que es una secuencia de grados de unicíclicos de longitud $n$ si existe al menos un grafo unicícliclo tal que su secuencia de grados es $s$. El conjunto de todos los unicíclicos conectados que tienen a $s$ como su secuencia de grados es denotado por $\mathcal{U}_s$.

Definimos \[ \displaystyle null_m(\mathcal{U}_s):=\min_{U\in \mathcal{U}_s}\{null(A(U))\},\] y \[ \displaystyle null_M(\mathcal{U}_s):=\max_{U\in \mathcal{U}_s}\{null(A(U))\},\] las nulidades mínima y máxima posibles en $\mathcal{U}_s$. Con $l(s)$ denotamos la cantidad de 1's de $s$ y con $n_2(s)$ la cantidad de 2's de $s$. Sea $a(s)$ el número de aniquilación de $s$, definido como el mayor índice tal que \[ \displaystyle \sum_{i=1}^{a(s)}d_i\leq n.\]

En este trabajo probamos que:

\[ null_m(\mathcal{U}_s)=\left\{ \begin{array}{cl} 2l(s)-n & \text{, si } l(s)\geq \lfloor \frac{n}{2} \rfloor, \\ 1 & \text{, si } \frac{n-3}{2}< l(s)< \lfloor \frac{n}{2} \rfloor \quad \text {y \] y \[ null_M(\mathcal{U}_s)=\left\{ \begin{array}{cl} 2a(s)-n+2 &\text{, si } n_2(s)\geq 3 \quad \text{y} \displaystyle \sum_{i=1}^{a(s)+1}d_i=n+1, \\ 2a(s)-n& \text{, en otro caso}. \end{array}\right.\]

Resumen en PDF

On Strategy-proofness and Semilattice Single-peakedness

Agustín Germán Bonifacio (Instituto de Matemática Aplicada San Luis - Universidad Nacional de San Luis, abonifacio@unsl.edu.ar); Jordi Massó (Universitat Autònoma de Barcelona, jordi.masso@uab.es)

We study social choice rules defined on the domain of semilattice single-peaked preferences. Semilattice single-peakedness has been identified as the necessary condition that a set of preferences must satisfy so that the set can be the domain of a strategy-proof, tops-only, anonymous and unanimous rule. We characterize the class of all such rules on that domain and show that they are deeply related to the supremum of the underlying semilattice structure.

Resumen en PDF

On the contracts between doctors and rural hospitals

Beatriz Alejandra Millán Guerra (Universidad Nacional de San Juan - Instituto de Matemática Aplicada San Luis, millanbetty2@gmail.com)

We prove that the set of doctors assigned to a hospital with unfilled positions is the same in all stable allocations for a many-to-one matching model with contracts where all hospitals have q-separable preferences. However, the characteristics of the relationships among these agents may differ from one stable allocation to another.

Resumen en PDF

On the inverse of nonsingular unicyclic graphs.

Daniel A. Jaume (Universidad Nacional de San Luis, djaume@unsl.edu.ar); Gonzalo Molina (Universidad Nacional de San Luis, gonzalo.molina.tag@gmail.com); Cristian Panelo (Universidad Nacional de San Luis, cristian.panelo.tag@gmail.com); Rodrigo Sota (Universidad Nacional de San Luis, rodrigo.sota.tag@gmail.com)

An unicyclic graph is a connected graph containing exactly one cycle. The induced cycled in $U$ is denoted by $C$. An unicyclic graph $U$ is said that is nonsingular if its adjacency matrix $A(U)$ is nonsingular. Unicyclic graphs are of three types: T1, T2 and T3. In this work we give formulas for the inverse of nonsingular unicyclic in terms of their matching structure.

Given an unicyclic graph $U$, a walk $W$ in $U$ and a matching $M$ of $U$, the walk $W$ is called an alternating walk with respect to $M$ if it has edges that are alternately unmatched and matched in $M$. An alternating walk $W$ with respect to $M$ is said a coaugmenting walk in $U$ with respect to $M$ if $W$ starts and ends at matched edges. The set of all coaugmenting walks from $i$ to $j$ (two different vertices of $U$) with respect to any maximun matching $M$ of $U$ is denoted by $CoW(U,i,j)$.

Let $U$ be a nonsingular unicyclic graph of Type 1 of order $n$. Then \[ A^{-1}(U) =Inv_{1}(U):=\sum \limits_{W \in CoW(U,i,j)}(-1)^{\left\lfloor \frac{|W|}{2} \right\rfloor},\] where $|W|$ is the length of the walk $W$.

For each vertex $v \in V (C)$, $T(v)$ denotes the pendant tree at $v$. We define $PSupp(U):= \bigcup_{u \in V(C)} Supp(T(u)).$ A matching $M$ of $U$ is called non-sun matching if $e \in M$ and $|e\cap E(C)| >1$, then $|e\cap E(C)|=2$. Let $i,j \in V(U)$, the set of all the coaugmenting walks from $i$ to $j$ with respect to any non-sun maximum matching is denoted by $CoW_{ns}(U,i,j)$. These walks are called non-sun coaugmenting walks.

For every nonsingular unicyclic $U$ of type 2 $A(U)^{-1}= Inv_{1}(U)+Inv_{2}(U),$ where $Inv_{1}(U)$ and $Inv_{2}(U)$ are two matrices of order $n$ given by \[ Inv_{1}(U)_{i,j} := \left\{ \begin{array}{ll} \frac{1}{2} (-1)^{\left\lfloor \frac{d_{w}(i,j)}{2} \right\rfloor}, & \text{ if } i,j \in PSupp(G) \text{ and } CoW_{ns}(U,i,j) \neq \emptyset, \\ & \\ \frac{1}{2} (-1)^{\left\lfloor \frac{|C|}{2}\right\rfloor + \left\lfloor \frac{d(i,j)}{2} \right\rfloor}, & \text{ if } i,j \in PSupp(G) \text{ and } CoW_{ns}(U,i,j) = \emptyset, \\ & \\ 0, & \text{otherwise}, \end{array} \right. \] where $d_{w}(i,j)$ is the length of a shorter non-sun coaugmenting walk from $i$ to $j$, and $d(i,j)$ is the usual distance. And \[ Inv_{2}(U)_{i,j} := \left\{ \begin{array}{ll} \sum \limits_{W \in CoW(U,i,j)} (-1)^{\left\lfloor \frac{|W|}{2} \right\rfloor}, & \text{if } i,j \in V\left( U-C \right) \text{ and } CoW(U-C,i,j) \neq \emptyset,\\ & \\ 0, & \text{otherwise}. \end{array} \right. \]

For every nonsingular unicyclic $U$ of type 3 $A(U)^{-1}= Inv_{2}(U)+Inv_{3}(U),$ where $Inv_{3}(U)$ is the matrix of order $n$ given by \[ Inv_{3}(U)_{i,j} := \left\{ \begin{array}{ll} \frac{1}{2} (-1)^{\left\lfloor \frac{d_{w}(i,j)}{2} \right\rfloor}, & \text{ if } i,j \in PSupp(G) \text{ and } CoW(U,i,j) \neq \emptyset, \\ & \\ 0, & \text{otherwise}. \end{array} \right. \]

Resumen en PDF

Operador de intersección de dicliques en Digrafos

Marisa Gutierrrez (Centro de Matemática de La Plata, marisa@mate.unlp.edu.ar); Silvia Tondato (Centro de Matemática de La Plata, tondato@mate.unlp.edu.ar); Bernardo Llano (Universidad Autónoma Metropolitana de Iztapalapa, México, llano@xanum.uam.mx); Miguel PizaÑa (Universidad Autónoma Metropolitana de Iztapalapa, México, mpizana@gmail.com)

Trataremos con digrafos simples, esto es sin lazos ni aristas múltiples. Sean $X$ e $Y$ subconjuntos disjuntos no vací os de vértices de $D$, $(X,Y)$ es un disimplex de $D$ si para cada $x\in X$ y cada $y\in Y$, $(x,y)$ es un arco de $D$. Sean $(X,Y)$ y $(Z,W)$ disimplex de $D$, decimos que $(X,Y)$ está incluí do en $(Z,W)$, $(X,Y) \preceq (Z,W)$ sii $X \subseteq Z$ y $Y \subseteq W$. Claramente es una relación de orden entre pares de subconjuntos de $V(D)$. Un disimplex $(X,Y)$ es un diclique de $D$ si es maximal con respecto a la relación de orden $\preceq$. Consideramos siguiente operador en digrafos:

\

Operador Diclique $\overrightarrow{K}$

Presentamos resultados preliminares en comparación con el clásico operador clique en grafos:

  1. generación de los dicliques desde los entornos del digrafo.

  2. Puntos fijos del operador.

  3. Suryectividad.

  4. Monotoní a.

  5. Comportamiento en torneos, torneos transitivos

  6. Comportamiento en digrafos fuertemente conexos.

  7. Variación de Distancia, Diámetro, Cuello y Altura.

  8. Comportamiento en Circulantes.

Resumen en PDF

Problema de asignación de aulas en institución con dos sedes

Mariana Silvina Escalante (CONICET y FCEIA - Universidad Nacional de Rosario, mariana@fceia.unr.edu.ar); Miguel Chiesa (FCEIA - Universidad Nacional de Rosario, miguechiesa@gmail.com); Pablo Fekete (FCEIA - Universidad Nacional de Rosario, fekete@fceia.unr.edu.ar)

Los problemas de asignación de aulas surgen naturalmente en el contexto de instituciones educativas, cuando se debe asignar un aula a cada curso sin incurrir en superposiciones horarias. Un antecedente que podemos mencionar en cuanto a un modelo general de asignación de aulas puede encontrarse en: A. Phillips, H. Waterer, M. Ehrgott, D. Ryan, Integer Programming Methods for large scale practical classroom assignment problems. Computers and Operations Research 53 (2015) 42-53.

En este trabajo consideramos el problema particular que surge en instituciones que cuentan con más de un edificio dentro de un predio extenso. Nos proponemos dar una formulación de este problema como programa lineal entero y ensayar distintas funciones objetivos que nos permitan comparar la “conveniencia” de las soluciones halladas.

Dado el conjunto de cursos, días y horarios de cursada, conjunto de aulas, matriz de compatibilidad entre los cursos y las aulas, tiempo de traslado estimado de una sede a otra y, para cada par de cursos y la cantidad de alumnos en común entre los dos cursos, el problema consiste en asignar a cada curso un aula compatible, de modo tal que cursos superpuestos no compartan el aula.

El problema se enmarca en el tema de coloreo en grafos, en particular, dadas las características del mismo, en el coloreo por listas.

Proponemos distintos modelos de programción lineal entera que reflejan la estructura del problema a ser analizado basados en el modelo estándar de coloreo (véase P. Coll, J. Marenco, I. Méndez Díaz y P. Zabala, Facets of the graph coloring polytope. Ann. Oper. Res. 116 (2002) 79-90). Estudiamos distintas funciones objetivos que pueden ser consideradas, por ejemplo, teniendo en cuenta la existencia de varias sedes minimizamos el tiempo de traslado entre una y otra sede, o tenemos en cuenta la restricción de que un alumno no deba cambiar de sede entre un curso y el siguiente.

Finalmente, consideramos el problema concreto de la asignación de aulas en la FCEIA, con sus dos sedes, Pellegrini y CUR, teniendo en cuenta los datos provistos por la propia facultad para el primer año, primer cuatrimestre de todas las carreras, correspondientes al año 2018.

Resumen en PDF

Problema de empaquetamiento generalizado en grafos con pocos $P_4$'s

Erica Hinrichsen (Universidad Nacional de Rosario, ericah@fceia.unr.edu.ar); Natalí Vansteenkiste (Universidad Nacional de Rosario, natali@fceia.unr.edu.ar); Pablo Torres (Universidad Nacional de Rosario y CONICET, ptorres@fceia.unr.edu.ar)

Dado un grafo $G=(V,E)$ y vectores $\textbf{k},{{\boldsymbol\ell}}, \textbf{u}\in \mathbb{Z}_+^V$ con ${{\boldsymbol\ell}} \leq \textbf{u}$, decimos que una asignación $f:V\rightarrow\mathbb{Z}_{+}$ es un $(\textbf{k},{{\boldsymbol\ell}},\textbf{u})$-empaquetamiento de $G$ si para todo $v\in V$, se verifica: \[ \ell(v)\leq f(v)\leq u(v) \;\;\; \text{ y } \;\;\; f(N[v])\leq k(v)\] donde $N[v]$ denota la vecindad cerrada de $v$. El Problema de Empaquetamiento Generalizado (PEG) consiste en determinar el número de $(\textbf{k},{{\boldsymbol\ell}},\textbf{u})$-empaquetamiento de $G$, definido como \[ L_{\textbf{k},{{\boldsymbol\ell}},\textbf{u}}(G)= \max \left\{\sum_{v\in V} f(v): f \text{ es un } (\textbf{k},{{\boldsymbol\ell}},\textbf{u})-\text{empaquetamiento}\right\}.\]

Este problema tiene como instancias particulares a la mayor parte de las diferentes variaciones de problemas de empaquetamiento de grafos estudiados en la literatura. Por ejemplo, los $k$-limited packings [3] corresponden al caso $k(v)=k$, $\ell(v)=0$ y $u(v)=1$ para todo $v \in V$. Si $\ell(v)=0$ y $u(v)\in\{0,1\}$ para todo $v \in V$, la asignación $f$ se denomina $(\textbf{k}, \mathcal{A})$-limited packings [1], donde $\mathcal{A}=\{v\in V: u(v)=1\}$; y si $k(v)=u(v)=k$, $\ell(v)=0$ para todo $v\in V$, tenemos las $\{k\}$-packing functions [2].

En este trabajo obtenemos una fórmula que permite calcular el número de $(\textbf{k},{{\boldsymbol\ell}},\textbf{u})$-empaque-
tamiento de la unión y el join de dos grafos, en función de los parámetros de los grafos involucrados. A partir de este resultado, el estudio del problema en grafos generales puede reducirse a grafos modulares (conexos con complementos conexos).

Analizamos el comportamiento del parámetro en grafos arañas y quasi arañas, grafos modulares de varias familias de grafos con pocos $P_4$'s. A partir de los resultados obtenidos se deriva un algoritmo lineal para el PEG sobre las instacias particulares correspondientes a las $\{k\}$-packing function en grafos $P_4$-tidy. Para el caso $\textbf{k}$ general y $\textbf{u}\geq \textbf{k}$, obtuvimos fórmulas para el número de $(\textbf{k},{{\boldsymbol\ell}},\textbf{u})$-empaquetamiento de grafos arañas flacas y resultados parciales para grafos arañas gordas.

Bibliografía

[1] M. P. Dobson, V. Leoni, G. Nasini, The $k$-limited packing and $k$-tuple domination problems in strongly chordal, $P_4$-tidy and split graphs, Electronic Notes in Discrete Mathematics 36 559--566, 2010.

[2] E. Hinrichsen, V. Leoni, $\{k\}$-packing functions in graphs. Lecture Notes in Computer Science, Springer, Heidelberg , pp. 325--335, 2014.

[3] R. Gallant, G. Gunther, B. Hartnell, D. Rall, Limited packings in graphs, Discrete Appl. Math. 158 (12), 1357--1364, 2010.

Resumen en PDF

Proper circular arc graphs as intersection graphs of paths ton a grid

María Pía Mazzoleni (Universidad Nacional de La Plata, maria_pia_400@hotmail.com); Esther Galby (Universidad de Friburgo, esther.galby@unifr.ch); Bernard Ries (Universidad de Friburgo, bernard.ries@unifr.ch)

Golumbic et al. introduced the class of edge intersection graphs of paths on a grid (EPG graphs), i.e. graphs for which there exists a collection of nontrivial paths on a rectangular grid in one-to-one correspondence with their vertex set, such that two vertices are adjacent if and only if the corresponding paths share at least one edge of the grid, and showed that every graph is in fact an EPG graph. A natural restriction which was thereupon considered, suggests to limit the number of bends (i.e. $90^{\circ}$ turns at a grid-point) that a path may have; for $k\geq 0$, the class $B_k$-EPG consists of those EPG graphs admitting a representation in which each path has at most $k$ bends.

A circular arc graph (CA graph) is an intersection graph of open arcs on a circle, i.e. a graph $G = (V, E)$ is a circular arc graph if one can associate an open arc on a circle with each vertex such that two vertices are adjacent if and only if their corresponding arcs intersect. If $C$ denotes the corresponding circle and $A$ the corresponding set of arcs, then $R = (C, A)$ is called a circular arc representation of $G$. A circular arc graph having a circular arc representation where no arc properly contains another is called a proper circular arc graph (PCA graph).

In this paper, we present a characterization by an infinite family of minimal forbidden induced subgraphs, of proper circular arc graphs which are intersection graphs of paths on a grid, where each path has at most one bend. That is, we present a characterization by an infinite family of minimal forbidden induced subgraphs for $B_1-EPG\cap PCA$. This is a first step towards finding a characterization of the minimal graphs in ($CA\cap B_2-EPG$) $\smallsetminus$ ($CA\cap B_1-EPG$).

Resumen en PDF

Propiedades estratégicas del Modelo de Asignación con preferencias Substituibles y q-Separables

Jorge Oviedo (Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Dep. de Matemática (UNSL), joviedo12@gmail.com); Paola Manasero (Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Dep. de Matemática (UNSL), pmanasero@hotmail.com)

Cuando mecanismos estables se usan en modelos de asignación bilateral muchos-a-uno emergen preguntas sobre incentivos en ambos lados del mercado (empresas-trabajadores). Sotomayor (2012) mostró en el modelo de asignación bilateral muchos a uno con preferencias q-responsiva el teorema general de manipulabilidad: si hay más de una asignación estable al menos un agente puede beneficiarse si declara una preferencia diferente a la verdadera. Nosotros estudiamos la validez de este resultado en modelo de asignación bilateral muchos-a-uno con preferencias substituibles y q-separables. Damos distintas definiciones de manipulabilidad que dependen de que estrategia deben usar los agentes para manipular (es decir, beneficiarse por declarar un orden distinto de su verdadero orden) el resultado del modelo. Mostramos ejemplos donde no se puede generalizar los resultados en el modelo con preferencias solo substituibles.

Resumen en PDF

$r$-estrellas en árboles

Emiliano Juan José Estrugo (Universidad Nacional de San Luis, juan.estrugo.tag@gmail.com); Adrián Pastine (Universidad Nacional de San Luis, adrian.pastine.tag@gmail.com)

Dado un grafo $G$, un entero $r \geq 1$ y un vértice $v$, la $r$-estrella centrada en $v$, $I^r_v(G)$, es la familia de conjuntos independientes de $G$ de cardinalidad $r$ que contienen al vértice $v$. Hulbert y Kamat conjeturaron que dado un árbol $T$ y un entero $r$, siempre es posible encontrar hoja $\ell$ tal que $|I^r_v(T)|\leq |I^r_{\ell}(T)|$ para todo vértice $v$. Si un árbol satisface dicha condición decimos que es un $HK$-árbol . Baber y Borg encontraron, de manera independiente, ejemplos de árboles que no son $HK$, mostrando que la conjetura de Hulbert y Kamat es falsa. Queda entonces por responder la pregunta de cuáles son los árboles $HK$. En este trabajo presentamos condiciones suficientes para que un árbol sea $HK$. En particular demostramos que los grafos caterpillar son $HK$. Nuestro resultado nos permite, además, distinguir un conjunto de vértices para los cuales existen hojas con $r$-estrellas de mayor tama\ {n}o. Esto da una mejor idea de como deben ser estructuralmente los árboles que no son $HK$.

Resumen en PDF

Sobre el Problema de Matching Perfecto en Hipergrafos Bipartitos

Paola Tolomei (UNR-CONICET, ptolomei@fceia.unr.edu.ar); Mariana Escalante (UNR-CONICET, escalante@fceia.unr.edu.ar); Daniel Severin (UNR-CONICET, daniel@fceia.unr.edu.ar)

El Problema de Matching Perfecto de Mínimo Peso en Hipergrafos Bipartitos (MP) es un problema que generaliza a su homónimo sobre grafos bipartitos y, entre otras aplicaciones, permite modelar otro problema denominado Identificación Cruzada de Catálogos Estelares (véase D. Severín, Cross-identification of stellar catalogs with multiple stars: Complexity and Resolution, Electron. Notes Discr. Math. 69 (2018), 29--36).

Sea $\mathcal{H} = (X, \mathcal{E})$ un hipergrafo. Un conjunto $\mathcal{E}' \subset \mathcal{E}$ es un matching de $\mathcal{H}$ si es un conjunto de hiperaristas disjuntas, i.e. para $t_1, t_2 \in \mathcal{E}'$ diferentes, $t_1 \cap t_2 = \emptyset$. $\mathcal{H}$ es bipartito si $X$ puede ser particionado en conjuntos $A, B$ y cada hiperarista $t$ satisface $|t \cap A| = 1$. Para un hipergrafo bipartito $\mathcal{H} = (A \cup B, \mathcal{E})$ y $t \in \mathcal{E}$, la función $\pi_A : \mathcal{E} \rightarrow A$ aplicada a $t$, i.e. $\pi_A(t)$, devuelve el único elemento de $t \cap A$ y la función $\pi_B : \mathcal{E} \rightarrow \mathcal{P}(B)$ se define como $\pi_B(t) \doteq t \cap B$. Llamamos $\mathcal{K}$ al máximo valor posible de $|\pi_B(t)|$.

Un conjunto $\mathcal{E}' \subset \mathcal{E}$ es un matching perfecto de un hipergrafo bipartito $\mathcal{H}$ si $\mathcal{E}'$ es un matching de $\mathcal{H}$ que satura $A$, i.e. $A = \{\pi_A(t) : t \in \mathcal{E}'\}$. Sea $w \in \mathbb{R}^{\mathcal{E}}$ un vector de costos positivos. El MP consiste en obtener un matching perfecto $\mathcal{E}'$ de $\mathcal{H}$ tal que $\sum_{t \in \mathcal{E}'} w_t$ sea mínimo.

Notemos que $\mathcal{H}$ podría no admitir un matching perfecto. De hecho preguntarse por su existencia es NP-completo, aunque existen condiciones suficientes y un algoritmo polinomial cuando una de ellas se satisface (véase C. Annamalai, Finding Perfect Matchings in Bipartite Hypergraphs, Combinatorica (2018), 1285--1307).

El MP puede resolverse mediante una transformación al Problema del Conjunto Estable de Máximo Peso. Sea $G$ el grafo que surge de dicha transformación. En este trabajo: 1) caracterizamos cómo debe ser la instancia del MP para que $G$ sea claw-free, resultando polinomial en estos casos, 2) demostramos que el MP es polinomial si $|A| = 2$, y 3) hallamos algunas familias de desigualdades clique del poliedro surgido de la formulación del MP en el caso en que $\mathcal{H}$ es completo (i.e. existen todas las hiperaristas posibles) y $\mathcal{K} = 2$.

Resumen en PDF

Sobre grafos bloque $CPT$

Noemí Amalia Gudiño (CENTRO DE MATEMATICA DE LA PLATA - CONICET - DTO DE CIENCIAS BASICAS FI UNLP, noemigudino@mate.unlp.edu.ar); Liliana Alcón (CENTRO DE MATEMATICA DE LA PLATA - CONICET, liliana@mate.unlp.edu.ar); Marisa Gutierrrez (CENTRO DE MATEMATICA DE LA PLATA - CONICET, marisa@mate.unlp.edu.ar)

Dado un grafo $G=(V,E)$, una orientación $\overrightarrow{E}$ de las aristas de $G$ es una atribución a cada arista $uv$ de $G$ una de sus dos posibles orientaciones: $\overrightarrow{uv}$ (de $u$ a $v$) o $\overrightarrow{vu}$ (de $v$ a $u$). La orientación $\overrightarrow{E}$ se dice transitiva si $\overrightarrow{uv}\in \overrightarrow{E}$ y $\overrightarrow{vw}\in \overrightarrow{E}$ implica $\overrightarrow{uw}\in \overrightarrow{E}$. Un grafo es de comparabilidad si existe una orientación transitiva de sus aristas. En general un grafo de comparabilidad admite distintas orientaciones transitivas de sus aristas. Un modelo de contención $M_{\overrightarrow{E}}$ de un grafo orientado $G=(V,\overrightarrow{E})$ asigna a cada elemento $v\in V$ un conjunto $M_v$ de tal manera que $\overrightarrow{uv}\in \overrightarrow{E}$ si y solo si $M_u$ es un subconjunto propio de $M_v$. El modelo $M_{\overrightarrow{E}}$ es la familia de conjuntos $(M_v)_{v\in V}$. Los grafos de comparabilidad que admiten un modelo por contención que asigna a cada vértice un camino de un árbol $T$ (considerando cada camino como un conjunto de vértices) se llaman grafos $CPT$ [1, 2].

La caracterización de los grafos $CPT$ por subgrafos prohibidos minimales es un problema abierto. En este trabajo consideramos el problema de reconocimiento y el de caracterización de los grafo $CPT$ restringidos a la clase de los grafos bloque, es decir la clase de grafos en los que cada componente dos conexa es un completo.

Bibliografía

[1] L. Alcón, N. Gudiño, M. Gutierrez, Recent result on containment graphs of paths in a tree, Discrete Applied Mathematics 245, pp. 139--147 (2018).

[2] Golumbic, Martin Charles and Scheinerman Edward R.,Containment Graphs, Posets, and Related Classes of Graphs, Combinatorial Mathematics: Proceedings of the Third International Conference, Volume 555, 192--204 (1989).

Resumen en PDF

Sobre grafos con matrices de vecindades cerradas perfectas

Valeria Alejandra Leoni (UNR y CONICET, valeoni@fceia.unr.edu.ar); Mariana Silvina Escalante (UNR y CONICET, mariana@fceia.unr.edu.ar); Erica Hinrichsen (UNR , ericah@fceia.unr.edu.ar)

{En este trabajo estudiamos la familia $\mathcal{F}$ de los grafos $G$ con matriz de vecindades cerradas, $N[G]$, perfecta, i.e. $\{x\in [0,1]^n: N[G]x \leq \mathbf{1}\}$ es un poliedro entero, donde $n=|V(G)|$ y $\mathbf{1}$ es el vector cuyas componentes son todas iguales a 1.}

{Presentamos una caracterización parcial de la familia $\mathcal{F}$ a través de subgrafos inducidos prohibidos. }

{A partir de la caracterización de matrices perfectas debida a Chvátal [2], es necesario probar que $N[G]$ satisface dos propiedades, éstas son, ser matriz clique-nodo de un cierto grafo (denotado por $Q_G$) y la perfección del mismo.}

{En primer lugar, identificamos a la familia de grafos cuya matriz de vecindades cerradas es clique-nodo, a través de la ausencia de un número finito de grafos de hasta siete nodos como subgrafos inducidos.}

{Por [1], un grafo es perfecto si y solamente si no posee un agujero impar ni su complemento como subgrafo inducido por nodos. A partir de esta propiedad, en segundo lugar caracterizamos a aquellos grafos $G$ tales que $Q_G$ no posee agujeros impares como subgrafos inducidos por nodos. }

{Las dos caracterizaciones halladas nos permiten derivar una descripción de una superfamilia de $\mathcal{F}$ a través de subgrafos inducidos prohibidos. }

{La motivación original de este trabajo fue la de ampliar el conjunto de las instancias en las cuales el problema de optimización de la función $\{k\}$-empaquetadora en grafos puede ser resuelto en tiempo polinomial en función del tamaño de la entrada, conjunto al que pertenecen los grafos fuertemente cordales, entre otros [3, 4, 5].}





{Referencias}



{[1] Chudnovsky, M., G. Cornuéjols, X.Liu, P.Seymour and K.Vu\v sković, Recognizing Berge Graphs, Combinatorica 25 (2005), 143--187.}



{[2] Chvátal, V., On Certain Polytopes Associated with Graphs, Journal of Combinatorial Theory (B) 18 (1975), 138--154. 1991) 166--190.}



{[3] Conforti, M. and G. Cornuéjols, Balanced $0,+1,-1$ Matrices, Bicoloring and Total Dual Integrality, Mathematical Programming 71 (1995), 249--258.}



{[4] Farber, M., Characterizations of Strongly Chordal Graph, Discrete Mathematics 43 (1983), 173--189.}



{[5] Hinrichsen, E. and V. Leoni, $\{k\}$-packing functions of graphs. Lecture Notes in Computer Science (2014), 325--335.}

Resumen en PDF

Sobre variantes y superclases de los grafos split

Verónica Moyano (Instituto de Ciencias, Universidad Nacional de General Sarmiento; Argentina, vmoyano@campus.ungs.edu.ar); Luciano Norberto Grippo (Instituto de Ciencias, Universidad Nacional de General Sarmiento; Argentina, lgrippo@campus.ungs.edu.ar)

Un grafo $G$ es split si existe una clique $C$ tal que $G-C$ es un conjunto independiente (ver [3]). En esta charla mostraremos resultados sobre un variante y una superclase de los grafos split.

Un grafo $G$ es $k$-\{probe split\} si contiene una familia de conjuntos independientes $N_1,\ldots,N_k$ tales que se le puede agregar a $G$ un conjunto de aristas con ambos extremos en algún $N_i$ para $i=1,\ldots,k$, de forma tal que el grafo resultante sea un grafo split. Cuando $k=1$ a estos grafos se los conocen en la literatura como probe split y fueron caracterizados en [1]. En este trabajo presentaremos algunos resultados estructurales y de complejidad vinculados a esta clase de grafo. Decimos que un grafo $G$ es unipolar si exsiste una clique $C$ tal que $G-C$ es un grafo sin $P_3$ como subgrafo inducido; es decir, una unión disjunta de grafos completos [2]. Si además todos estos grafos completos tienen a los sumo $k$ vértices, diremos que el grafo es $k$-unipolar. En este trabajo presentaremos una caracterización estructural para los grafos $2$-unipolares.

Bibliografía

[1] Bang Le, V., de Ridder, H. N. Probe Split Graphs, Discrete Mathematics & Theoretical Computer Science 9 (2007).

[2] Ekim, T., Hell, P., Stacho, J. and de Werra, D. Polarity of chordal graphs, Discrete Applied Mathematics 156 (2008), pp. 2469--2479.

[3] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, North- Holland, Second Edition, 2004.

Resumen en PDF

Soporte de grafos de línea de árboles

Diego Gabriel Martinez (Universidad Nacional de San Luis, martinezdiegogabriel@gmail.com); Adrián Pastine (Universidad Nacional de San Luis, adrian.pastine.tag@gmail.com)

Dado un grafo $G=(V,E)$, el grafo de línea de $G$, $\mathcal{L}(G)$, tiene como vértices a las aristas de $G$, dos de las cuales son vecinas en $\mathcal{L}(G)$ si y sólo si tienen un vértice en común. Por otro lado, el soporte de un grafo son los vértices asociados a las coordenadas no nulas de los vectores del espacio nulo de su matriz de adyacencia. Este conjunto es interesante por brindar una conexión entre propiedades estructurales y propiedades espectrales de los grafos. Por ejemplo, el soporte de un árbol es la intersección de todos los conjuntos independientes máximos. En este trabajo estudiamos el soporte de los grafos de línea de los árboles. En particular, demostramos que el soporte es indepentiente si y sólo si el árbol original tiene un matching perfecto. Además, en dicho caso, el soporte coincide con las aristas del matching.

Resumen en PDF

Suryectividad del operador de torneos transitivos maximales

Maria Guadalupe Sanchez Vallduvi (Universidad Nacional de La Plata, mguadalupesanchezv@gmail.com); Marisa Gutierrrez (Universidad Nacional de La Plata, marisa@mate.unlp.edu.ar); Bernardo Llano (Universidad autonoma metropolitana de iztapalapa, Mexico, llano@xanum.uam.mx)

10pt

En grafos dirigidos, un torneo es un digrafo que posee un arco para cada par de vértices. Un torneo se dice transitivo si, para cada tres vértices $a,b,c$ se cumple la transitividad de la relación es decir si $(a,b),(b,c)$ son arcos del digrafo, entonces $(a,c)$ es un arco del digrafo.

Hemos definimos un operador similar al operador clique en grafos dirigidos. Dicho operador es el de intersección de subtorneos transitivos maximales en un digrafo, que se define de la siguiente manera:

  1. (i) $V(\tau (D))$ es el conjunto de todos los subtorneos transitivos maximales por contención del digrafo $D$ y

  2. (ii) $A(\tau (D))$ es el conjunto de todas aquellas flechas definidas de la siguiente forma: si $T_{1}$ y $T_{2}$ son torneos transitivos maximales de $D$, entonces $T_{1}\longrightarrow T_{2}$ si los vértices fuente de $T_{1}$ y sumidero de $T_{2}$ no pertenecen a $V(T_{1}) \cap V(T_{2})$ y los vértices sumidero de $T_{1}$ y fuente de $T_{2}$ pertenecen a $V(T_{1}) \cap V(T_{2})$.
En este trabajo hemos encontrado la prueba de que el operador $\tau$ no es suryectivo en la clase de los digrafos. Mostramos ejemplos de una familia infinita de digrafos que están en la imgen de $\tau$, sin embargo, añadiendo algunos arcos no están en la imagen.
Por otro lado, probamos que la imagen del operador es una clase no hereditaria de digrafos: mostramos un digrafo en la imagen de $\tau$ que al borrarle un vértice no está en la imagen del operador.

Resumen en PDF

Teorema de transición de árboles

Victor Nicolás SchvÖllner (Universidad Nacional de San Luis, victor.schvollner.tag@gmail.com); Daniel Alejandro Jaume (Universidad Nacional de San Luis, daniel.jaume.tag@gmail.com); Adrián Pastine (Universidad Nacional de San Luis, adrian.pastine.tag@gmail.com)

La secuencia de grados de un grafo es la lista de los grados de sus vértices. El $2$-switch es una operación que altera las aristas de un grafo, pero preserva su secuencia de grados. En 1973 Berge demostró que dados dos grafos cualesquiera con la misma secuencia de grados, existe una sucesión de $2$-switches que transforma uno en el otro. Esta es una herramienta fundamental para comprender los comportamientos de los grafos que comparten una secuencia de grados. En particular, si tomamos dos árboles, este teorema nos asegura poder transformar uno en el otro por medio de $2$-switches, pero no asegura que los grafos intermedios sean árboles. En este trabajo presentamos un teorema del estilo de Berge, que nos permite convertir un árbol en cualquier otro por medio de $2$-switches de manera tal que todos los grafos intermedios también sean árboles. Además, presentamos un algoritmo que permite determinar una sucesión de $2$-switches que realiza la transformación.

Resumen en PDF

Unos circularmente compatibles, $D$-circularidad y bigrafos arco-circulares propios

Martín D. Safe (Departamento de Matemática, Universidad Nacional del Sur (UNS), Bahía Blanca, Argentina e INMABB, Universidad Nacional del Sur (UNS)-CONICET, Bahía Blanca, Argentina, msafe@uns.edu.ar)

En 1969, Alan Tucker [2] caracterizó los grafos arco-circulares propios como aquellos grafos cuyas matrices de adyacencia aumentadas tienen la propiedad de los unos circularmente compatibles. Más aún, también halló un algoritmo de tiempo polinomial para decidir si cualquier matriz de adyacencia aumentada dada tiene la propiedad de los unos circularmente compatibles. Estos resultados le permitieron diseñar el primer algoritmo de reconocimiento de tiempo polinomial para los grafos arco-circulares propios. Sin embargo, como el propio Tucker señala, no resolvió los problemas de encontrar un teorema estructural y un algoritmo de reconocimiento eficiente para la propiedad de los unos circularmente compatibles en matrices arbitrarias (es decir, no solo para matrices de adyacencia aumentadas). En este trabajo resolvemos ambos problemas. Más precisamente, proporcionamos una caracterización por submatrices prohibidas minimales para la propiedad de los unos circularmente compatibles en matrices arbitrarias y un algoritmo de reconocimiento de tiempo lineal para la misma propiedad. Derivamos estos resultados de otros análogos para una propiedad relacionada llamada $D$-circularidad. Curiosamente, estos resultados conducen a una caracterización por subgrafos inducidos prohibidos minimales y a un algoritmo de reconocimiento de tiempo lineal para los bigrafos arco-circulares propios, resolviendo un problema planteado por primera vez por Basu, Das, Ghosh y Sen [1]. Nuestros resultados generalizan algunos resultados conocidos sobre los hipergrafos $D$-intervalares y los bigrafos de intervalos propios.

Bibliografía

[1] A. Basu, S. Das, S. Ghosh, and M. Sen. Circular-arc bigraphs and its subclasses. J. Graph Theory, 73(4):361--376, 2013.

[2] A. C. Tucker. Two characterizations of proper circular-arc graphs. PhD thesis, Stanford University, 1969.

Resumen en PDF

Upla dominación en grafos webs

Valeria Alejandra Leoni (UNR y Conicet, valeoni@fceia.unr.edu.ar); María Patricia Dobson (UNR, mpdobson@fceia.unr.edu.ar); María Inés Lopez Pujato (UNR y Conicet, lpujato@fceia.unr.edu.ar)

Dado un entero positivo $k$ y un grafo simple $G=(V,E)$, una $k$-upla dominante en $G$ es un subconjunto $D$ de $V$ tal que todo vértice perteneciente a $V$ es adyacente a al menos $k$ elementos de $D$ o es un vértice de $D$ que es adyacente a al menos $k-1$ elementos de $D$. El mínimo tamaño entre todas las $k$-uplas dominantes en $G$ se denota por $\gamma_{\times k}(G)$ [3].

Desde el punto de vista de la complejidad computacional de problemas de optimización, el problema de hallar una $k$-upla dominante de mínimo tamaño (para $k$ fijo) es NP-díficil [5]. En la clase de los grafos arco-circulares, su complejidad no es conocida para $k\geq 2$. Para $k=1$, en [4] se presenta un algoritmo eficiente que resuelve el problema en esta clase.

El objetivo es avanzar en el estudio de este problema sobre la clase de los grafos arco-circulares.

En un trabajo previo [2], hemos presentado un algoritmo eficiente que resuelve este problema en la clase de los grafos C$0$P, para todo valor de $k$ que no supere en más de 3 a la cantidad de vértices universales del grafo de entrada. Los grafos C0P son arco-circulares y están definidos como aquellos para los cuales su matriz de vecindades cerradas tiene la propiedad de los 0's consecutivos por columnas, propiedad de matrices de entradas 0,1 definida por Tucker en [6].

Siguiendo nuestra línea de estudio, en el presente trabajo avanzamos sobre otra subclase de grafos arco-circulares, la de los grafos web. Un grafo web, denotado por $W_n^m$ con $m\geq 1$ y $n >2m+1$, es un grafo para el cual el conjunto de sus vértices es $\left\{v_1,\cdots,v_{n}\right\}$ y $v_iv_j$ son adyacentes si y sólo si $|i-j|\leq m$, donde las adiciones se toman módulo $n$ [7]. Estos grafos en particular verifican la propiedad de los 1's circulares por columnas [6].

En [1], utilizando un enfoque poliedral, se presentan una cota superior y una inferior para cada valor de $k$ para el número $\gamma_{\times k}(W_n^{m})$. Además se obtiene el valor exacto de $\gamma_{\times 2}(W_n^{m})$.

Con otro tratamiento que se basa en la aritmética modular y en las propiedades de las matrices que definen a los grafos webs, en esta comunicación mostramos cómo hallar el valor exacto de $\gamma_{\times k}(W_n^{m})$ para todo valor de $k$, obteniéndose \[ \gamma_{\times k}(W_n^{m})=\left\lceil \dfrac{kn}{2m+1}\right\rceil,\] donde $n=c(2m+1)+r$ y $0\leq r\leq 2m$.



[1] Argiroffo, G., Escalante, M., Ugarte, M.E., On the $k$-dominating set polytope of web graphs, Electronic Notes in Discrete Mathematics 36 (2010), 1161--1168.

[2] Dobson, M.P., Leoni, V., Lopez Pujato, M.I., Tuple domination on graphs with the consecutive-zeros property, Electronic Notes in Theoretical Computer Science, en prensa.

[3] Harary, F., and T. W. Haynes, Double domination in graphs, Ars Combin. 55 (2000), 201--213.

[4] Hsu, W.L., and K.H. Tsai, Linear time algorithms on circular-arc graphs, Inform. Process. Lett. 40, 3 (1991), 123--129.

[5] Liao, C.S. and G. J. Chang, $k$-tuple domination in graphs, Inform. Process. Lett. 87, 1 (2003), 45--50.

[6] Tucker, A. Matrix characterizations of circular-arc graphs, Pacific J. Math. 39.2 (1971), 535--545.

[7] Turner, J. Point-symmetric graphs with a prime number of points, , J. Combin. Theory 3 (1967), 136--145.

Resumen en PDF

Zero Forcing Number sobre grafos Circulantes.

Elias Damian Cancela (Universidad Nacional de San Luis , elias.cancela.tag@gmail.com)

En este trabajo estudiamos el Zero Forcing Number para grafos Circulantes, una subfamilia de los grafos de Cayley, el cual denotamos $ Z(C(n,\{a_1, \ldots a_k\}))$. Primero obtenemos un lema sobre grafos de Cayley generales $G = Cay(Gamma, S)$ que nos permite encontrar ciertos $forts$ en $G$ dados $cosets$ en $Gamma$. Utilizamos este lema para encontrar cotas inferiores no triviales para $Z(Circ(2n,\{1,n-1\})$. Aplicando otras técnicas también encontramos cotas para $Z(C(2n,\{1,n-1\}))$ , $Z(C(2n,\{1,a, n-1\})))$, $Z(C(2n,\{a,b, n-1\})))$ entre otros varios casos. Además determinamos específicamente el Forcing Number para los casos $C(2n,\{1,n-1\})$ y $C(n,\{1,3\})$.También dado cualquier primo p encontramos cotas superiores para el caso general $ Z(C(p,\{a_1, \ldots a_k\}))$.

Resumen en PDF

UMA SOMACHI
Ir arriba