2014-15 LIMDA Seminar

Abstract: 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.

Date: May 21st 2015

Speaker: Dieter Mitsche, Univ. Nice

Title: On the bondage number of random graphs

 

Abstract: 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.

____________________________ 
Date: May 7th 2015
Speaker: Ignasi Sau, CNRS-LIRMM Montpellier

Title: The List Allocation problem and some of its applications in parameterized algorithms

Abstract: 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.

____________________________ 
Date: April 23rd 2015

Speaker: Juraj Hromkovic, ETH Zurich

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

Abstract: 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.

 Date: March 19th 2015

Speaker: Juanjo Rué, Freie Universitat Berlin

Title: Arithmetic Removal Lemmas and Independent sets in hypergraphs

Abstract: 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.

____________________________ 

Date: March 5th 2015
Speaker: Elisabet Burjons, UPC Barcelona

Title: On-line graph coloring with random adversary

Abstract: 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.

____________________________  

Date: February 19th 2015

Speaker: Jaroslav Nešetřil, IUUK MFF, Charles University Prague

Title: Sparsity and fast algorithms for combinatorial problems 

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

Date: February 19th 2015
Speaker: Jarek Grytczuk, Jagiellonian University in Krakow

Title: Fanciful variations on non-repetitiveness

 

Abstract: 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.

____________________________    

Date: February 19th 2015
Speaker: Aida Abiad, Tilburg University, The Netherlands

Title: Switched symplectic graphs and their 2-ranks

 

Abstract: 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.

____________________________    
Date: November 20th 2014

Speaker: Simeon Ball, UPC Barcelona

Title: Applications of the polynomial method in combinatorial geometry to Kakeya and Bourgain sets

 

Abstract: 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.

____________________________    
Date: October 30th, 2014
Speaker: Klara Stokes, University of Skövde

Title: Pentagonal maps of Moore graphs and geometric pentagonal geometries

 

Abstract: 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.

____________________________  

 Date: October 23rd 2014

Speaker: Francesc Aguiló, UPC Barcelona

Title: Some Structural Properties of optimal diameter 2-Cayley digraphs on finite abelian groups

 

Abstract: 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á.

 Date: October 16th 2014

Speaker: Miquel Àngel Fiol, UPC Barcelona

Title: Distance-regular graphs where the distance-d graph has fewer distinct eigenvalues

Abstract: 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)

____________________________  

 Date: October 9th 2014

Speaker: Felix Lazebnik, University of Delaware

Title: On Graphs Defined by Some Systems of Equations

 

Abstract: 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.

____________________________   

Date: October 2nd 2014

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

Title: Recognizing caterpillars by U-polynomials

 

Abstract: 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.