# Seminar 2011-2012

Sessions and Abstracts

*Unless otherwise stated, all sessions take place at C3-Room 005, Campus Nord, UPC.*

## Sessions

Monday July 23, 11h

Conference Room of ETSECCPB (2nd floor, room C2 212)

###### The Inverse Problem on finite networks

Ph.D. Thesis proposal**Cristina Araúz Lombardía**

Thesis advisors: Ángeles Carmona Mejías and Andrés M. Encinas Bachiller

Friday June 22, 12h

##### On the largest tournament Maker can build

**Anita Liebenau (TU Berlin)**

*Abstract:*

In the k-tournament game, the two players, called Maker and Breaker, alternately claim and direct edges from the complete graph K_n on n vertices. At the beginning of the game, Breaker chooses a goal tournament T (an orientation of the complete graph) on k vertices. Maker wins the game if her digraph contains a copy of T.

In 2008, Beck showed that the largest undirected clique Maker can build is of order k_c = (2-o(1)) log n. Based on a "random graph intuition" he conjectured that the largest k_t such that Maker wins the k_t-tournament game is of order k_t = (1-o(1)) log n.

Given n large enough, we show that Maker wins the k-tournament game for k = (2-o(1)) log n = k_c - 10. That is, building a tournament is almost as easy for Maker as building an undirected clique.

In the talk, I will explain the necessary background from positional games, the random graph intuition, and how it relates to our result.

Joint work with Dennis Clemens and Heidi Gebauer.

In 2008, Beck showed that the largest undirected clique Maker can build is of order k_c = (2-o(1)) log n. Based on a "random graph intuition" he conjectured that the largest k_t such that Maker wins the k_t-tournament game is of order k_t = (1-o(1)) log n.

Given n large enough, we show that Maker wins the k-tournament game for k = (2-o(1)) log n = k_c - 10. That is, building a tournament is almost as easy for Maker as building an undirected clique.

In the talk, I will explain the necessary background from positional games, the random graph intuition, and how it relates to our result.

Joint work with Dennis Clemens and Heidi Gebauer.

Thursday June 21, 11h30

Sala de Graus, Campus de Cappont

Universitat de Lleida (UdL)

#### Special session in memory of Joan Gimbert

11h30

##### Welcome

11h45

##### Les aportacions de Joan Gimbert a la teoria de grafs

**Josep Conde i Nacho López (UdL)**

12h30

##### The contribution of Joan Gimbert to the degree/diameter problem

**Dominique Buset (Université Libre de Bruxelles)**

Thursday June 14, 12h

##### Polytopes of degree 1

**Arnau Padrol (UPC, Barcelona)**

Abstract:

Abstract:

The combinatorial degree of a polytope is the maximal codimension of one of its interior faces. This definition is motivated from a corresponding Ehrhart-theoretic notion for lattice polytopes.

We will use Gale duality to prove that the only polytopes of combinatorial degree 1 are k-fold pyramids over polygons and k-fold pyramids over prisms over simplices.

We will use Gale duality to prove that the only polytopes of combinatorial degree 1 are k-fold pyramids over polygons and k-fold pyramids over prisms over simplices.

Thursday June 7, 12h

##### An alternative way to generalize the pentagon

**Simeon Ball, UPC Barcelona**

(joint work with John Bamberg, Alice Devillers and Klara Stokes)

*Abstract:*

We introduce the concept of a pentagonal geometry as a generalisation of the pentagon and the Desargues configuration, in the same vein that the generalised polygons share the fundamental properties of ordinary polygons. In short, a pentagonal geometry is a regular partial linear space in which for all points x, the points not collinear with the point x, form a line.

In the talk we will see some constructions of pentagonal geometries, obtain some non-existence results for seemingly feasible parameters and suggest a cryptographic application related to identifying codes of partial linear spaces.

I will also offer a prize to the first person to construct a pentagonal geometry with at least four points on a line with a connected deficiency graph.

