Skip to content

Seminar 2014-2015

(If you are using the Firefox web browser, you may need to reload the page to obtain its most recent version instead of the cache version.)

Sessions and activities

Thursday July 16, 2015, 12h
C3-Room 005, Campus Nord UPC

Edita Máčajová, Comenius University, Bratislava, Slovakia

Large cycles and matchings in cubic graphs

The Cycle Double Cover Conjecture claims that every bridgeless graph contains a family of cycles that together cover each edge exactly twice. This conjecture is equivalent to its restriction to the family of cubic graphs. The Fulkerson Conjecture asserts that any bridgeless cubic graphs contains a family of six perfect matchings that together cover every edge exactly twice.

We discuss old and new results and research directions on the way towards these long-standing conjectures. Our talk will include results concerning extensions, bipartizing matchings, Fano colourings, and others.


22nd International Colloquium on Structural Information and Communication Complexity

July 15-17, 2015
Montserrat, Spain

On Wednesday July 15, 14:30 - 15:20 Memorial Talk

Miquel Àngel Fiol

On the works of José Gómez. In memoriam.

Tuesday July 14, 2015, 12h
Sala d'Actes FME


Joan Vilaltella

Phd Defense: "Contributions to the theory of graph edge-coloring: snarks and multipoles"
Advisor: Miquel Àngel Fiol.

Monday July 6, 2015, 16h
Sala d'Actes FME

Elisabet Burjons

Master Thesis: "On-line Graph Coloring With Random Adversary"
Director: Xavier Muñoz


June 29 to July 3, 2015, CRM


Richard A. Brualdi, University of Wisconsin-Madison
Angeles Carmona Mejías, Universitat Politècnica de Catalunya-BarcelonaTech
Stephen J. Kirkland, University of Manitoba
Dragan Stevanovic, Serbian Academy of Sciences and Arts (SANU)
Pauline van den Driessche, University of Victoria

Workshop on Algebraic Combinatorics

18 June 2015 at Tilburg University, The Netherlands.

Invited speakers:

Aart Blokhuis - Technische Universiteit Eindhoven
Sebastian Cioaba - University of Delaware
Miquel Àngel Fiol - Universitat Politècnica de Catalunya
Monique Laurent - Centrum Wiskunde & Informatica Amsterdam/Tilburg University
Oriol Serra - Universitat Politècnica de Catalunya

Wednesday June 17, 15h30
Facultat de Filosofia (UB), 4th floor
Montalegre 6, Barcelona


Jordi López Abad, ICMAT-CSIC
Ramsey properties of finite dimensional normed spaces


June 8 to 12, 2015, CRM Barcelona





Thursday, June 11, 2015, 15:00-16:00

Room S215 Omega Building, Campus Nord UPC
(equiv.: Room 215 Floor -2)


Déborah Oliveros, Universidad Nacional Autónoma de México

Helly-type theorems and beyond


Prof. Déborah Oliveros is visiting the CRM and UPC in the “Lluís Santaló visiting program”, a program sponsored by the Institut d’Estudis Catalans:



The classical Helly’s Theorem 1913 is perhaps one of the most cited theorems in Discrete Geometry and has given rise to many generalizations and interesting problems. In the past ten years, there has been a significant increase in research activity and productivity in the area. In this talk we will give a survey on this topic and present some nice applications.



Tuesday, June 9, 2015, 15:00-16:00

Room S215 Omega Building, Campus Nord UPC
(equiv.: Room 215 Floor -2)

Birgit Vogtenhuber, Technische Universität Graz, Austria

Enumerating All Good Drawings of Small Complete Graphs



Good drawings (also known as simple topological graphs) are drawings of graphs such that any two edges intersect at most once. Such drawings have attracted attention as generalizations of geometric graphs, in connection with the crossing number, and as data structures in their own right. We are in particular interested in good drawings of the complete graph. In this work, we describe our techniques for generating all different weak isomorphism classes of good drawings of the complete graph for up to nine vertices. In addition, all isomorphism classes were enumerated. As an application of the obtained data, we present several existential and extremal properties of these drawings.


Wednesday, June 3, 2015
Seminar at CRM (Centre de Recerca Matemàtica)

Christos Papadimitriou, University of California, Berkeley
Complexity in Game Theory

How hard is it to find an equilibrium in a game or an economy? And how relevant can this question be to Game Theory and Economics?

