2022-23 LIMDA Seminar

Date: Tuesday, 18 July, 2023

Time: 15.00h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Inference in balanced community modulated recursive trees

Speaker: Vasiliki Velona (Hebrew University of Jerusalem)

Abstract:

I will introduce a random recursive tree model with two communities, called balanced community modulated random recursive tree (BCMRT in short), which was inspired by the CMRT model of S. Bhamidi, R. Fan, N. Fraiman, and A. Nobel. The model is dependent on a parameter q and the asymptotic degree distribution coincides for all q as the number of vertices tends to infinity. Therefore, one wonders how to distinguish between different values of q when only the graph structure is observed. We find a statistic that manages to do this task and also discover an upper and a lower bound for the possibility of testing, when one allows q to vary with the size of the tree. Moreover, we show that if q is small enough, then it is possible to cluster in a way correlated with the true partition, even though the algorithm is exponential in time. This is joint work with Anna Ben-Hamou.

 

Date: Monday, 3 July, 2023

Time: 12.00h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: Random embeddings with optimal spread

Speaker: Alp Müyesser (University College London)

Abstract:

Let G and H be graphs on n vertices, and suppose G has large enough minimum degree to necessarily contain H as a subgraph. We show that H in fact embeds into G with good ``spread''.  More precisely, for a wide class of H, we find a randomised embedding f:H->G with the following property: for every s, for any partial embedding f' of s vertices of H into G, the probability that f extends f' is at most O(1/n)^s. This is a common generalisation of several streams of research surrounding the classical Dirac-type problem. 

For example, setting s=n, we obtain an asymptotically tight lower bound on the number of embeddings of H on G. This recovers and extends recent results of Glock-Gould-Joos-Kühn-Osthus and Montgomery-Pavez-Signé regarding enumerating Hamilton cycles in Dirac hypergraphs. Moreover, using the recent developments surrounding the fractional Kahn-Kalai conjecture, this result implies that many Dirac-type results hold robustly, meaning H still embeds into random sparsifications of the edge-set of G. This allows us to recover recent results of Kang-Kelly-Kühn-Osthus-Pfenninger and Pham-Sah-Sawhney-Simkin for perfect matchings, and obtain novel results for Hamilton cycles and graph factors.

In this talk, we present our randomised embedding algorithm, which is simple and self-contained. Notably, the algorithm does not rely on the regularity/absorption method, unlike similar results in the area. 

This is joint work with Tom Kelly and Alexey Pokrovskiy.

 

Date: Thursday, 22 June, 2023

Time: 17.00h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title: The asymptotics of $r(4,t)$

Speaker: Sam Mattheus (University of California, San Diego)

Abstract:

For integers $s,t \geq 2$, the Ramsey numbers $r(s,t)$ denote the minimum $N$ such that every $N$-vertex graph contains either a clique of order $s$ or an independent set of order $t$. I will give an overview of recent work, joint with Jacques Verstraete, which shows

$$r(4,t) = \Omega\Bigl(\frac{t^3}{\log^4 \! t}\Bigr) \quad \quad \mbox{ as }t \rightarrow \infty$$

which determines $r(4,t)$ up to a factor of order $\log^2 \! t$, and solves a  conjecture of Erd\H{o}s.

 

Date: Thursday, 1 June, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  Approximate sampling and counting for spin models on graphs

Speaker: Xavier Povill (UPC)

Abstract:

The framework of spin models, originated in statistical physics, can be used from a combinatorics perspective to study graph structures such as independent sets or colorings. In this expository talk we introduce two general techniques by Weitz and Barvinok to devise approximate sampling and counting algorithms for general spin models, and give a survey of the recent results of Davies and Perkins, and Jain, Perkins, Sah and Sawhney on the complexity of sampling an approximately uniform independent set of a given size. We also discuss some ongoing work on extending this approach to the sampling of colorings with given color sizes.

 

Date: Thursday, 11 May, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  Packing large balanced trees

Speaker: Giovanne Santos (Universidad de Chile)

Abstract:

We say that a graph H embeds in a graph G if there is a copy of H in G.
A family of graphs H_1,...,H_k packs in a graph G if there exist pairwise edge-disjoint embeddings of H_1,...,H_k in G. In 1976, Gyárfás raised the following question: does any sequence of n trees T_1,...,T_n such that T_i has i vertices pack into the complete graph on n vertices, K_n? Despite recent progress for sequences of trees with almost-linear maximum degree, this question is still open. Balogh and Palmer proved (for n sufficiently large) that we can pack any sequence of t := n^{1/4}/10 large trees T_n,...,T_{n-t+1} into K_n as long as no tree in the sequence is a star. Hollingsworth presented in 2013 a variant of
Gyárfás' conjecture to balanced trees. In this talk, I will present an approximate analogue of Balogh and Palmer's result for Hollingsworth's conjecture.

