Seminari de Teoria de Grafs, Combinatòria i Aplicacions (1998-99)

Research Group on Graph Theory and Combinatorics

• 01-10-98 Ileana Streinu. Nature Doesn't Have Straight-Lines: the Complexity of Recognizing Visibility Graphs.
• 15-10-98 Angeles Carmona. El Núcleo Laplaciano: Un Algoritmo para la Obtención de Caminos Cortos en Grafos Distancia-Regulares.
• 22-10-98 Eduardo Canale. Grafos Asintóticamente Densos.
• 29-10-98 Margarida Mitjana. The Spectra of a Vertex Symmetric Digraph.
• 05-11-98 Miquel Angel Fiol. Grafos, Matrices y Geometría.
• 12-11-98 José Luís Ruiz. On the Connected Components of Galois Graphs.
• 19-11-98 Josep Fàbrega. Extraconnectivity of Digraphs.
• 26-11-98 Oriol Serra. A Local-Global Principle for Macaulay Posets.
• 03-12-98 Carlos Domingo. Practical Sampling Methods for Data Mining.
• 17-12-98 Manuel Hernández, Jaume Sanz. Research Activities on GPS and Neural Networks
• 14-01-99 Carlos Andújar. Validity-Preserving Simplification of Very Complex Polyhedral Solids
• 21-01-99 Victor Zinoviev. On Three-Regular Subgraphs of Four-Regular Graphs
• 04-02-99 Alexandre Nogué. Sobre la Capacitat de Shannon
• 11-02-99 Ferran Hurtado. Transformacions Elementals d'Objectes Geometrics
• 18-02-99 José Gómez. Una Nueva Familia de Grafos Densos
• 25-02-99 Pavol Hell. Generalizations of Matching
• 04-03-99 Pavol Hell. List Partitions
• 11-03-99 Margarida Mitjana. Tesi Doctoral: Propagació d'Informació en Grafs i Digrafs que Modelen Xarxes d'Interconnexió Simètriques
• 11-03-99 Francesc Aguiló. Dinàmiques Discretes sobre les L-Formes Planes
• 08-04-99 María José Serna. Graph Layout Problems
• 15-04-99 Francesc Aguiló i Maria Lluïsa Fiol. Superposició de Tesel.lacions Congruents i Periòdiques com a Mètode de Descomposició de Tessel.les d'Igual Àrea
• 22-04-99 Marc Noy. Enumeration of crossing and non-crossing configurations.
• 29-04-99 Francesc Antoni Muntaner. On Edge Magic and Super Edge Magic Graphs.
• 06-05-99 Germán Sáez i Moreno. Aplicacions de la Combinatòria a la Criptografia.
• 13-05-99 Xavier Marcote. The Jordan Normal Form of a Line Digraph.
• 18-05-99 Erich Prisner. Generating Interconnection Networks via Graph Operators.
• 20-05-99 Carlos Seara. Separabilidad de Objectos en el Plano.
• 27-05-99 Camino Balbuena. Diameter Vulnerability of Generalized Compound Graphs.
• 03-06-99 Steve Skiena. Jai-Technology: Computers, Gambling, and Mathematical Modeling to Win.
• 7-06-99 Miquel Angel Fiol. Algebraic Characterizations of Distance-Regular Graphs. FPSAC'99, Invited lecture.
• 03-06-99 Sonia Pérez Mansilla. Construction of k-Arc Regular Digraphs.

Ileana Streinu.

(Smith College)

NATURE DOESN'T HAVE STRAIGHT-LINES: THE COMPLEXITY OF RECOGNIZING VISIBILITY GRAPHS.

Sessió inaugural del SEMINARI LIMDA

