CONNECT Combinatorics of Networks and Computation Research Day

The research day is organized within the project CONNECT. It brings together researchers working on networks, graph theory, computational geometry, discrete mathematics, and related areas. The research day offers eight conferences.  

Date and Location: 

14 of June 2019, 10:00 - 17:00

Universitat Politècnica de Catalunya

Facultat de Matemàtiques

Sala de Juntes

https://fme.upc.edu/ca/la-facultat/telefons-horaris

Abstracts:

David Flores-Peñaloza

Universidad Nacional Autónoma de México

Title: Erdős–Szekeres theorem on cyclic sequences

Abstract: A classical result of Erdős and Szekeres states the number $f(n)$, which is the smallest integer such that any sequence of distinct real numbers of length $f(n)$ contains a monotone (increasing or decreasing) subsequence of length $n$.

A \emph{circular sequence} $C$ is a sequence of distinct real numbers $x_0, x_1, x_{n-1}$; where, given indices $i < j < k$,  the triplet $(x_i, x_j, x_j)$ is \emph{increasing} if the three elements are \emph{cyclically ordered} in the sequence: either a) $x_i < x_j < x_k$, or b)

$x_j < x_k < x_i$, or $x_k < x_i < x_j$; otherwise the triplet $(x_i,x_j,x_k)$ is \emph{decreasing}. A subsequence $S$ of $C$ is \emph{monotone} if either all its triplets are increasing; or all its triplets are decreasing.

We extend the result of Erdős and Szekeres to show the value of $f_c(n)$, the smallest integer such that any \emph{circular sequence} of length $f_c(n)$, contains a \emph{monotone} circular subsequence of length $n$, along with related results.

This is joint work with Juan José Montellano from Instituto de Matemáticas, Universidad Nacional Autónoma de México.

Florent Balacheff

Universitat Autònoma de Barcelona 

Title: Applications of graph theory to Riemannian geometry

Abstract: In this short talk, I will survey some nice examples of how graph theory can be used to derive universal inequalities on Riemannian manifolds.

Nacho López

Universitat de Lleida

Title: On the degree/diameter problem for mixed graphs

Abstract: Network topologies based on mixed graphs arise in many practical situations, where the relationship between nodes into the network can be undirected or directed depending on whether the communication between nodes is two-way or only one-way. From this point of view, mixed graphs generalize both graphs and digraphs. Given three natural numbers $r,z$ and $k$, the Degree$/$Diameter problem for mixed graphs asks for the largest possible number of vertices $n(r,z,k)$ in a mixed graph with maximum undirected degree $r$, maximum directed out-degree $z$ and diameter $k$. The study of this problem has deserved much attention in the last decades either for graphs and digraphs, but not for mixed graphs.  In this talk we present some recent advances and open questions regarding this problem.

Alfredo García

Universidad de Zaragoza

Title:  Plane Subgraphs of Complete Topological Drawings

Abstract:  This talk is about simple topological drawings of the complete graph K_n. We  present some new structural results on plane subgraphs of those drawings. In particular, we prove that maximal plane subgraphs must be 2-connected and what we call essentially 3-edge-connected. They must also contain at least 3n/2 edges. The problem of computing a plane subgraph with maximum number of edges is also studied. This problem turns out to be NP-Hard. However, for a given plane spanning subgraph, a maximum plane augmentation can be found in O(n^3) time.

Ruy Fabila-Monroy

CINVESTAV

Title: Forks in blockchain with longest chain rule

Abstract: Blockchains are the core data structure of most cryptocurrencies. Operations on the shared ledger are grouped into blocks. These blocks are stored in a sequence called a blockchain. Each block is numbered and contains a hash of the previous block in the chain. In this sense a blockchain is a linked list of blocks. Each node participating in the network stores a copy of the blockchain. New blocks are proposed asynchronously by nodes in the network. It may happen that two different versions of the new block are proposed almost at the same time. Each node has then to decide which of the two blocks to include in the blockchain. This is usually done with the longest chain rule. That is, nodes always choose the highest numbered block. As a result two nodes might have a different version of the blockain; two different coexisting versions of the blockchain are called forks. We propose a model to study the behavior of these forks in the scenario where many blocks are generated simultaneously.

 Krystal Guo

Université libre de Bruxelles

Title: Algebraic graph theory and quantum walks

Abstract: A system of interacting quantum qubits can be modelled by a graph. The evolution of the quantum system can be completely encoded as a quantum walk in a graph, which can be seen, in some sense, as a quantum analogue of random walk. This gives rise to a rich connection between algebraic graph theory, linear algebra and quantum computing. In this talk, I will present recent results on the average mixing matrix of a graph: a quantum walk has a transition matrix which is a unitary matrix with complex values and thus will not converge, but we may speak of an average distribution over time, which is modelled by the average mixing matrix. This talk will not assume any prior knowledge of quantum computing or physics.

Hebert Pérez-Rosés

Universitat Rovira i Virgili

Title: The probabilistic/algebraic approach to network reliability

Abstract: Networks are ubiquitous in modern society, and constructing robust networks is of outmost importance. There are many approaches to quantify network robustness against random failures or intentional attacks. Perhaps the most popular approach is based on the so-called "reliability polynomial", which quantifies the probability that a network remains connected if some of its components (vertices or edges) fail with a given probability. We survey the most important results associated with the reliability polynomial, and outline some areas of current and future development. 

Berenice Martínez-Barona

Universitat Politècnica de Catalunya

Title: A characterization of diamond-free CIS graphs

Abstract: A clique in a graph is strong if it intersects all maximal stable sets, and a graph is said to be CIS if every maximal clique in G is strong. Currently, no good characterization or recognition algorithm for the CIS graphs is known. We study this property in the class of diamond-free graphs. We prove that the Strong clique recognition problema still NP-hard within the family of diamond-free graphs. Nevertheless, we develop a polynomially testable characterization of diamond-free CIS graphs. Together with some known results on CIS graphs available in the literature, this result implies that the problem of recognizing CIS graphs is polynomial-time solvable in every class of H-free graphs where H is a graph on at most four vertices. (Joint work with Nina Chiarelli, Martin Milanič, Jerome Monnot and Peter Muršič.)

   This project has received funding from the European Union's Horizon 2020 research and innovation programme 

   under the Marie Skłodowska-Curie grant agreement No 734922.

The CONNECT Combinatorics of Networks and Computation Research Day is organized by 

Cristina Dalfó, Universitat de Lleida, and Clemens Huemer, Universitat Politècnica de Catalunya.