This is joint work with Maya Stein, Cristina G. Fernandes and Tássio Naia.

 

Date: Thursday, 4 May, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  The Implicit Graph Conjecture is false

Speaker: Clément Requilé (UPC)

Abstract:

An implicit representation of an n-vertex graph G assigns a binary code of length a(n) to each vertex of G so that the adjacency between each pair of vertices can be determined as a function of their respective codes. This representation is efficient when a(n) = O(log n).
    A family of graphs with efficient implicit representation is small in the sense that it contains at most factorially many graphs with a fixed number of vertices. However, not all small graph families have an efficient implicit representation. The counter-examples come from non-hereditary graph families, and the three-decades-old Implicit Graph Conjecture asks whether all hereditary graph familes, i.e. closed under taking induced subgraphs, that are small admit an efficient implicit representation.
    In this talk we will discuss the recent breakthrough of Hatami and Hatami (see https://arxiv.org/abs/2111.13198) in which they disprove the conjecture. Their proof is relatively short and combines an observation about sparse random graphs with an information-theoretic counting argument. 

Date: Thursday, 27 April, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  Quantum cyclic redundancy codes

Speaker: Simeon Ball and Ricard Vilar (UPC)

Abstract:

We extend the idea of classical cyclic redundancy check codes to quantum cyclic redundancy check codes. This allows us to construct codes quantum stabiliser codes which can correct burst errors where the burst length attains the quantum Rieger bound. We then consider a certain family of quantum cyclic redundancy check codes for which we present a fast linear time decoding algorithm.

 

In this talk, we discuss a generalisation of tilings into a multipartite setting. In particular, let $G$ be a $k$-partite graph with parts $V_1, \ldots, V_k$ each of size $n$, and let the minimum degree in $G[V_i, V_{i+1}]$ be at least $(1+1/k)n/2$ for each $i \in [k]$. We show that if $k$ is even and $n$ is `sufficiently large’, $G$ contains a $C_k$-factor in which each copy of $C_k$, the cycle $k$ vertices, contains exactly one vertex from each $V_i$. This resolves independent conjectures of Fischer and H\"aggkvist in the case when $k$ is even. When $k$ is odd, we show that either $G$ contains such a $C_k$-factor or $G$ is `close to' extremal. 

This is joint work with Richard Mycroft.

 

Date: Thursday, 13 April, 2023

Since the work of Goemans-Williamson in 1995 there has been much interest in finding randomized approximation algorithms for NP-hard problems by using semi-definite programs (SDPs). In 2008, Johan Håstad presented an SDP based probabilistic algorithm for finding approximate solutions to the maximum 2-CSP problem.
We use Håstad's SDP in a slightly modified version to obtain necessary and sufficient conditions for q-colorability refutations of degree 2 to exist in the proof system Sum-of-Squares.
As shown by Banks, Kleinberg and Moore in 2017, the same can be done with the Lovász Theta Number as well.

Master thesis supervised by Albert Atserias and Jacobo Torán

 

Date: Tuesday, 11 April, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:   Killing a Vortex

Speaker: Dimitrios Thilikos (AlGCo project-team, CNRS, LIRMM, Montpellier)

Abstract: We provide a “vortex-free” refinement of the seminal structure theorem for K_t-minor free graphs by Robertson and Seymour as follows: we identify a (parameterized) graph Ht and we prove that if we replace K_t by H_t, then the resulting decomposition becomes “vortex- free”. Up to now, the most general classes of graphs admitting such a result were either bounded Euler genus graphs or the so called single-crossing minor-free graphs. This result is tight in the sense that, whenever we minor-exclude a graph that is not a minor of some H_t, the appearance of vortices is unavoidable. Using the above decomposition theorem, we design an algorithm that, given an H_t-minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. This algorithm yields, on H_t-minor-free graphs, polynomial algorithms for computational problems such as the dimer problem, the exact matching problem, and the computation of the permanent. Our results, combined with known complexity results, imply a complete characterization of minor-closed graphs classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every H_t as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.

Paper available at: https://arxiv.org/abs/2207.04923

 

Date: Thursday, 30 March, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  Product-free sets in the free group

Speaker: Miquel Ortega (UPC)

Abstract:

We prove that product-free sets of the free group over a finite alphabet have maximum density 1/2 with respect to the natural measure that assigns total weight one to each set of irreducible words of a given size. This confirms a conjecture of Leader, Letzter, Narayanan and Walters. In more general terms, we actually prove that strongly k-product-free sets have maximum density 1/k in terms of the said measure.

Date: Thursday, 23 March, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  Long running times for hypergraph bootstrap percolation

Speaker: Alberto Espuny (TU Ilmenau)

Abstract:

Consider the hypergraph bootstrap percolation process in which, given a fixed $r$-uniform hypergraph $H$ and starting with a given hypergraph $G_0$, at each step we add to $G_0$ all edges that create a new copy of $H$. We are interested in maximising the number of steps that this process takes before it stabilises. In this talk, I will explain the recent progress on this problem. Moreover, for the case where $H=K_{r+1}^{(r)}$ with $r\geq3$, I will present a new construction for $G_0$ that shows that the number of steps of this process can be of order $\Theta(n^r)$. This answers a recent question of Noel and Ranganathan.

To demonstrate that different running times can occur, we also prove that, if $H$ is $K_4^{(3)}$ minus an edge, then the maximum possible running time is $2n-\lfloor \log_2(n-2)\rfloor-6$. However, if $H$ is $K_5^{(3)}$ minus an edge, then the process can run for $\Theta(n^3)$ steps.

This is based on joint work with Barnabás Janzer, Gal Kronenberg and Joanna Lada.

 

Date: Thursday, 16 March, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  Acyclonestohedra

Speaker: Arnau Padrol (UB)

Abstract:

Nested complexes are simplicial complexes associated to building sets of a meet semi-lattice. They were defined by Feichtner and Kozlov motivated by De Concini and Procesi's wonderful compactification. Nested complexes of the boolean lattice can be realized as polytopes, called nestohedra, and have received a lot of attention. The family includes famous polytopes as the permutahedron, the associahedron or the cyclohedron, which are particular classes of graph associahedra. I will do an introduction to the topic motivated by our recent introduction of oriented building sets defined on the ground set of an oriented matroid, and their associated acyclic nested complexes, which are nested complexes fulfilling an additional acyclicity condition. For realizable oriented matroids, we provide a polytopal construction as a section of a nestohedron with a linear subspace.  When the oriented matroid is associated to an acyclic directed graph, we obtain a polytopal realization of Galashin's poset associahedra, which was on of our original motivations. This is joint work with Chiara Mantovani and Vincent Pilaud.

 

Date: Thursday, 9 March, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  Short Synchronizing Words for Random Automata

Speaker: Guillem Perarnau (UPC)

Abstract:

We prove that a random deterministic finite automaton on n states has a synchronizing word of length O(n^{1/2}\log n) with high probability, confirming conjectures of several authors based on numerical simulations. The best theoretical result prior to this work was the bound O(n \log^3 n) given by Cyril Nicaud. Additionally, our proof provides a quasi-quadratic algorithm to find such synchronizing word. This is joint work with Guillaume Chapuy.

 

Date: Friday, 3 March, 2023

Time: 11.30h (Barcelona time)

Where: Sala d'Actes FME, Edifici U, Campus Sud

Title:  First Order Logic of Random Sparse Structures

Ph.D. Defence, Applied Mathematics: Larrauri Borroto, Lázaro Alberto

Advisor: Noy Serrano, Marc

Speaker: Alberto Larrauri Borroto (UPC-TU Graz)

Abstract:

This work is dedicated to the study several models of random structures from the perspective of first-order logic. We prove that the asymptotic probabilities of first-order statements converge in a general model of random structures with linear density, extending previous results by Lynch. Additionally, we give an application of this result to the random SAT problem. We also inspect the set of limiting probabilities of first-order properties in sparse binomial graphs, binomial d-uniform hypergraphs and graphs with given degree sequences. In particular, we characterize the conditions under which this set of asymptotic probabilities is dense in the interval [0, 1]. Finally, we introduce the question of whether preservation theorems, namely Los-Tarski Theorem and Lyndon's Theorem, hold in a probabilistic sense in various models of random graphs. We obtain several positive results in different regimes of the binomial random graph and uniform graphs from addable minor-closed classes.

 

Date: Thursday, 23 February, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  Recent progress on the Union-Closed Conjecture

Speaker: Patrick Morris (UPC)

Abstract:

A set family F is said to be union-closed if for any two sets a,b in F, their union a\cup b also belongs to F. In 1979, Péter Frankl posed the beautiful conjecture that for any union-closed family, there is some element of the ground set that is contained in at least half of the sets in the family. Despite considerable attention over the years, this conjecture is yet to be solved. However, at the end of 2022, there was a big breakthrough by Justin Gilmer, a researcher at Google's `Brain Team', who proved a weaker version of the conjecture, showing that in any union-closed family, there is an element which belongs to a positive proportion of the sets. This led to a flurry of results, incrementally improving the implicit constant. In this talk, I will discuss the new approach introduced by Gilmer, which is common to all recent improvements.

 

Date: Tuesday, 21 February, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  The 4-color Ramsey Multiplicity of Triangles

Speaker: Christoph Spiegel (Zuse Institute Berlin)

Abstract:

In 1959 Goodman established that asymptotically, in any two-edge-coloring of the complete graph, at least a quarter of all triangles must be monochromatic. This initiated the much studied Ramsey Multiplicity problem and was extended in 2013 by Cummings et al. to three-edge-colorings. In this talk, we will explore some ongoing work related to triangles in four-edge-colorings and the computational challenges of scaling up the proofs, which are based on flag algebras and conic optimization.

This is joint work with Aldo Kiem and Sebastian Pokutta.

 

Date: Thursday, 16 February, 2023

Time: 16.15h (Barcelona time)

Where: Room C3-005 Campus Nord UPC and Meet link

Title:  Towards the 3n-4 theorem in groups of prime order

Speaker: Oriol Serra (UPC)

Abstract:

A well-known theorem of Freiman states that a set A of integers having doubling |2A| smaller than 3|A|-3 must be dense in an arithmetic progression, more precisely, contained in an arithmetic progression of length at most |2A|-|A|+1. It was conjectured long ago that an analogous result should hold in groups of prime order. The talk will discuss the history of this problem and a recent progress towards this conjecture in a joint work with Vsevolod Lev.

 

Date: Thursday, 2 February, 2023

Time: 16.15h (Barcelona time)

Where: Meet link

Title:  Joint properties of vertices with a given degree in the random recursive tree

Speaker: Bas Lodewijks (University of Lyon, University of Saint-Etienne)

Abstract:

In this talk, we will investigate the joint behaviour of the degree, depth, label of, and graph distance between high-degree vertices in the random recursive tree with n vertices labelled {1,...,n}. The analysis of the label of and graph distance between high-degree vertices is novel, in particular in relation to the behaviour of the depth of such vertices (whose known results we also improve and extend). Our analysis is based on a correspondence between the random recursive tree and a representation of the Kingman's n-coalescent.

 

Date: Thursday, 26 January, 2023

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Meet link

Title:  Cops and Robber Game on Surfaces of Euclidean, Spherical and Hyperbolic Metric

Speaker: Alexandra Wesolek (Simon Fraser University)

Abstract:

Recently, Mohar introduced a variant of the cops and robber game that is played on geodesic spaces. The game combines properties of pursuit-evasion games with the classical cops and robber game played on graphs. In this talk we discuss the rules of the game and strategies for the players when the game is played on compact surfaces of constant curvature 0,1 and -1. Joint work with Vesna Iršič and Bojan Mohar.

 

Date: Thursday, 19 January, 2023

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Meet link

Title:  Classifying weighted graphs up to Clifford group equivalence

Speaker: Robin Simoens (Ghent University and UPC)

Abstract:

Let G be an undirected, loopless graph on n vertices whose edges have weights in F_p, p prime. Let A=(a_ij) be its adjacency matrix. Define the following two operations:

    For a given vertex k, map all a_ij to a_ij+a_ik a_jk (for all i,j in the neighbourhood of k, add a_ik a_jk to the weight of the edge connecting them).

    For a given vertex k and a nonzero c in F_p, map all a_ik to ca_ik (multiply all edges incident with k, with c).

We call two such graphs Clifford group equivalent if there exists a sequence of these operations that converts one into the other. We are interested in the number of graphs up to this equivalence.

Our motivation comes from stabiliser codes. Two stabiliser codes are equivalent if their stabilisers are the same up to conjugation with a Clifford gate. Such equivalent codes have been shown to correspond with Clifford group equivalent graphs and vice versa.

For p=2 and n<=12, the number of equivalence classes has been determined. For odd p however, no results are known.

In this talk, I will discuss the above equivalence and present some strategies to compute the number of equivalence classes for p=3. I will explain how this helps us classify the stabiliser codes and certain other quantum error-correcting codes.

 

Date: Thursday, 1 December, 2022

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Meet link

Title:  Pattern Occurrence Counts in Random Planar Maps

Speaker: Michael Drmota (TU Wien)

Abstract:

Random planar maps have been studied from various aspects during the last 15 or 20 years, including various limiting distributions for several parameters of interest (such as the largest 2-connected component) and local Benjamini-Schramm limits as well as scaling limits. A pattern is a given planar map and we say that it appears in another map if it could be "cut out" just leaving a face. The simplest pattern is just an k-gons. It directly follows from the Benjamini-Schramm limit that the expected number of occurrences of a given pattern is asymptotically linear in the number of edges of the random map. However, it is a challenging problem to provide a more precise limit law. The purpose of this talk is to give a survey on the results and methods that have used so far in order to settle this question. It is conjectures that there is always a central limit theorem - and all results so far support this conjecture. 

 

Date: Thursday, 10 November, 2022

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Meet link

Title:  Polynomial Algebras and Ideals for marked graphs reconstruction

Speaker: José Aliste (Universidad Andrés Bello, Chile)

Abstract:

In a previous work by using the framework of the  V-polynomial of Ellis-Monaghan and Moffatt, we introduced marked graphs, the M-polynomial and the D-polynomial and showed how the D-polynomial can be used to give a fast computation of  the expansion of the chromatic symmetric function of a graph as linear combination of chromatic symmetric functions of star forests. The D-polynomial is obtained from the M-polynomial by some relations that we call undotting relations. In this talk, we concentrate on the question of  reconstructing the M-polynomial from the D-polynomial and study the undotting relations from a polynomial algebra point of view. By using results on Gröbner bases and elimination theory, plus some quasi-homogeneous polynomials we will explain that it is not always possible to reconstruct the M-polynomial from the D-polynomial, but that the M-polynomial will belong to a polytope that can be uniquely characterized starting from the D-polynomial in combinatorial and algebraic ways. 

This is ongoing joint work with Anna de Mier, José Zamora and Rosa Orellana.

 

Date: Thursday, 3 November, 2022

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Zoom link

Title:  Archaeology of random recursive dags and Cooper-Frieze random networks

Speaker: Simon Briend (UPF)

Abstract:

We study large networks that grow dynamically over time and in particular we consider network archaeology. It is a statistical problem of inferring the past properties of such growing networks, given the current state of the network. The existing literature on network archaeology mostly focuses on the simplest possible kind of networks, that is, trees. In various models of growing random trees, it is quite well understood up to what extent one may identify the origin of the tree (i.e., the root) by observing a large unlabeled tree. We will address the more realistic problem of finding the origin of growing networks when the network is not a tree. This requires new ideas as the centrality measures that proved to be successful in trees crucially rely on properties of the trees. More concretely, we propose to investigate archaeology of networks modelled by union of uniform random recursive trees as well as a particular case of the Cooper-Frieze model, which can be interpreted as a noisy uniform random recursive tree.

Date: Thursday, 27 October, 2022

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Zoom link

Title:  Enumeration of chordal graphs with bounded tree-width

Speaker: Jordi Castellví (UPC)

Abstract: 

Tree-width is a fundamental parameter in structural and algorithmic graph theory. Graphs with tree-width at most $t$ can be defined as subgraphs of $t$-trees. A $t$-tree is a graph obtained from a $(t+1)$-clique by iteratively adding a new vertex connected to an existing $t$-clique. The asymptotic enumeration of graphs with tree-width at most $t$ is open for $t\geq 3$. This talk is devoted to the enumerative study of labelled graphs with bounded tree-width that are also chordal. A graph is chordal if it has no induced cycle of length greater than three. Chordality arises naturally in our setting, since $t$-trees are chordal, and has remarkable consequences, such as the fact that we can define the $k$-connected components of any chordal graph. With the help of analytic combinatorics, we obtain that the number of $k$-connected chordal graphs with $n$ labelled vertices and tree-width at most $t$ is of the form $cn^{-5/2}\gamma^n n!$, for some constants $c$ and $\gamma$ depending on $t$ and $k$. Additionally, the number of $i$-cliques in a uniform random $k$-connected labelled chordal graph with tree-width at most $t$ is normally distributed as $n\to\infty$.

Joint work with Michael Drmota, Marc Noy and Clément Requilé.

 

Date: Thursday, 6 October, 2022

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Zoom link

Title:  Ramsey-type properties of the binomial random graph

Speaker: Tássio Naia (LaBRI-U. Bordeaux)

Abstract:

The binomial random graph G(n,p) is a random graph obtained
from a complete graph of order n by deleting each edge with
probability 1 -p, where deletions are mutually independent.
We shall discuss recent advances in some of the following
questions (and maybe others, time permitting).

1) What subdigraphs must every orientation of G(n,p) contain?