In the talk we will see some constructions of pentagonal geometries, obtain some non-existence results for seemingly feasible parameters and suggest a cryptographic application related to identifying codes of partial linear spaces.

I will also offer a prize to the first person to construct a pentagonal geometry with at least four points on a line with a connected deficiency graph.

Thursday May 31, 12h

###### A short proof of the odd-girth theorem

**Miquel Àngel Fiol, UPC Barcelona**

*Abstract:*

Recently, it has been shown that a connected (but not necessarily regular) graph $G$ with $d+1$ distinct eigenvalues and odd-girth $2d+1$ is distance-regular. The proof of this result was based on two versions of the spectral excess theorem. In this talk we present an alternative and more direct proof which does not rely on the spectral excess theorem, but on a known characterization of distance-regular graphs in terms of the predistance polynomial of degree $d$.

(joint work with E.R. van Dam)

(joint work with E.R. van Dam)

Thursday May 24, 12h

###### Polarity graphs and other $C_4$-free graphs of large size

**Camino Balbuena, UPC Barcelona**

*Abstract:*

We give a method for obtaining first a projective plane of order $q$ and second the adjacency matrix of the polarity graphs of order $q$ where $q$ is a prime power. Then, we apply this result to obtain some lower bound on the extremal function $ex(n; C_4 )$, that is, the maximum number of edges of a graph free of squares.

Among other results we obtain the adjacency matrix of a $C_4$-free graph on $n=q^2-\sqrt{q}$ vertices and $\frac{1}{2} q(q^2-1)-\frac{1}{2}\sqrt{q} (q-1)$ edges when $q$ is a square prime power.

Joint work with M. Abreu and D. Labbate.

Thursday May 3, 12h

###### Locally identifying colourings of graphs

**Aline Parreau, University Joseph Fourier of Grenoble**

*Abstract:*

We introduce the notion of locally identifying colourings of graphs. A proper colouring of vertices is said to be locally identifying if for any adjacent pair of vertices u and v, the set of colours in their closed neighborhood are distinct.

In this talk, we will present different results on these colorings in different classes of graphs, in particular in subclasses of perfect graphs and in planar graphs. We will also show that a graph with maximum degree D has a locally identifying coloring with O(D^2) colours.

Thursday April 26, 12h

###### Huge locating dominations of graphs

**Iñaki Pelayo, UPC, Barcelona**

Abstract:

Abstract:

A vertex v in a graph G=(V,E) is dominated (resp. totally dominated) by a subset S of vertices if the closed (resp. open) neighborhood of v intersects S.

A dominating set is called locating-dominating (resp. distinguishing-dominating or simply identifying) if distinct vertices not in S (resp. in V) are dominated by distinct subsets of S. Similarly, a total dominating set is locating-total dominating (resp. distinguishing-total dominating) if distinct vertices not in S (resp. in V) are totally dominated by distinct subsets of S.

In this talk we will survey a number of basic properties related to these sets, such as exact values of basic graph families, general bounds, extremal values and bounds for trees. We will also show some of our most recent contributions to this subject, including a Nordhaus-Gaddum type result for the locating-dominating number, which is the minimum cardinality of a locating-dominating set.

Joint research work with Carmen Hernando and Mercè Mora.

A dominating set is called locating-dominating (resp. distinguishing-dominating or simply identifying) if distinct vertices not in S (resp. in V) are dominated by distinct subsets of S. Similarly, a total dominating set is locating-total dominating (resp. distinguishing-total dominating) if distinct vertices not in S (resp. in V) are totally dominated by distinct subsets of S.

In this talk we will survey a number of basic properties related to these sets, such as exact values of basic graph families, general bounds, extremal values and bounds for trees. We will also show some of our most recent contributions to this subject, including a Nordhaus-Gaddum type result for the locating-dominating number, which is the minimum cardinality of a locating-dominating set.

Joint research work with Carmen Hernando and Mercè Mora.

Thursday March 22, 12h

###### Strongly regular graphs

**Andriy Bondarenko, CRM (Barcelona)**

*Abstract:*

