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/lafacultat/telefonshoraris
Program: 

10:00  10:15  Welcome and Presentation CONNECT 
10:15  10:45  David FloresPeñaloza 
Erdős–Szekeres theorem on cyclic sequences  
10:45  11:15  Coffee break 
11:15  11:45  Florent Balacheff 
Applications of graph theory to Riemannian geometry  
11:50  12:20  Nacho López 
On the degree/diameter problem for mixed graphs  
12:25  12:55  Alfredo García 
Plane Subgraphs of Complete Topological Drawings  
13:00  14:30  Lunch 
14:30  15:00  Ruy FabilaMonroy 
Forks in blockchain with longest chain rule  
15:05  15:35  Krystal Guo 
Algebraic graph theory and quantum walks  
15:35  15:50  Coffee break 
15:55  16:25  Hebert PérezRosés 
The probabilistic/algebraic approach to network reliability  
16:30  17:00  Berenice MartínezBarona 
A characterization of diamondfree CIS graphs 
Abstracts:
David FloresPeñ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_{n1}$; 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 twoway or only oneway. 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 outdegree $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 2connected and what we call essentially 3edgeconnected. 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 NPHard. However, for a given plane spanning subgraph, a maximum plane augmentation can be found in O(n^3) time.
Ruy FabilaMonroy
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érezRosé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 socalled "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ínezBarona
Universitat Politècnica de Catalunya
Title: A characterization of diamondfree 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 diamondfree graphs. We prove that the Strong clique recognition problema still NPhard within the family of diamondfree graphs. Nevertheless, we develop a polynomially testable characterization of diamondfree 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 polynomialtime solvable in every class of Hfree 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łodowskaCurie 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.