2) Let k be an integer. For what p does G(n,p) asymptotically almost surely admit an orientation free of transitive tournaments (i.e., transitive orientations of a clique) of order k?

3) Given p, what is the largest integer t such that every orientation of G(n,p) contains every oriented tree on t vertices?

This is joint work with G.F. Barros, B.P. Cavalar, H. Hàn, G. Mota, Y. Kohayakawa, M. Pavez-Signé and M. Stein.

 

Date: Thursday, 29 September, 2022

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Zoom link

Title:  Multidimension of simple games: compact representations of voting systems

Speaker: Fabián Riquelme (Universidad de Valparaíso)

Abstract:

Simple games are mathematical structures that represent binary decision-making procedures between players, agents, or actors. Weighted voting games (WVG) are simple games usually used to represent voting systems in which the players have different powers to influence the collective decision. The WVGs can be represented as unions and/or intersections of integer vectors, i.e., compact ways of representation that help to store and understand the system's collective behavior. The dimension, codimension, and multidimension are the minimum number of WVGs such that their intersection (union, intersection/union, respectively) is the given game. We present different properties and theoretical and experimental results regarding these succinct representations that allow understanding gaps between weighted voting systems and simple games.

This is a project partially funded by Fondecyt de Iniciación 11200113 from ANID, Chile.