I shall recount and reexamine a decade of progress and debate on these questions.
Wednesday May 27
Seminar at CRM

Paul Goldberg, Oxford University
Learning game-theoretic equilibria via query protocols

In the traditional model of algorithmically solving a game, the entire game is the "input data", which is presented in its entirety to an algorithm that is supposed to compute a solution, for example an exact/approximate Nash/correlated equilibrium. In some situations it may be preferable to regard the game as a "black box" which the algorithm can find out about via queries. For example, a complete description of a multi-player game may be infeasibly large. In this talk, we give an overview of recent work on algorithms that find game-theoretic equilibria via a sequence of queries that specify pure-strategy profiles, and answer with the associated payoffs. The main research issue is "query complexity", which refers to how many queries are needed in order to find a given kind of solution.

Thursday May 21, 12h
C3-Room 005, Campus Nord, UPC

Dieter Mitsche, Univ. Nice
On the bondage number of random graphs

A dominating set of a graph is a subset D of its vertices such that every vertex not in D is adjacent to at least one member of D. The domination number of a graph G is the number of vertices in a smallest dominating set of G. The bondage number of a nonempty graph G is the size of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. We study the bondage number of binomial random graph G(n,p). We obtain a lower bound that matches the order of the trivial upper bound. As a side product, we give a one-point concentration result for the domination number of G(n,p) under certain restrictions.

Joint work with X. Pérez-Giménez and P. Pralat.

Thursday May 7, 12h
C3-Room 005, Campus Nord, UPC

Ignasi Sau, CNRS-LIRMM Montpellier
The List Allocation problem and some of its applications in parameterized algorithms

In this talk we will sketch the main ideas of a Fixed-Parameter Tractable (FPT) algorithm for a quite general cut problem on general graphs, which we call List Allocation. Our algorithm strongly uses the "edge contraction" technique introduced by Chitnis et al. [2012]. Besides being a natural cut problem by itself, the relevance of List Allocation is best demonstrated by the following algorithms, which we obtain by reducing in FPT time each corresponding problem to particular cases of List Allocation:

(1) An FPT algorithm for a generalization of Digraph Homomorphism, which we call Arc-Bounded List Digraph Homomorphism.
(2) An FPT algorithm for a graph partitioning problem, called Min-Max Graph Partitioning.
(3) An FPT 2-approximation algorithm for computing the "tree-cut width" of a graph, a graph invariant recently introduced by Wollan [2013] and that has proved of fundamental importance in the structure of graphs not admitting a fixed graph as an immersion.

If time permits, we will partially discuss the above applications of our main algorithm. No previous knowledge of Paramerized Complexity will be assumed in the talk.

This is joint work with EunJung Kim, Sang-Il Oum, Christophe Paul, and Dimitrios M. Thilikos.

Thursday April 30, 12h
C3-Room 005, Campus Nord, UPC

Joaquim Bruna, UAB-CRM Barcelona

Un exemple de transferència en matemàtiques: què tenen a veure els encoders òptics amb els conjunts de Sidon, els Golomb rulers i l'autocorrelació discreta?

S'explicarà com la solució a un problema de tipus industrial proposat per una empresa al Servei de Consultoria del CRM es relaciona i serveix de nexe entre diferents camps de les matemàtiques, alguns d'ells molt treballats a nivell teòric. Això passa sovint en transferència, però en aquest cas- i això és més rar- s'explicarà com determinats teoremes de la teoria additiva de nombres mostren que la solució aportada pel CRM és òptima.

Thursday April 23, 12h

C3-Room 005, Campus Nord, UPC


Juraj Hromkovic, ETH Zurich

Towards a better understanding of the hardness of NP-hard optimization problems


We present the concept of the stability of approximation. The basic idea is to partition the set of the instances of a given hard optimization problem into infinitely many infinite classes with respect to the quality of efficiently achievable approximation. This approach enables to recognize classes of easy instances as well as to fix which kind of instances is really hard and whether the hard instances are more or few exotic or typical. In this way one revise the classification of the hardness of discrete optimization problems.




Thursday March 19, 12h
C3-Room 005, Campus Nord, UPC

Juanjo Rué, Freie Universitat Berlin
Arithmetic Removal Lemmas and Independent sets in hypergraphs

