LIMDA Joint Seminar Announcements 2015-2016

ALBCOM Seminar on Algorithms and Theory of Computation COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications

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:

A digraph $G=(V,E)$ is a line digraph when every pair of vertices $u,v\in V$ have either equal or disjoint in-neighborhoods. When this condition only applies for vertices in a given subset, we say that $G$ is a locally line digraph. In this paper we give a new method to obtain a digraph $G'$ cospectral with a given locally line digraph $G$ with diameter $D$, where the diameter $D'$ of $G'$ is in the interval $[D-1,D+1]$.

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, December 4, 2015, 12:30-13:30 (15 minutes delayed with respect to the usual schedule)
Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2)

Clemens Huemer, Universitat Politècnica de Catalunya

The degree/diameter problem in maximal planar bipartite graphs

Abstract:

The $(\Delta,D)$ (degree/diameter) problem consists of finding the largest possible number of vertices $n$ among all the graphs with maximum degree $\Delta$ and diameter $D$. We consider the $(\Delta,D)$ problem for maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle. We obtain that for the $(\Delta,2)$ problem, the number of vertices is $n=\Delta+2$; and for the $(\Delta,3)$ problem, $n= 3\Delta-1$ if $\Delta$ is odd and $n= 3\Delta-2$ if $\Delta$ is even. Then, we prove that, for the general case of the $(\Delta,D)$ problem, an upper bound on $n$ is approximately $3(2D+1)(\Delta-2)^{\lfloor D/2\rfloor}$, and another one is $C(\Delta-2)^{\lfloor D/2\rfloor}$ if $\Delta\geq D$ and $C$ is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on $n$ for maximal planar bipartite graphs, which is approximately $(\Delta-2)^{k}$ if $D=2k$, and $3(\Delta-3)^k$ if $D=2k+1$, for $\Delta$ and $D$ sufficiently large in both cases.

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:

Constraint Satisfaction Problems (CSP) are a generalization of 3-SAT, consisting of problems of the form: given an instance consisting of a set of variables, and a set of constraints on them (where each constraint is a relation from a fixed vocabulary on a fixed domain), decide whether there exists an assignment of domain values, which satisfies every constraint. Depending on the allowed set of relations, the CSP problem can have various complexities within NP. We consider CSP problems in which the instance is allowed to be infinite, but has a finite description (an interpretation) in a fixed, countable first-order structure with enough decidability properties, e.g. (N,=) or (Q,<). Then, I will specify tight complexity bounds for this problem, showing that the complexity increases exponentially when we allow infinite instances. In the upper bound, we use results from Ramsey theory and topological dynamics. In this talk, I will recall all the notions mentioned above, and sketch a proof of the upper bound.

Barcelona, 25-27 November 2015

Zero-error information, Operators, and Graphs Workshop

http://www.qciao.org/

The scope of the workshop is to bring together researchers from information and quantum information theory, combinatorics, and functional analysis, with the purpose of developing the nascent links between these fields within the recently growing area of zero-error quantum information.

Confirmed invited participants:

Aida Abiad (Maastricht), Antonio Acín (Barcelona), Sabine Burgdorf (Amsterdam), Runyao Duan (Sydney), Miquel Àngel Fiol Mora (Barcelona), Vittorio Giovannetti (Pisa), Janos Körner (Roma), Monique Laurent (Amsterdam/Tilburg), Debbie Leung (Waterloo), Laura Mančinska (Singapore/Bristol), Gláucia Murta Guimarães (Belo Horizonte), Miguel Navascués (Vienna), Carlos Ortiz (Houston), Teresa Piovesan (Amsterdam), David Roberson (Singapore/London), Ana Belén Sainz (Bristol), Florian Speelman (Amsterdam), Ivan Todorov (Belfast), Antonios Varvitsiotis (Singapore), Nik Weaver (St. Louis).

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:

Given a plane graph G and a positive integer d, the Plane Diameter Completion problem asks whether G is a spanning subgraph of a plane graph H that has diameter at most d. Plane graphs are defined as planar graphs given together with a fixed embedding on the unit-sphere.

We are interested in the complexity of this problem, and to this end examine two variants of it where the input comes with another parameter k. In the first variant, k upper bounds the total number of edges to be added and in the second, k upper bounds the number of additional edges per face. Both problems appear to be NP-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when k = 1 on 3-connected graphs of face-degree at most 5.

A traditionnal way to deal with difficult problems is the design of parameterized algorithms, i.e. algorithms for which the complexity is polynomial in the size of the input and at least exponential in some other parameters independent of the size. This talk will be focused on the presentation of such an algorithm, solving a generalisation of both problems, that is parameterized by both k and d and run in time O(n^3) + 2^{ 2^{O((kd)^2*log(d))} }*n.

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:

A class of graphs is bridge-addable if, given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. We prove a conjecture of McDiarmid, Steger and Welsh, that says that if G_n is taken uniformly at random from a class of bridge-addable graphs on n vertices, then G_n is connected with probability at least exp(-1/2)+o(1), when n tends to infinity. This lower bound is asymptotically best possible and it is reached for the class of forests. Our proof uses a "local double counting" strategy that enables us to compare the size of two sets of combinatorial objects by solving a related multivariate optimization problem.

This is joint work with Guillaume Chapuy.

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:

Given a rational matrix A, consider the homogeneous system of linear equations Ax=0. This system or the matrix is called k-regular, if for every k-coloring of the natural numbers the system has a monochromatic solution. A matrix is called regular if it is k-regular for all k. Generalizing both Schur and Van der Waerden's Theorems a celebrated result by Richard Rado characterizes regular matrices. In the context of the arithmetic anti-Ramsey Theory, which concerns the study of the existence of rainbow structures instead of monochromatic ones, we present a rainbow Ramsey version of Rado's Theorem. We also disprove two conjectures proposed in the literature. We use techniques from the Geometry of Numbers.

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:

Constructing optimal (minimum average search time) binary search trees (BSTs) is one of the canonical early uses of dynamic programming. In 1971, Knuth described how to solve this problem in O(n^2) time, with input specifying the probability of the different successful and unsuccessful searches. While the trees constructed were binary, the comparisons used were ternary. Successful searches terminated at internal nodes and unsuccessful searches at leaves.

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:

The Strong Exponential Time Hypothesis (SETH) says that solving the SATISFIABILITY problem on formulas that are k-CNFs in n variables require running time 2^((1 - c_k) n) where c_k goes to 0 as k goes to infinity. Of course SETH is much stronger than P vs NP hence proving (or disproving) SETH seems to be out of reach at the moment. However one could ask if SETH is consistent with some particular algorithm or some class of algorithms. For example the fact that SETH holds for the DPLL algorithm could be derived from lower bounds on the size of tree-like resolution refutations. Despite the fact that exponential lower bounds on size of resolution proofs are 30 years old [Haken 85], only in 2000 Pudlak and Impagliazzo proved lower bounds for tree-like resolution strong enough to support SETH. Recently Beck and Impagliazzo (2013) proved that SETH is consistent with regular resolution. Informally this tell us that any SAT solver that could be formalised in regular resolution cannot disprove SETH. At the moment is not known whether SETH is consistent with full resolution, that is without constraints. Here we present a different/simpler proof of the lower bound for regular resolution by Beck and Impagliazzo. Our proof pass trough game characterisations of width and size of resolution proofs and a multiplication of strategies in those games. This technique actually works for some proof systems between regular resolution and resolution. In such systems the refutations are allowed to have some (fairly small) amount of irregularity, that is some (fairly small) number of variables is allowed to be resolved multiple times along paths of the refutations.

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