We will discuss recent results and open problems on strongly regular graphs.

Special attention will be paid to the Euclidean representation of strongly regular graphs.

In particular we will outline the proof of the following our results:

There is no strongly regular graph with parameters (289,54,1,12);

there is a unique strongly regular graph with parameters (729,112,1,20) (the Games graph).

Special attention will be paid to the Euclidean representation of strongly regular graphs.

In particular we will outline the proof of the following our results:

There is no strongly regular graph with parameters (289,54,1,12);

there is a unique strongly regular graph with parameters (729,112,1,20) (the Games graph).

Thursday March 15, 12h

###### Testing function isomorphism

**David García, CWI Amsterdam**

*Abstract:*

We study the problem of isomorphism (equivalence up to relabelling of the input variables) between two boolean functions $f,g:\{0,1\}^n \to \{0,1\}$ under the property testing framework (or, what amounts to the same thing, testing isomorphism between general hypergraphs). In the most widely studied variant of the problem, g is known and the algorithm has black-box access to f. We present a series of recent results establishing nearly tight worst-case query-complexity bounds for the problem, as well as some progress towards the research goal of characterizing the functions g to which isomorphism can be tested with O(1) queries.

Our results also have applications to a number of other property testing problems, in particular those of testing for ``concise representations'' in the sense of Diakonikolas et al. (FOCS 2007), such as having low Fourier degree or circuits of small size. Namely, the existing upper bounds can be improved via the construction of ``sample extractors'', and new or sharper lower bounds for these problems can be derived from our lower bounds for testing isomorphism.

Based on joint work with Sourav Chakraborty, Eldar Fischer and Arie Matsliah.

Thursday March 8, 12h

###### Moments in graphs

**Miquel Àngel Fiol, UPC, Barcelona**

*Abstract:*

Let $G$ be a connected graph with vertex set $V$ and a {\em weight function} $\rho$ that assigns a nonnegative number to each of its vertices. Then, the {\em $\rho$-moment} of $G$ at vertex $u$ is defined to be

$M_G^{\rho}(u)=\sum_{v\in V} \rho(v)\dist (u,v)$,

where $\dist(\cdot,\cdot)$ stands for the distance function. Adding up all these numbers, we obtain the {\em $\rho$-moment of $G$}:

$$

M_G^{\rho}=\sum_{u\in V}M_G^{\rho}(u)

=\frac{1}{2}\sum_{u,v\in V}\dist(u,v)[\rho(u)+\rho(v)].

$$

This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the {\em Wiener index} $W(G)$, when $\rho(u)=1/2$ for every $u\in V$, and the {\em degree distance} $D'(G)$, obtained when $\rho(u)=\delta(u)$, the degree of vertex $u$.

In this talk we derive some exact formulas for computing the $\rho$-moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding $\rho$-moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same $\rho$-moment (and, hence, with equal mean distance, Wiener index, degree distance, etc). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product.

Joint work with C. Dalfó and E. Garriga

Thursday February 23, 12h

###### Many neighborly polytopes

**Arnau Padrol, UPC Barcelona**

*Abstract:*

We say that a d-polytope P is neighborly if every subset of at most d/2 vertices is a face of P. We present a new construction that uses Gale duality to build many neighborly polytopes. With it, we can prove that the number of different neighborly d-polytopes with n vertices is at least of order n^(nd/2), which even improves previously known lower bounds for the number of different combinatorial types of polytopes (not necessarily neighborly!).

Thursday February 16, 12h

###### Graphs and Matrices with Integral Spectrum in Some Families

**Igor Shparlinsky, Department of Computing, Macquarie University, Australia**

*Abstract:*

We give a survey of recent results about counting of graphs and matrices (of various types) with integral eigenvalues. This question leads to several other natural counting problems (for example, counting singular matrices in some families). We also pose several open problems.

Thursday February 9, 12h

###### Consecutive patterns in permutations: clusters, generating functions and asymptotics

**Marc Noy, UPC, Barcelona**