In the last years, several authors have studied sparse and random analogues of a wide variety of results in extremal combinatorics. Very recently, due to the work of Balogh, Morris, and Samotij, and the work of Saxton and Thomasson on the structure of independent sets on hypergraphs, several of these questions have been addressed in a new framework by using the so-called containers in hypergraphs.

In this talk I will present how to use this technology together with arithmetic removal lemmas due to Serra, Vena and Kral in the context of arithmetic combinatorics. We will show how to get sparse (and random) analogues of well-known additive combinatorial results even in the non-abelian situation.

This talk is based on a work in progress joint with Oriol Serra and Lluís Vena.

Thursday March 5, 12h
C3-Room 005, Campus Nord, UPC

Elisabet Burjons, UPC Barcelona
On-line graph coloring with random adversary

We introduce the concept of on-line algorithms under different models and assumptions, and in particular we consider the problem of on-line graph coloring. We show a new model consisting of infinite advice and random adversary and show upper and lower bounds for the expected competitive ratio in terms of the number of random bits the adversary accesses.

This is joint work with Juraj Hromkovič, Xavier Muñoz and Walter Unger.




Wednesday February 25, 12h
Sala d'Actes de l'FME

Lectura de la tesi doctoral d'Aaron Dall
Matroids: h-vectors, zonotopes, and Lawrence polytopes

El principal objeto de estudio de la presente tesis son las matroides, que generalizan propiedades de matrices a un contexto más combinatorio. Nos interesaremos principalmente por tres clases particulares: matroides regulares, matroides aritméticas, y matroides internamente perfectas. De estas famílias, las matroides regulares son las mejor estudiadas. En cambio, las matroides aritméticas son estructuras relativamente nuevas que capturan simultáneamente invariantes combinatorias y geométricas de configuraciones racionales de vectores. Introducimos en esta tesis la clase de matroides internamente perfectas, que nos permiten usar la estructura del orden interno de dichas matroides para probar, en este caso y suponiendo la veracidad de una afirmación, la conjetura de Stanley que cualquier h-vector de una matroide es una O-secuencia pura. Esta tesis está estructurada de la siguiente forma. En el Capítulo 1 damos los antecedentes relevantes. En el Capítulo 2 ofrecemos una nueva demostración de una generalización del teorema de Kirchhoff. Después reestructuramos el problema en el mundo de la geometría poliédrica a través de dos zonotopos determinados por una matroide regular, demostrando que los volúmenes de estos zonotopos son iguales, y construyendo una biyección explícita entre ellos (fuera de un conjunto de medida cero). Generalizamos entonces al caso de una matroide con pesos. Concluimos mostrando que nuestra técnica pude ser usada para volver a demostrar el teorema clásico de Kirchhoff, puliendo los detalles cuando las matrices tienen corrango igual a uno. Este capítulo es fruto de trabajo conjunto con Julian Pfeifle. En el Capítulo 3 sacamos provecho de una conexión entre el zonotopo y el politopo de Lawrence generado por una representación íntegra (con coeficientes enteros) de una matroide racional para probar relaciones entre varios polinomios asociados con ellos. Primero demostramos una relación entre el polinomio de Ehrhart del zonotopo y el numerador de la serie de Ehrhart del politopo de Lawrence. Al nivel de matroides aritméticas esta relación nos permite ver el numerador de la serie de Ehrhart del politopo de Lawrence como el análogo, para matroides aritméticas, del usual h-vector de la matroide. Después de demostrar el resultado mencionado, lo usamos para ofrecer una nueva interpretación de los coeficientes de una evaluación particular del polinomio aritmético de Tutte. Finalmente mostramos que el h-vector de la matroide y la serie de Ehrhart del politopo de Lawrence coinciden cuando la representación es unimodular. En el Capítulo 4 consideramos una nueva clase de matroides, cuyo orden interno las vuelve especialmente dispuestas para demostrar la conjetura de Stanley. Esta conjetura dice que para cualquier matroide existe un ideal de orden puro cuya O-secuencia coincide con el h-vector de la matroide. Damos un breve repaso de los resultados conocidos en la Sección 4.1 antes de enfocarnos en las matroides ordenadas y el orden interno en la Sección 4.2, donde también definimos las bases y matroides internamente perfectas. En la Sección 4.3 probamos resultados preliminares sobre bases internamente perfectas culminando en el Teorema 4.11, dónde mostramos que, suponiendo la veracidad de cierta afirmación, cualquier matroide perfecta satisface la conjetura de Stanley. Por otra parte, conjeturamos que esta afirmación, en efecto, es válida para todas las matroides internamente perfectas.


