Seminar 2014-2015

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: http://www.iec.cat/

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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)

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.

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.