# Seminar 2014-2015

## 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**

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

SIROCCO 2015

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.On the works of José Gómez. In memoriam.

**Joan Vilaltella**

**"Contributions to the theory of graph edge-coloring: snarks and multipoles"**

**Advisor: Miquel Àngel Fiol.**

**Elisabet Burjons**

**"On-line Graph Coloring With Random Adversary"**

**Director: Xavier Muñoz**

###### ADVANCED COURSE ON COMBINATORIAL MATRIX THEORY

June 29 to July 3, 2015, CRM

http://www.crm.cat/en/Activities/Curs_2014-2015/Pages/Combinatorial-Matrix-Theory.aspx

*Speakers:*

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 http://www.win.tue.nl/~aartb/ - Technische Universiteit Eindhoven

Sebastian Cioaba http://www.math.udel.edu/~cioaba/ - University of Delaware

Miquel Àngel Fiol http://www-ma4.upc.edu/~fiol/ - Universitat Politècnica de Catalunya

Monique Laurent http://homepages.cwi.nl/~monique/ - Centrum Wiskunde & Informatica Amsterdam/Tilburg University

Oriol Serra http://www-ma4.upc.edu/~oserra/ - Universitat Politècnica de Catalunya

http://workshoponalgebraiccombinatorics2015.weebly.com/

Wednesday June 17, 15h30

Facultat de Filosofia (UB), 4th floor

Montalegre 6, Barcelona

SET THEORY SEMINAR

**Jordi López Abad, ICMAT-CSIC**

###### Ramsey properties of finite dimensional normed spaces

###### WORKSHOP ON STRATEGIC BEHAVIOR AND PHASE TRANSITIONS IN RANDOM AND COMPLEX COMBINATORIAL STRUCTURES

June 8 to 12, 2015, CRM Barcelona

http://www.crm.cat/en/Activities/Curs_2014-2015/Pages/Strategic-Behaviour.aspx

COMPUTATIONAL GEOMETRY SEMINAR

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

*Abstract:*

COMPUTATIONAL GEOMETRY SEMINAR

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

*Abstract:*

Wednesday, June 3, 2015

Seminar at CRM (Centre de Recerca Matemàtica)

**Christos Papadimitriou, University of California, Berkeley**

###### Complexity in Game Theory

I shall recount and reexamine a decade of progress and debate on these questions.

Seminar at CRM

**Paul Goldberg, Oxford University**

###### Learning game-theoretic equilibria via query protocols

Thursday May 21, 12h

C3-Room 005, Campus Nord, UPC

**Dieter Mitsche, Univ. Nice**

###### On the bondage number of random graphs

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

(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**

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 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

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.

###### Joint ALBCOM/COMBGRAPH Seminar

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

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

Thursday February 19, 11h

**C3-Room 005, Campus Nord, UPC**

**Aida Abiad, Tilburg University, The Netherlands**

###### Switched symplectic graphs and their 2-ranks

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 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

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

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

*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 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**