Thursday February 19, 2015, 17h15
C3-Room 005, Campus Nord, UPC

Jaroslav Nešetřil, IUUK MFF, Charles University Prague
Sparsity and fast algorithms for combinatorial problems

Combinatorial problems model many important situations from both theoretical and applied computer science. To find broad classes of problems which can be effectively solved is of prime importance which leads to several popular dichotomies.

In the lecture we survey the recent actual development from the point of view sparse vs dense dichotomy.

(Joint work with P. Ossona de Mendez -Paris and Prague.)


Thursday February 19, 12h
C3-Room 005, Campus Nord, UPC

Jarek Grytczuk, Jagiellonian University in Krakow
Fanciful variations on non-repetitiveness


A repetition is a finite sequence whose first half looks exactly the same as the second half. For instance, aa, abab, abcabc, abacabac are repetitions. A sequence is nonrepetitive if it does not contain any repetitions (as subsequences of consecutive terms). In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences built of only three symbols. This result initiated lots of research leading to deep results, important applications, and interesting generalizations in different areas of mathematics and computer science. In the talk I will present some problems inspired by the theorem of Thue for various combinatorial structures. Here is a new one for example: suppose that we are given a finite set of lines in the plane and we want to color all intersection points of these lines so that there is no repetition on any line. How many colors are needed? It can be proved that 405 colors suffice, but it does not seem optimal.


Thursday February 19, 11h
C3-Room 005, Campus Nord, UPC

Aida Abiad, Tilburg University, The Netherlands
Switched symplectic graphs and their 2-ranks

We apply Godsil-McKay switching to the symplectic graphs over F_2 with at least 63 vertices and prove that the 2-rank of (the adjacency matrix of) the graph increases after switching. This shows that the switched graph is a new strongly regular graph with the same parameters as the symplectic graph over F_2 but different 2-rank.

For the symplectic graph on 63 vertices we investigate repeated switching by computer and find many new strongly regular graphs with the same parameters but different 2-ranks.

By using these results and a recursive construction method for the symplectic graph from Hadamard matrices, we also obtain several graphs with the same parameters as the symplectic graphs over F_2, but different 2-ranks.

This is joint work with Willem Haemers.


Thursday November 20, 2014, 12h
C3-Room 005, Campus Nord, UPC

Simeon Ball, UPC Barcelona
Applications of the polynomial method in combinatorial geometry to Kakeya and Bourgain sets

In recent years significant advances have been made in the application of algebraic methods to finite geometrical objects, see the recent survey by Tao [1]. Whether these objects are in real, finite or complex space, the finiteness of the object allows for some combinatorial methods to be used. Combining these with algebraic methods, most notably from algebraic geometry, one can hope to obtain theorems concerning the geometrical object under consideration.

In this talk I will consider Kakeya sets and Bourgain sets.

Let F be a field and let AG_k(F) denote the k-dimensional affine space over F. Let F_q denote the finite field with q elements.

A Kakeya set in AG_n(F) is a set L of lines with the property that L contains no two lines with the same direction. I will explain an iterative geometric construction of Kakeya sets in AG_n(F) starting from a Kakeya set in AG_2(F). I will say something about Dvir's proof (from [2]) that if L is a Kakeya set in AG_n(F) which contains a line in every direction then there is a constant c=c(n) such that if S is the set of points incident with some line of L then |S|>cq^n.

A Bourgain set in AG_n(F) is a set L of lines with the property that a plane contains few lines of L. Amongst other things I will sketch Guth and Katz's proof [3] that if L is a set of N^2 lines in AG_3(R), with at most N contained in any plane, and S is a set of points with the property that every line of L is incident with at least N points of S then there is a constant c such that |S|>cN^3.

Furthermore, I will talk about Ellenberg and Hablicsek's article [2] on the finite analogue of this in which L is a set of aq^2 lines in AG_3(F_q) with at most bq lines in a plane, for some constant b. They prove that if q is prime then there is a constant c=c(a,b) such that if S is the set of points incident with some line of L then |S|>cq^3. This does not hold true over non-prime finite fields and we shall also consider this finite non-prime case. I will also detail some results about Bourgain sets in higher dimensions.