*Abstract:*

Given a sequence of distinct positive integers s = s_1,...,s_k, the reduction st(s) is the permutation of length k obtained by relabelling the elements of s with {1,...,k} so that the order relations among the elements remains the same. For instance, st(46382) = 34251. A permutation p of length n contains a permutation \sigma of length m as a consecutive pattern if st(p_i...p_{i+m-1}) = \sigma for some i in {1,...,n-m+1}. Two permutations \sigma and \tau of the same length are called Wilf-equivalent if for all n the number of permutations of length n avoding \sigma is the same as the number of permutations avoiding \tau. We use the cluster method of Goulden and Jackson in order to enumerate permutations avoiding consecutive patterns. We reprove and generalize in a unified way several known results and obtain new results on certain patterns. Among others we solve completely the patterns 1324, 123...(s-1)(s+1)s(s+2)(s+3)...(2s), and 134...(s+1)2(s+2)(s+3)...(2s), for s > 2. We also prove several conjectures of Nakamura on Wilf-equivalence of several patterns. Finally we prove that the monotone pattern dominates asymptotically all non-overlapping patterns of the same length, thus proving a conjecture of Elizalde and Noy for a positive fraction of all patterns. This is joint work with Sergi Elizalde.

Thursday January 26, 12h

###### On a conjecture of Erdös, Faber and Lovász

**David Romero, Instituto de Matemáticas, UNAM, Cuernavaca, México**

*Abstract:*

La conjetura de Erdös-Faber-Lovasz tiene 40 años y muy pocos avances. El mismo Paul Erdös la consideraba uno de sus tres problemas favoritos y se puede plantear así: dado un hipergrafo

*H*donde cada una de sus*n*aristas tiene exactamente*n*vértices, y tal que dos aristas cualquiera se interceptan en cuando más un vértice, es posible encontrar una*n*-coloración de los vértices de*H*de modo que ninguna arista de*H*tenga dos vértices del mismo color. Se presenta un caso especial donde la conjetura es cierta.Thursday January 12, 12h

###### Algunos resultados en teoría anti-Ramsey aritmética

**Amanda Montejano, Centro de Física Aplicada y Tecnología Avanzada, UNAM, Mexico**

*Abstract:*

Mientras la teoria de Ramsey se ocupa de estudiar la existencia de estructuras monocromáticas en universos coloreados, la teoría anti-Ramsey se ocupa de garantizar la existencia de estructuras multicolor (en la literatura llamadas rainbow). Dada una coloración de un conjunto X, decimos que un subconjunto Y de X es multicolor si cada uno de sus elementos recibe un color diferente. Versiones aritméticas de esta teoría han sido estudiadas por Jungi\'c, Fox, Mahdian, Ne\v{s}et\v{r}il y Radoi\v{c}i\'c entre otros. Dichos autores han llamado Rainbow Ramsey Theory a la rama específica en que la existencia de estructuras multicolor se garantiza bajo ciertas condiciones en la densidad de las clases cromáticas.