Joint work with Xavier Molinero, Salvador Roura, Maria Serna

Date: Thursday, 22 September, 2022

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Zoom link

Title:  The jump of the clique chromatic number of random graphs

Speaker: Dieter Mitsche (Univ. Jean Monnet, Saint-Etienne/Univ. Claude Bernard, Lyon)

Abstract:

The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In 2016 together with McDiarmid and Pralat we noted that around pm n^{-1/2} the clique chromatic number of the random graph G(n,p) changes by n^{\Omega(1)} when we increase the edge-probability p by n^{o(1)}, but left the details of this surprising phenomenon as an open problem.
We settle this problem, i.e., resolve the nature of this polynomial `jump' of the clique chromatic number of the random graph G(n,p) around edge-probability p = n^{-1/2}. Our proof uses a mix of approximation and concentration arguments, which enables us (i) to go beyond Janson's inequality used in previous work and (ii) to determine the clique chromatic number of G(n,p) up to logarithmic factors for any edge-probability p.

Joint work with Lyuben Lichev and Lutz Warnke.

 

Date: Thursday, 15 September, 2022

Time: 16.15h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Zoom link

Title:  Zero-knowledge proofs and their applications

Speaker: Marta Bellés (UPF)

Abstract:

Informally speaking, zero-knowledge proofs are cryptographic tools that allow you to prove that you know a secret without revealing it. More precisely, zero-knowledge proofs are cryptographic protocols that allow one party to convince another that a statement is true without revealing anything other than the veracity of the statement. This type of proofs were introduced in 1985 as theoretical cryptographic objects, but the appealing properties of the protocols have made them become crucial tools in many real-world applications with strong privacy issues. In this presentation I will explain the main ideas behind zero-knowledge, I will talk about the type of statements that we know can be proved with zero-knowledge, and present some of the most outstanding applications of this technology.

 

Date: Thursday, 8 September, 2022

Time: 15.00h (Barcelona time)

Where:  Room C3-005 Campus Nord UPC and Zoom link

Title:  Triality revisited

Speaker: Klara Stokes (Umeå)

Abstract:

An incidence geometry has a duality if there is a correlation permuting two of the types. A duality of order two is also called a polarity. A triality is a correlation of order three, permuting three types. Triality is a classical notion in geometry, associated with an outer automorphism of Lie groups of type $D_4$. It was first described by E. Study in 1903 and later by E. Cartan in 1925. In 1959, J. Tits classified the trialities with absolute points. These investigations motivated his definition of the generalised polygons; the content of the appendix of the same paper.

In this talk I will describe how to use coset geometries to construct examples of incidence geometries with r-alities and prescribed automorphism group. I will also describe how to construct incidence geometries with trialites using maps on surfaces as well as from voltage graphs/gain graphs.

This is joint work with Dimitri Leemans.