[1] Zeev Dvir, On the size of Kakeya sets in finite fields, arXiv:0803.2336v3.
[2] Jordan S. Ellenberg and Márton Hablicsek, An incidence conjecture of Bourgain over fields of positive characteristic, arXiv:1311.1479v1.
[3] Larry Guth and Nets Hawk Katz, Algebraic methods in discrete analogs of the Kakeya problem, Adv. Math., 225 (2010), 2828--2839.
[4] Terence Tao, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory, arXiv:1310.6482v5.

Thursday October 30, 2014, 12h
C3-Room 005, Campus Nord, UPC

Klara Stokes, University of Skövde
Pentagonal maps of Moore graphs and geometric pentagonal geometries

A map is a drawing of a graph on a Riemann surface such that the complement of the drawing is the disjoint union of finitely many topological discs called faces. It will be explained how to construct geometric point-circle configurations embedded on Riemann surfaces from uniform maps. In particular, geometric realizations of all pentagonal geometries with k lines through each point and either k or k-1 points on each line can be obtained in this way. All these pentagonal geometries come from Moore graphs. Therefore this work involves a study of maps of Moore graphs. In particular we give the minimum genus of the Hoffman-Singleton graph.




Thursday October 23, 2014, 12h

C3-Room 005, Campus Nord, UPC

Francesc Aguiló, UPC Barcelona
Some Structural Properties of optimal diameter 2-Cayley digraphs on finite abelian groups

Given a Cayley digraph G of degree two on a finite Abelian group, we study optimal structural properties related with the diameter. We call such a digraphs 2-Cayley digraphs. An expansion of G is a 2-Cayley digraph G' with the same generating set, that contains an isomorphic copy of G. A contraction of G is a 2-Cayley digraph G'' contained in G. Optimal digraphs that attain the diameter lower bound are called tight digraphs.

In this work we define two processes for obtaining contractions and expansions of 2-Cayley digraphs. These definitions are well suited from the metrical point of view. In particular, a contraction of an optimal diameter digraph has also optimal diameter. This is not true for expansions. Tight expansions from tight digraphs are characterized. Tight 2-Cayley digraphs having infinite tight expansions are also analized.

Joint work with A. Miralles and M. Zaragozá.



Thursday October 16, 2014, 12h
C3-Room 005, Campus Nord, UPC

Miquel Àngel Fiol, UPC Barcelona
Distance-regular graphs where the distance-d graph has fewer distinct eigenvalues

Let the Kneser graph K of a distance-regular graph Γ be the graph on the same vertex set as Γ, where two vertices are adjacent when they have maximal distance in Γ. We study the situation where the Bose-Mesner algebra of Γ is not generated by the adjacency matrix of K. In particular, we obtain strong results in the so-called 'half-antipodal' case.

(joint work with A.E. Brouwer)




Thursday October 9, 2014, 12h

C3-Room 005, Campus Nord, UPC

Felix Lazebnik, University of Delaware
On Graphs Defined by Some Systems of Equations

In this talk I will present a simple method for constructing infinite families of graphs defined by a class of systems of equations over commutative rings. The graphs in all such families possess some general properties including regularity or bi-regularity, existence of special vertex colorings, and existence of covering maps between every two members of the same family (hence, embedded spectra). Another general property is that nearly every graph constructed in this manner edge-decomposes either the complete, or complete bipartite, graph which it spans.

In many instances, specializations of these constructions have proved useful in various graph theory problems, but especially in many extremal problems which deal with cycles in graphs. I will explain motivations for these constructions, survey both old and new related results, applications, and state open questions.




Thursday October 2, 2014, 12h
C3-Room 005, Campus Nord, UPC

José Aliste-Prieto, Universidad Andrés Bello, Santiago de Chile

Recognizing caterpillars by U-polynomials

En este trabajo con J. Zamora, estudiamos como reconocer grafos tipo orugas a partir de los U-polinomios. Usando su estructura lineal, relacionamos una versión restringida del U-polinomio con una función de Schur naturalmente asociada con composiciones de enteros. Luego usamos la clasificación de equivalencias de dichas funciones de Schur para mostrar que dos orugas tendrán el mismo U-polinomio si y solo si son isomorfas.