En términos generales nos interesa estudiar la ``forma'' de aquellas coloraciones que no contengan estructuras multicolor (llamaremos a estas coloraciones libres-multicolor (rainbow-free). En vez de estudiar condiciones en el tamaño de las clases cromáticas para garantizar la existencia de estructuras multicolor, buscaremos describir todas las coloraciones libres-multicolor. En esta charla presentaremos tres resultados que siguen esta filosofía.

En el primero (trabajo conjunto con Oriol Serra) damos una caracterización estructural de las coloraciones libre-multicolor en grupos abelianos de orden impar, con respecto a progresiones aritméticas de tres términos (equivalentemente, soluciones a la ecuación x+y=2z). En el segundo (trabajo conjunto con Bernardo Llano) estudiamos una caracterización estructural análoga en grupos cíclicos de orden primo, con respecto a soluciones de la ecuación lineal en tres variables x+y=cz+d. Finalmente, presentaremos algunos avances con respecto al estudio de soluciones multicolor en Z_p de ecuaciones lineales con cuatro variables.

En términos generales nos interesa estudiar la ``forma'' de aquellas coloraciones que no contengan estructuras multicolor (llamaremos a estas coloraciones libres-multicolor (rainbow-free). En vez de estudiar condiciones en el tamaño de las clases cromáticas para garantizar la existencia de estructuras multicolor, buscaremos describir todas las coloraciones libres-multicolor. En esta charla presentaremos tres resultados que siguen esta filosofía.

En el primero (trabajo conjunto con Oriol Serra) damos una caracterización estructural de las coloraciones libre-multicolor en grupos abelianos de orden impar, con respecto a progresiones aritméticas de tres términos (equivalentemente, soluciones a la ecuación x+y=2z). En el segundo (trabajo conjunto con Bernardo Llano) estudiamos una caracterización estructural análoga en grupos cíclicos de orden primo, con respecto a soluciones de la ecuación lineal en tres variables x+y=cz+d. Finalmente, presentaremos algunos avances con respecto al estudio de soluciones multicolor en Z_p de ecuaciones lineales con cuatro variables.

Thursday December 22, 12h

###### A removal lemma for linear configurations in subsets of the circle

**Pablo Candela (Cambridge University)**

*Abstract:*

We shall discuss results in additive combinatorics known as arithmetic removal-lemmas, in particular the version for the circle group, and we shall describe some applications related to solving linear equations in subsets of abelian groups.

Thursday December 15, 12h

###### Upper Bounds for Higher Sumsets

**Giorgis Petridis (Cambridge University)**

*Abstract:*

We will discuss how graph theory can be used to bound the size of sumsets. Let A and B be finite sets in a commutative group. A central question in the theory of set addition is bounding the size of the sumset

A+hB = {a+b_1+....+b_h : a in A , b_1,....,b_h in B}.

One needs information on |A| and |A+B| in order to be able to extract meaningful bounds. To keep the notation simple we assume that |A+B| \leq \alpha |A|. Imre Ruzsa has obtained a very good upper bound in terms of these two quantities. Applying a graph-theoretic method of Helmut Pl\"unnecke he showed that

|A+hB|\leq \alpha^h |A|^{2-1/h}.

Ruzsa's elegant approach,which we will present it in some detail, yields the best possible dependence on |A| and \alpha. The upper bound can nevertheless be improved as it does not have the correct dependence on the third parameter h. A refinement of Ruzsa's method gives

|A+hB|\leq \frac{\alpha^h}{h^2} |A|^{2-1/h}

We will explain the significance of this improved bound and time permitting sketch how it is obtained.

A+hB = {a+b_1+....+b_h : a in A , b_1,....,b_h in B}.

One needs information on |A| and |A+B| in order to be able to extract meaningful bounds. To keep the notation simple we assume that |A+B| \leq \alpha |A|. Imre Ruzsa has obtained a very good upper bound in terms of these two quantities. Applying a graph-theoretic method of Helmut Pl\"unnecke he showed that

|A+hB|\leq \alpha^h |A|^{2-1/h}.

Ruzsa's elegant approach,which we will present it in some detail, yields the best possible dependence on |A| and \alpha. The upper bound can nevertheless be improved as it does not have the correct dependence on the third parameter h. A refinement of Ruzsa's method gives

|A+hB|\leq \frac{\alpha^h}{h^2} |A|^{2-1/h}

We will explain the significance of this improved bound and time permitting sketch how it is obtained.

Thursday December 1 2011, 12h

###### Maximum degree in minor-closed classes of graphs

**Marc Noy (UPC, Barcelona)**

*Abstract:*

Given a class of graphs A closed under taking minors, we study the maximum degree Delta_n of random graphs from A with n vertices. We prove lower and upper bounds that hold with high probability, depending on the nature of the excluded minors. In particular, we find orders of magnitude for Delta_n not observed before, such us logn / log log logn and logn / log log log logn.

Our main tool is a counting argument introduced recently by McDiarmid and Reed for analyzing the maximum degree of random planar graphs.

Joint work with Omer Giménez and Dieter Mitsche.

Our main tool is a counting argument introduced recently by McDiarmid and Reed for analyzing the maximum degree of random planar graphs.

Joint work with Omer Giménez and Dieter Mitsche.

Thusday November 24, 12h

###### On the cardinality of sumsets in torsion free groups

**Károly J. Böröczky (Alfred Rényi Institute, Budapest)**

*Abstract:*

Let A and B be finite subsets of a torsion-free group G. We prove that for every positive integer k there is a f(k) such that if |B|>f(k) then the inequality |AB|>|A|+|B|+k holds unless a left translate of A is contained in a cyclic subgroup. We obtain f(k) < c k^6 for arbitrary torsion-free groups, and f(k) < c k^3 for groups with the unique product property, where c is an absolute constant. We give examples to show that f(k) is at least quadratic in k.

Thursday November 17 2011, 12h

###### Rainbow k-connection in Dense Graphs

**Henry Liu, Universidade Nova de Lisboa, Portugal**

*Abstract:*

For a graph G and a positive integer k, the rainbow k-connection number rc_k(G) is the minimum integer t such that, there exists an edge-colouring of G with t colours, where any two vertices of G are connected by k internally vertex-disjoint paths, with each path "rainbow" (i.e., using distinct colours). The function rc_k(G) was introduced by Chartrand et al in 2008, and has since attracted considerable interest (Caro et al, Krivelevich and Yuster, Li and Sun, Schiermeyer, among others).

In this talk, we shall prove many new results concerning rc_k(G). We consider the cases when G has fixed vertex-connectivity, when G = K_{n,n}, and when G is some random graph model. We shall also present many related open problems.

Joint work with Shinya Fujita (Gunma National College of Technology, Japan) and Colton Magnant (Georgia Southern University, GA, USA).

In this talk, we shall prove many new results concerning rc_k(G). We consider the cases when G has fixed vertex-connectivity, when G = K_{n,n}, and when G is some random graph model. We shall also present many related open problems.

Joint work with Shinya Fujita (Gunma National College of Technology, Japan) and Colton Magnant (Georgia Southern University, GA, USA).

Thursday November 10, 12h

###### Complete Bipartite Turan numbers

**Simeon Ball (UPC, Barcelona)**

Thursday November 3, 12h

###### On the face vectors of polytopes: unimodality and generalized Euler's relations

**Laszlo Major (Tampere Univ., Finland)**

*Abstract:*

The unimodality conjecture is proved for cyclic polytopes. A general method, based on Stanley's construction of a Pascal's type triangle, is considered to conclude about log-concavity of the face vectors of certain polytopes. A well-known necessary condition for an arbitrary (d+2)-tuple of integers to be the face vector of some d-polytope is Euler's relation. According to Euler's relation any polytope P has as many faces of even dimension as it has faces of odd dimension. As a generalization of this fact one can compare the number of faces whose dimension is congruent to i modulo m with the number of all faces of P for some positive integer m and for some 0 < i < m+1. The powers of certain doubly stochastic matrices are discussed to show that for pyramids, bipyramids, prisms and for simple polytopes the above proportion is asymptotically equal to 1/m.

Thursday October 27, 12h

###### Breaking symmetry in tournaments

**Antoni Lozano (UPC, Barcelona)**

*Abstract:*

We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices S of V (T ) is a /determining set/ for a tournament T if every nontrivial automorphism of T moves at least one vertex of S, while S is a /resolving set/ for T if every two distinct vertices in T have different distances to some vertex in S. We show that the minimum size of a determining set for an order n tournament (its determining number) is bounded by n/3, while the minimum size of a resolving set for an order n strong tournament (its metric dimension) is bounded by n/2. Both bounds are optimal.

Thursday October 20 2011, 12h

###### Quantum Correlations and Device-Independent Quantum Information Processing

**Antoni Acin (Institut de Ciènces Fotòniques, Barcelona)**