(Dijous 1 d' Octubre de 1998, 14:00, Aula 002, Modul C4, Campus Nord, UPC)

Angeles Carmona.

EL NUCLEO LAPLACIANO: UN ALGORITMO PARA LA OBTENCION DE CAMINOS CORTOS EN GRAFOS DISTANCIA-REGULARES.

Autors: Enrique Bendito, Angeles Carmona y Andrés M. Encinas

(Dijous 15 d' Octubre de 1998, 12:00, Aula 005, Modul C3, Campus Nord, UPC)

Abstract. Los elementos b\'asicos de una Teor\'\i a del Potencial son: un espacio subyacente junto con las medidas soportadas por \'el y un n\'ucleo. En este trabajo consideramos como espacio, el conjunto de v\'ertices de un grafo $\Gamma$ y como n\'ucleo, el Laplaciano $\L$ de $\Gamma$. Entonces probamos que $\L$ satisface algunas propiedades fundamentales tales como los principios del m\'aximo y de la energ\'\i a, as\'\i \,como el principio de equilibrio sobre cada subconjunto propio de $\Gamma$.
Si consideramos $\Gamma$ como subconjunto propio de un cierto grafo, el problema de equilibrio para $\Gamma$ tiene soluci\'on y el n\'umero de componentes diferentes de su medida de equilibrio, conduce a una cota superior del di\'ametro de $\Gamma$.
La aplicaci\'on de esta t\'ecnica a grafos distancia-regulares, permite desarrollar un algoritmo para la obtenci\'on de los caminos cortos entre cualquier par de v\'ertices y obtener adem\'as el "intersection array´´ del grafo en t\'erminos de la medida de equilibrio. Finalmente, damos una nueva caracterizaci\'on de los grafos fuertemente regulares.

Eduardo Canale.

GRAFOS ASINTOTICAMENTE DENSOS.

Autors: Eduardo Canale, José Gómez.

(Dijous 22 d' Octubre de 1998, 12:00, Aula 005, Modul C3, Campus Nord,UPC)

Abstract. En la busqueda de grafos asintoticamente densos (grandes ordenes para diametro y grado fijos) nos centraremos en una familia particular: Los Grafos Compuestos Generalizados. Primero veremos el orden asintotico de estos grafos comparandolo con otras familias conocidas. Segundo analizaremos un poco su definicion. Tercero veremos como redefinirlos utilizando dos tipos de productos: 1) Producto "a la Delorme" de digrafos por grafos. 2) Producto "de la casa" o cartesiano generalizado. Por ultimo veremos varias formas de mejorarlos (en el sentido de aumentar el orden).

Margarida Mitjana.

THE SPECTRA OF A VERTEX SYMMETRIC DIGRAPH.

(Dijous 29 d' Octubre de 1998, 12:00, Modul C3, Aula 005, Campus Nord, UPC)

Abstract. Cycle prefix digraphs are a family of vertex symmetric digraphs that can be defined as a digraphs on an alphabet. They exhibit some interesting properties that make them a good model for interconnection networks. In this very recent work, some new results referred to the spectra of the digraphs will be presented. In particular, the adjacency matrix of the digraph satisfies a matricial equation. Using such an equation, we will be able to find the eigenvalues of the digraph.

Miquel Angel Fiol.

GRAFOS, MATRICES Y GEOMETRIA.

SEMINARI LIMDA

(Dijous 05 de Novembre de 1998, 14:00, Modul C4, Aula 002, Campus Nord, UPC)

Abstract. Como es bien sabido, a través de la matriz de adyacencia A de un grafo G, es posible realizar una "aproximación algebraica" al estudio de sus propiedades estructurales. La idea es hacer uso de algunos invariantes de A, tales como su espectro, para deducir resultados sobre algunos parámetros (o, en último extremo, caracterizar) G. En este contexto pretendemos explicar dos cosas: 1. Describir algunos invariantes de A y, en su caso, discutir como están relacionados. 2. Comentar algunos resultados conocidos sobre G, que usan hacen uso de los invariantes anteriores. Gran parte de los conceptos y/o resultados expuestos tienen un carácter marcadamente geométrico, de manera que, en esta exposición, podríamos decir que el algebra de matrices es el puente que nos lleva de la teoria de grafos a la geometría.

José Luís Ruiz.

ON THE CONNECTED COMPONENTS OF GALOIS GRAPHS.

Autors: J.M. Brunat, J.L. Ruiz (MA2, UPC)

(Dijous 12 de Novembre de 1998, 12:00, Modul C3, Aula 005, Campus Nord, UPC)

Abstract. Let $\Phi(x,y)$ be a symmetric polynomial with coefficients in an algebraically closed field $K$ of characteristic zero. The \emph{Galois graph} $G(\Phi)$ is defined by taking the elements $j\in K$ as vertices and an ordered pair $(j_1,j_2)$ as an arc of multiplicity $n$ if $j_2$ is a root of $\Phi(j_1,y)$ of multiplicity $n$.
The following conjecture has been stated: all the connected components of a Galois graph are isomorphic except a finite number of them.
Our goal is to prove the conjecture for some classes of polynomials.
We give a complete description of the connected components of $G(\Phi)$ when $\Phi$ is a polynomial of degree 2 and also when $\Phi$ is an homogeneous polynomial of any degree. In both cases the conjecture holds.
A further question arises: given a graph $G$, is $G$ isomorphic to a connected component of $G(\Phi)$ for some $\Phi$? Let such a graph be called a \emph{polynomial graph.} We prove that any circulant graph is a polynomial graph. In particular, the complete graphs $K_n$, the bipartite complete graphs $K_{n,n}$ and the generalized complete cycles $C(n,k)$ are polynomial graphs.

Josep Fàbrega.

EXTRACONNECTIVITY OF DIGRAPHS.

Autors: C. Balbuena, J. Fàbrega, I. Pelayo

(Dijous 19 de Novembre de 1998, 12:00, Modul C3, Aula 005, Campus Nord, UPC)

Abstract. The $\eta$-extraconnectivity $\kappa_\eta$ [respectively, $\eta$-edge-extraconnectivity $\lambda_\eta$] of a simple strongly connected digraph is introduced as a kind of conditional connectivity that can be defined as the minimum number of vertices [respectively, directed edges] whose deletion leaves a nonstrongly connected subdigraph, but in such a way that all remaining nontrivial strongly connected components have more than $\eta$ vertices. For instance, the usual connectivity and superconnectivity [respectively, edge-connectivity and edge-superconnectivity] of a digraph correspond to $\kappa_0$ and $\kappa_1$ [respectively, $\lambda_0$ and $\lambda_1$].
To state precisely the meaning of these connectivities $\kappa_\eta$ and $\lambda_\eta$ for a given digraph $G$, the structure of $G-F$ or $G-A$, when $F$ or $A$ are respectively $\eta$-nontrivial disconnecting sets of vertices or edges with cardinalities $\kappa_\eta$ or $\lambda_\eta$, is studied. It is proved that an optimal lower bound for $\kappa_\eta$ and $\lambda_\eta$ is $\tau_\eta=(\eta+1)(\delta-1)$, a value that corresponds to the maximum cardinality of the neighbourhood of a directed cycle with $\eta+1$ vertices each one with out-degree $\delta$.
The main result of the work formulates sufficient conditions to guarantee that a given digraph $G$ is optimally $\eta$-extraconnected. These conditions are stated in terms of a new parameter $\ell_\eta$, related to the number of short paths between the vertices of $G$, and the diameter of the digraph. The sufficient conditions are also applied to iterated line digraphs, showing that if the iteration order is large enough and $\ell_\eta\ge\eta+1$, any iterated line digraph is optimally $\eta$-extraconnected. Finally, the results on iterated line digraphs are used to prove the optimallity of the extraconnectivity of some families of digraphs which have been considered as good models of interconnection networks, such as the dense bipartite digraphs $BD(d,n)$ and the generalized $p$-cycles.

Oriol Serra

A LOCAL-GLOBAL PRINCIPLE FOR MACAULAY POSETS

Autors: S. Bezrukov (Univ. Paderborn), X. Portas (UPC), and O.Serra (UPC).

(Dijous 26 de Novembre de 1998, 12:00, Modul C3, Aula 005, Campus Nord, UPC)

Abstract. Local-Global Principles were first established by Alswede and Cai with respect to submodular functions (in particular for the edge iosperimetric problem). The name refers to the fact that a property of the minimization problem which is satisfied by a structure $S$ and its square $S^2$ is then satisfied by all cartesian powers $S^n, n\ge 3$. We consider the vertex isoperimetric problem (which do not correspond to a submodular function). At the first stage, we consider the related shadow minimization problem (SMP) for cartesian powers $P^n$ of a Macaulay poset $P$. Our main result is a local-global principle with respect to the lexicographic order ${\cal L}^n$. Namely, we show that under certain conditions the shadow of any initial segment of the order ${\cal L}^n$ for $n\geq 3$ is minimal iff it is so for $n=2$. These conditions include such poset properties as {\it additivity\/}, {\it shadow increasing\/}, {\it final shadow increasing\/} and being {\it rank-greedy\/}. We also show that these conditions are essentially necessary for the lexicographic order to provide nestedness in the SMP. This is a joint work with S. Bezrukov (Univ. Paderborn) and X. Portas (UPC).

Carlos Domingo

(LSI, UPC)

PRACTICAL SAMPLING METHODS FOR DATA MINING

Autors: Carlos Domingo, Ricard Gavalda (UPC) and Osamu Watanabe (TIT, Tokyo)

SEMINARI LIMDA

(Dijous 03 de Desembre de 1998, 14:00, Modul C4, Aula 002, Campus Nord, UPC)

Abstract. With the recent increase in aplications of machine learning methods to knowledge discovery in large databases, what is commonly known as data mining, appropiate sampling methods are becoming increasingly important. The theoretical tools widely used in the learning theory and theoretical computer science community to calculate necessary sample sizes for estimating probabilities are the Chernoff and Hoeffding bounds. One usual criticism to these bounds is that either overestimate the sample size or assume the knowledge of parameters not known in real world problems.
In this talk, we will propose an alternative sampling method that, while keeping all the theoretical guarantees as the usual one, allows us to obtain more realistic sample size bounds and eliminate the dependence on unknown parameters. The main difference between our method and previous ones is that we do the sampling in an on-line fashion instead of the usual batch approach where the sample size is calculated a priori.
To illustrate the importance of the method, we will review several typical data mining problems (hypotheses or model selection, mining of association rules, subgroup discovery) where sampling is commonly used and show how our method can be applied. No previous knowledge of data mining, machine learning or databases is assumed.

Manuel Hernández, Jaume Sanz

(Grup d'Astronomia i Geodesia Espacial del Departament de Matemàtica Aplicada i Telemàtica, UPC)

RESEARCH ACTIVITIES  ON GPS AND NEURAL NETWORKS

(Dijous 17 de Desembre de 1998, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. (veieu http://maite152.upc.es/~manuel/gAGE5/gAGE5.html)

Carlos Andujar

(LSI, UPC)

VALIDITY-PRESERVING SIMPLIFICATION OF VERY COMPLEX POLYHEDRAL SOLIDS

SEMINARI LIMDA

(Dijous 14 de Gener de 1999, 14:00, Modul C4, Aula 002, Campus Nord, UPC)

Abstract. We introduce the Discretized Polyhedra Simplification (DPS), a framework for polyhedra simplification using space decomposition models. The DPS is based on a new error measurement and provides a sound scheme for error-bounded, geometry and topology simplification while preserving the validity of the model. A method following this framework,  Direct DPS, is presented and discussed. Direct DPS uses an octree for topology simplification and error control, and generates valid solid representations. Our method is also able to generate approximations which do not interpenetrate the original model, either being completely contained in the input solid or bounding it. Unlike most of the current methods, restricted to triangle meshes, our algorithm can deal and also produces faces with arbitrary complexity.

Victor Zinoviev

(Institute for Problems of Inform. Transmission, Russian Academy of Sciences)

ON THREE-REGULAR SUBGRAPHS OF FOUR-REGULAR GRAPHS

(Dijous 21 de Gener de 1999, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. The Berge-Sauer conjecture say that any simple 4-regular graph  contains a 3-regular subgraph. This conjecture was proved by Tashkinov in  1982. Then Alon-Friedland-Kalai in 1984 used the Chevalley-Warning theorem to extent this result for graphs which are 4-regular plus an edge. Our main result presents the sufficient condition for a 4-regular graph with multiple edges  to have a 3-regular subgraph. It gives the new 4-regular graphs with multiple edges which have no 3-regular subgraphs, for which we know exactly the  number of Euler orientatios.  A conjecture of Thomassen says that any 4-regular connected graph with multiple edges and loops has a 3-regular  subgraph, whenever the  number of vertices is even. We reduce this conjecture  to the same conjecture for graphs with only multiple edges.

Alexandre Nogué

SOBRE LA CAPACITAT DE SHANNON

(Dijous 4 de Febrer de 1999, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. Per conèixer el comportament de les transmissions de paraules  sobre un alfabet finit, construïm un graf associant un vèrtex a cada lletra i posant adjacències entre les lletres confonibles. En principi, el nombre d'independència podria semblar un paràmetre vàlid per mesurar aquest comportament, però no ho és quan la longitud dels missatges  es fa arbitrària: cal, doncs, definir un nou paràmetre (la capacitat  de Shannon).
A partir d'aquesta definició s'exposen diversos resultats que la  relacionen amb d'altres paràmetres ja coneguts com el nombre cromàtic  i els valors propis. Com a cas particular, calcularem la capacitat del pentàgon.

Ferran Hurtado

(MA2, UPC)

TRANSFORMACIONS ELEMENTALS D'OBJECTES GEOMETRICS

SEMINARI LIMDA

(Dijous 11 de Febrer de 1999, 14:00, Modul C4, Aula 002, Campus Nord, UPC)

Abstract. When two triangles which share an edge in a triangular decomposition of a planar domain form a convex quadrilateral, it is possible to replace the common diagonal by the other one in the quadrilateral, the resul being a new decomposition, nearly equal to the former, the only difference being this minimal change. This procedure,usually called {\sl edge flip}, is well known as a technique for local improvement in mesh generation. In a purely combinatorial graph, the flip consists of the suppression of an edge, followed by the introduction of a new one.
Given a set $P$ of $n$ points, it is possible to consider many geometric structures attached to this set, as well as many possible {\sl minimal changes} which can play the role of a flip operation.  Many abstract graphs can then be constructed (imagined) having a node for every state of the structure, edges corresponding to flips.
When the points are in convex position, the properties of these graphs depend usually only on $n$, and the problems are essentially combinatorial.  On the contrary, in general position the main problem is to study how the geometric properties of the set will translate into combinatorial properties of the graphs.
The flip can also be considered as a way for progressively transforming a structure, either for the optimization of some parameter or for enumerative or random generation purposes.
In this talk we describe some basic facts and variations about many of these problems, and make precise some of our results.

(This is a survey style talk, works were done with many different coauthors, with M. Noy and myself conducting the research)

José Gómez

UNA NUEVA FAMILIA DE GRAFOS DENSOS

(Dijous 18 de Febrer de 1999, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. Tras repasar algunas de las mejores familias de grafos sobre alfabeto densos, incluyendo los grafos compuestos generalizados, se presenta una nueva familia con buenas propiedades.

Pavol Hell

(Simon Fraser University)

GENERALIZATIONS OF MATCHING

(Dijous 25 de Febrer de 1999, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. There has been renewed interest recently in packing disjoint copies of graphs from a fixed family. (When the family has only one member, K_2, we have the matching problem.) I will first describe what was known about this problem in general, and then give the recent developments. Work of Kirkpatrick, Cornuejols, Pulleyblank, Hartvigsen, Loebl, Poljak, Kaneko, Brewster, Pantel, and the speaker will be mentioned.

Pavol Hell

(Simon Fraser University)

LIST PARTITIONS

SEMINARI LIMDA

(Dijous 4 de Març de 1999, 14:00, mòdul C4, aula 002, Campus Nord, UPC)

Abstract. I will describe a general model of a problem that includes many well known graph partition problems (split graphs, clique cutsets, homogeneous graphs, graph colourings and homomorphisms, skew cutsets, etc.). I will explain some polynomial and some quasi-polynomial algorithmic techniques that solve many problems of this type. In particular, a full classification is obtained for partitions with few parts, including the well known open problem of skew cutset. Some of the techniques use ideas from communication complexity. This is joint work with T. Feder, S. Klein, and R. Motwani.

Margarida Mitjana

PROPAGACIO D'INFORMACIO EN GRAFS I DIGRAFS QUE MODELEN XARXES D'INTERCONNEXIO SIMETRIQUES

TESI DOCTORAL

(Dijous 11 de Març de 1999, 12:00, Aula de Teleensenyament ETSETB, Edifici B3, Campus Nord, UPC)

Resum. En aquest treball s'ha aprofundit en diferents aspectes dels digrafs de prefix-cicle proposats com a model de xarxa d'interconnexió.
L'estudi s'ha dirigit bàsicament, a trobar noves propietats dels digrafs de prefix-cicle, estudiar-ne la descomposició en cicles, analitzar-ne l'espectre i a proposar algorismes eficients de comunicació.
Es dóna una nova manera de calcular la distància entre dos vèrtexs qualssevol del digraf. A partir d'aquest procediment, es determina el nombre de vèrtexs que hi ha a una certa distància d'un vèrtex donat, en funció del nombre de vèrtexs que hi havia a distàncies menors. Es defineixen els polinomis distància i recorregut, i s'estudia la relació que hi ha entre aquestes dues famílies de polinomis.
L'estudi de l'existència de cicles i la descomposició del digraf en cicles i camins, és el que ha aportat un major coneixement de l'estructura del digraf de prefix-cicle. S'ha pogut demostrar, gràcies a un nou mètode, que, de la mateixa manera que es compleix per als digrafs de Kautz, els digrafs de prefix-cicle són quasi pancíclics és a dir, contenen cicles de totes les longituds excepte l'ordre menys u.
S'ha obtingut també la descomposició del digrafs en cicles d'una mateixa longitud i es dóna també una descomposició del digraf en camins vèrtexs-disjunts, que permet, en el cas d'una xarxa modelada pel digraf, la distribució de tasques diferents entre grups d'usuaris de diferent nombre.
S'ha trobat que els digrafs de prefix-cicle tenen un estructura recursiva o jeràrquica que permet descomposar un digraf , en subdigrafs de la mateixa família però diàmetre menor.
Els resultats sobre cicles i la descomposició jeràrquica han estat determinants per a definir un algorisme eficient de difusió d'un missatge des d'un vèrtex qualsevol a tots els altres vèrtexs del digraf. Aquest esquema millora resultats previs i és òptim per a valors petits del grau.
Finalment, i fent ús del coneixement de l'estructura del digraf de prefix-cicle, s'ha demostrat que la matriu d'adjacència del digraf de prefix-cicle compleix una equació matricial similarment amb les equacions satisfetes per la matriu d'adjacència dels digrafs de de Bruijn i de Kautz. Aquest darrer resultat, permet calcular l'espectre dels digraf de prefix-cicle i comprovar que els valors propis només depenen del diàmete del digraf i no del grau.

Francisco Aguiló

DINAMIQUES DISCRETES SOBRE LES L-FORMES PLANES

(Dijous 18 de Març, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Resum. A partir de la classificació ja coneguda de les L-formes planes, es presenta una visió dinàmica (discreta) sobre elles. Es comenten resultats relacionats amb els conjunts "atractors" i com es comporten les "òrbites" generades per a una L-forma "inicial". Es comenten algunes aplicacions d'aquests resultats, referents a L-formes, sobre els digrafs de doble pas commutatiu i fix.

María José Serna

(LSI, UPC)

GRAPH LAYOUT PROBLEMS

SEMINARI LIMDA

(Dijous 8 d'Abril de 1999, 14:00, mòdul C4, aula 002, Campus Nord, UPC)

Abstract. Several optimization problems on graphs can be formulated as Layout problems, their goal is to find a linear ordering, or layout, of the nodes of a given graph in such a way that a certain function is minimized. The talk will survey some recent results on layout problems. Covering complexity results for some generalizations of the problem, experimental results on heuristics, and the analysis on random graphs, in particular random graphs in the Gn,p model, random lattice graphs and random geometric graphs.

Francesc Aguiló i Maria Lluïsa Fiol.

SUPERPOSICIO DE TESEL.LACIONS CONGRUENTS I PERIODIQUES COM A METODES DE DESCOMPOSICIO DE TESEL.LES D'IGUAL AREA

(Dijous 15 d' Abril, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Resum. Amb una certa freqüència, i especialment al càlcul d'àrees i volums d'objectes geomètrics, s'usa el mètode de descomposició: s'utilitzen puzzles dissenyats per a fer el càlcul a partir de figures més sencilles, en les quals l'àrea o el volum ja són coneguts. Presentem un nou mètode útil en la resolució de determinats problemes i/o en la demostració de teoremes. El mètode es basa en la superposició de mosaics congruents i periòdics. Aquest métode ens permet determinar puzzles a partir de les dues rajoles bàsiques d'igual àrea dels dos mosaics donats. El mètode resulta ser força àgil per a abordar de forma nova la demostració de teoremes antics i moderns, com ara, per exemple, el de Pitàgoras i els de Bolyai-Gerwin (1833) i Hadwiger-Glur (1951) sobre equidescomposicions de figures planas d'igual àrea.

Marc Noy.

ENUMERATION OF CROSSING AND NON-CROSSING CONFIGURATIONS

(Dijous 22 d' Abril, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. Crossing configurations (usually called chord diagrams or involutions without fixed points) are obtained by matching 2n points on a circle using n chords without common endpoints. Non-crossing configurations consist of any set of chords joining n points on a circle so that no two chords cross. The enumeration of such configurations is a classical topic in combinatorics and has been studied by Euler, Kirkman, Cayley and Schr\"oder among others, and more recently by Touchard, Riordan, Kreweras, Rogers and many others.
We present a systematic approach to these enumerative problems based on symbolic decompositions of combinatorial structures and on the analysis of generating functions. We obtain exact formulas (using Lagrange's inversion theorem), asymptotic estimates (by means of singularity analysis of generating functions) and limit probability laws for several parameters of interest (analyzing multivariate generating functions). The main parameters we consider in a configuration are the number of chords, the number of components, and the number of crossings.
The talk will be kept at a non technical level, emphasizing the nature of the results and the techniques used, rather than the proofs themselves. (This is joint work with Philippe Flajolet).

Francesc Antoni Muntaner.

ON EDGE MAGIC AND SUPER EDGE MAGIC GRAPHS

(Dijous 29 d' Abril, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. A graph G with order p and size q is edge magic if there exists a bijective function f:V(G) U E(G) ---->{1,2,...,p+q} such that f(u)+f(uv)+f(v) = k is constant, called the valence of f, for any edge uv of G. Moreover, G is said to be super edge magic, if f(V(G)) ={1,2,...,p}. Every super edge magic graf is known to be harmonious if q > p-2, sequential, cordial, antimagic, and sometimes admits an alfa valuation.
In this talk examples of families that admit edge magic and super edge magig labelings will be given, some properties of the valences will be discused, and some necessary and sufficient conditions for a graf to be edge magic will be presented.

Germán Sáez i Moreno

(MAiTE, UPC)

APLICACIONS DE LA COMBINATORIA A LA CRIPTOGRAFIA

SEMINARI LIMDA

(Dijous 6 de Maig de 1999, 14:00, mòdul C4, aula 002, Campus Nord, UPC)

Resum. En els darrers anys han aparegut diverses aplicacions de la Combinatòria a la Criptografia. Entre aquestes destaquen els esquemes per a compartir secrets. En un esquema per a compartir secrets es preten repartir un secret entre una sèrie de persones de forma que només determinades agrupacions puguin recuperar el secret. A més, la resta d'agrupacions no han de poder obtenir cap informaci ó sobre el valor del secret.
En aquest seminari presentem alguns resultats sobre taxa d'informació i detecció de tramposos en esquemes per a compartir secrets. Presentem també alguns problemes oberts relacionats amb aquests temes. Finalment, descrivim de manera breu altres àrees de la Criptografia en què la Combinatòria hi juga un paper destacat: les emissions xifrades, la computació multipart i els codis d'autentificació.

Xavier Marcote.

THE JORDAN NORMAL FORM OF A LINE DIGRAPH

(Dijous 13 de Maig, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. Let $G$ be a simple and finite digraph, and $A(G)$ its adjacency matrix. If $A(LG)$ is the adjacency matrix of the line digraph of $G$, we solve the problem of predicting the Jordan normal form of $A(LG)$ from the knowledge of the Jordan normal form of $A(G)$ under a few structural parameters related to $G$. More precisely, the Jordan normal form of a line digraph is found assuming that $\delta(G)\ge 1$. This condition can be relaxed to $\delta^+(G)\ge 1$ or $\delta^-(G)\ge 1$ when the geometric and algebraic multiplicities of zero are equal in $A(G)$. As an application, the Jordan normal form of a Kautz digraph $K(d,D)$ is obtained. Moreover, for any simple and finite digraph $G$, the relationship between characteristic polynomials of $A(G)$ and $A(LG)$ is derived as a natural consequence of the study of the spectra of these matrices. This fact has allowed to compare some properties of $G$ and $LG$ related to the set of directed cycles in these digraphs, as their girths, their d-girths, or their numbers of cycles of a certain length.

Erich Prisner.

(Mathematisches Seminar, Universitat de Hamburg)

GENERATING INTERCONNECTION NETWORKS VIA GRAPH OPERATORS

(Dimarts 18 de Maig, 15:30, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. The contents of the project is to
1) investigate generalizations of de Bruijn and Kautz networks--- underlying graphs of iterated line digraphs of general (noncomplete) graphs---as proposed in the Fiol, Yebra, Alegre 84-paper.
2) try another approach for generating large networks, one that is somewhat similar to the approach above, except that it avoids the bypass over directed graphs. Probabilistic results indicate that, for large networks, complete graphs seem to be the worst graphs to start with, therefore better networks than the deBruijn and Kautz networks should be possible with this approach. The project would also include theoretical work, as well as algorithms/experiments.

Carlos Seara.

SEPARABILIDAD DE OBJETOS EN EL PLANO

(Dijous 20 de Maig, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. Dados dos conjuntos de $N$ objetos del plano (clasificados como objetos rojos y objetos azules) queremos saber si son separables según diferentes criterios. El criterio más usual es la separabilidad lineal, es decir, existe una recta $l$ tal que los objetos rojos están en un semiplano definido por $l$ y los azules en el otro semiplano. El problema decisional de la separabilidad lineal es $O(N)$. Si los objetos no son linealmente separables se estudian otros criterios de separabilidad: separabilidad por cuña, por banda, por doble cuña, por $\Theta$-poligonal, etc.

Camino Balbuena.

DIAMETER VULNERABILITY OF GENERALIZED COMPOUND GRAPHS

(Dijous 27 de Maig, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. Fault tolerance concern in the design of interconnection networks has arisen interest in finding large graphs with maximum degree $\Delta$ and diameter $D$ such that the subgraphs obtained by deleting any set of up to $\delta-1$ vertices, where $\delta$ denotes the minimum degree, have diameter at most $D'$, being this value close to $D$ or even equal to it.
The Generalized compound graphs provide the best known values of the order for diameter not too small in general. In this paper it is studied the increasing of their diameter when one vertex is deleted. For it, three families of line digraphs are estudied. Their underlying graphs are shown $(\Delta,D,D,1)$-graphs, which are used to define the Generalized compound graphs in an alternative way. This fact allows to prove that most of the Generalized compound graphs are $(\Delta,D,D+1,1)$-graph.

Steve Skiena

(Dept. of Computer Science, State University of New York at Stony Brook)

JAI-TECHNOLOGY: COMPUTERS, GAMBLING, AND MATHEMATICAL MODELING TO WIN

SEMINARI LIMDA

(Dijous 3 de Juny de 1999, 14:00, mòdul C4, aula 002, Campus Nord, UPC)

Abstract. This talk describes a system that we have developed to predict the outcome of jai-alai matches (the Basque sport which you may know of as "cesta punta" or "pelota vasca"). It is legal to gamble on this sport in parts of the United States. I will describe the "Spectactular Seven" scoring system used in the United States, and how biases inherent in it can be exploited to profitably bet on it.

Miquel Angel Fiol

ALGEBRAIC CHARACTERIZATIONS OF DISTANCE-REGULAR GRAPHS.

FPSAC'99, INVITED LECTURE

(Dilluns 7 de Juny de 1999, 14:30, Sala d'Actes, ETSETB, UPC)

Abstract. We survey some old and some new characterizations of distance-regular graphs, which depend on information retrieved from their adjacency matrix.

Sonia Pérez Mansilla.

CONSTRUCTION OF k-ARC REGULAR DIGRAPHS

(Dijous 17 de Juny, 12:00, mòdul C3, aula 005, Campus Nord, UPC)

Abstract. A digraph is $k$--arc transitive if it has group of automorphisms which acts transitively on the set of $k$--arcs. Unlike the undirected case, in which cycles are the only $k$--edge transitive graphs for $k\geq 8$, there are $k$--arc transitive digraphs for every positive integer $k$. We show that every $r$-regular digraph admits for each positive integer $k$ a regular covering by an $k$-arc regular digraph. This is a generalization of a result by Babai (1985) which corresponds to the cases $k=0,1.$ The result provides a technique to construct $k$-arc regular digraphs from arbitrary regular digraphs. Some examples are given from complete graphs with and without loops.

---

updated by Roger Trias 1999/05/03