# LIMDA Joint Seminar Announcements 2015-2016

Date: 2016-06-16

Time: 12:00

Where: Room 005, Building C3, Campus Nord UPC

Speaker: Christian Elsholtz, Graz University of Technology

Title: Hilbert cubes in arithmetic sets

Abstract:

We show upper bounds on the maximal dimension d of Hilbert

cubes H=a_0+{0,a_1}+ ... + {0, a_d} in several

sets S of arithmetic interest such as the squares.

Date: 2016-06-02

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Víctor Diego, Departament de Matemàtiques, UPC

Title: Distance mean-regular graphs

Abstract:

We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let $\G$ be a graph with vertex set $V$, diameter $D$, adjacency matrix $\A$, and adjacency algebra ${\cal A}$. Then, $\G$ is {\em distance mean-regular} when, for a given $u\in V$, the averages of the intersection numbers $p_{ij}^h(u,v)=|\G_i(u)\cap \G_j(v)|$ (number of vertices at distance $i$ from $u$ and distance $j$ from $v$) computed over all vertices $v$ at a given distance $h\in \{0,1,\ldots,D\}$ from$u$, do not depend on $u$. In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of $\G$ and, hence, they generate a subalgebra of ${\cal A}$. Some other algebras associated to distance mean-regular graphs are also characterized.

Date: 2016-05-26

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Jack Koolen, University of Science and Technology of China

Title: Recent progress on 2-walk-regular graphs

Abstract:

In this talk I will present some recent progress on 2-walk-regular graphs.

This is based on joint work with Zhi Qiao, Jongyook Park and Shao-Fei Du.

Date: 2016-03-17

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Christoph Spiegel, Freie Universität Berlin

Title: Threshold functions for systems of equations in random sets

Abstract:

We present a unified framework to deal with threshold functions for the existence of solutions to systems of linear equations in random sets. This covers the study of several fundamental combinatorial families such as k-arithmetic progressions, k-sum-free sets, B_h(g)- sequences and Hilbert cubes of dimension k.

We show that there exists a threshold function for the property "A^m contains a non-trivial solution of Mx=0” where A is a random set. This threshold function depends on a parameter maximized over all subsystems, a notion previously introduced by Rödl and Rucinski. The talk will contain a formal definition of trivial solutions for any combinatorial structure, extending a previous definition by Ruzsa.

Joint work with Juanjo Rué Perna and Ana Zumalacárregui.

Thursday, December 10, 2015, 12h

Room C3-005, Campus Nord UPC**Miquel Àngel Fiol, UPC Barcelona****Cospectral digraphs from locally line digraphs***Abstract:*

In particular, when the method is applied to De Bruijn or Kautz digraphs, we can obtain cospectral digraphs with the same algebraic properties that characterize the formers.

Joint work with Cristina Dalfó.

COMPUTATIONAL GEOMETRY SEMINAR

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

**Clemens Huemer, **

Wednesday, December 2nd, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord

**Szymon Toruńczyk, Department of CS, UPC and University of Warsaw, Poland**

**CSPs with infinite instances**

*Abstract:*

Barcelona, 25-27 November 2015

**Zero-error information, Operators, and Graphs Workshop**

http://www.qciao.org/

* Confirmed invited participants:*

* Organizers:*

Andreas Winter (Barcelona), Simone Severini (London), Giannicola Scarpa (Barcelona).

Wednesday November 18, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

**Clément Requilé, Freie University, Berlin**

**Variants of Plane Diameter Completion**

*Abstract:*

This talk represents joint work with Petr A. Golovach and Dimitrios M. Thilikos.

Thursday, November 5, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

**Guillem Perarnau, University of Birmingham (UK)**

** Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture**

*Abstract:*

Wednesday, November 4, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

**Amanda Montejano, Instituto de Matemáticas, UNAM (Mexico)**

** A Rainbow Ramsey Analogue of Rado's Theorem***Abstract:*

Wednesday, October 14, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

** Mordecai Golin, Department of Computer Science, Hong Kong University of Science and Technology**

** Optimal Binary Comparison Search Trees**

*Abstract:*

By contrast, in binary comparison trees (BCSTs), internal nodes perform binary comparisons; the search branches left or right depending upon the comparison outcome and all searches terminate at leaves. Polynomial algorithms exist for solving the optimal BCST problem in special cases with input restricted to successful searches. Hu and Tucker gave an O(n log n) algorithm when all comparisons are the inequality “<”; Anderson et. al. developed an O(n^4) algorithm when both “<” and “=” comparisons are allowed.

In this talk we present the first polynomial time algorithms for solving the optimal BCST problem when unsuccessful searches are included in the input and any set of comparisons are permitted. Our running times depend upon the comparisons allowed. If equality is not allowed, our algorithm runs in O(n log n) time; if equality is allowed, O(n^4). We also demonstrate O(n) time algorithms that yield almost optimal binary comparison trees, with tree cost within constant additive factor of optimal.

This is joint work with Marek Chrobak, Ian Munro and Neal Young.

Thursday, October 1, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

**Ilario Bonaccina, Computer Science Department, University of Rome Sapienza, Rome, Italy**

**Strong Size Lower Bounds in Resolution via Games**

*Abstract:*

Joint work with N. Talebanfard (Tokyo Institute of Technology) IPEC 2015.

Thursday, September 17, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC**Bruce Reed, School of Computer Science, McGill Univ. (Montreal)**

*Random Models Of 21st Century Networks And Their Connectivity Structure*

*Abstract:*

The traditional Erdos-Renyi model of a random network is of little use in modeling the type of complex networks which modern researchers study. It postulates that each node has the same likelihood of being attached to every other node. However, in, e.g. the web, certain authoritative pages will have many more links entering them. A 1995 paper of Molloy and Reed, cited over 1500 times, sets out some conditions guaranteeing the existence of a giant component in a network with a specified degree sequence. This work has attracted such a great deal of attention because it can be applied to random models of a wide range of complicated 21st century networks such as the web or biological networks operating at a sub-molecular level. A heuristic argument suggests that a giant component will exist provided the sum of the squares of the degrees of the nodes of the network is at least twice the sum of the degrees. Molloy and Reed proved that this is indeed true subject to certain technical conditions. Many authors, have obtained related results by specifying different technical conditions, or by tying down the size of the giant component.

Since the interest in this result is its wide applicability, it is natural to try and prove it under as few assumptions as possible. Recently, Joos, Perarnau-Llobet, Rautenbach, and Reed proved the result under essentially no conditions.

I will present, in an accessible way, a variety of complex networks and their random models to which the Molloy-Reed result has been applied. I will then sketch the proof of our result and how it differs from the proof of the Molloy-Reed result.

### Acknowledgements

The activities of this seminar series are partially funded by European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR), by AGAUR AGAUR (grant 2014SGR1147 and 2014SGR1034) and MINECO (projects MTM2014-54745-P, MTM2014-60127-P and TIN2013-48031-C4-1-P (TASSAT2) )