LIMDA Seminar
Joint seminar of GAPCOMB, together with the ALBCOM and the COMBGRAPH teams. We meet every Thursday at 16:15 at C3-005. Cookies and coffee starting at 15:30 at the lounge on the 2nd floor of C3 :)
Next talk
Date: Thursday, 25 April, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Universality for transversal Hamilton cycles
Speaker: Patrick Morris (UPC)
Abstract:
Let $\mathbf{G}=\{G_1, \ldots, G_m\}$ be a graph collection on a common vertex set $V$ of size $n$ such that $\delta(G_i) \geq (1+o(1))n/2$ for every $i \in [m]$. In this talk, we discuss a recent result showing that $\mathbf{G}$ contains every Hamilton cycle pattern. That is, for every map $\chi: [n] \to [m]$ there is a Hamilton cycle whose $i$-th edge lies in $G_{\chi(i)}$. This represents joint work with Candida Bowtell, Yanitsa Pehova and Katherine Staden.
Date: Thursday, 30 May, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Solving the List Coloring Problem trough a Branch-and-Price Algorithm
Speaker: Graciela Nasini (Universidad Nacional de Rosario)
Abstract:
We present a Branch-and-Price algorithm to solve the weighted version of the List Coloring Problem, based on a vertex cover formulation by stable sets. This problem is interesting for its applications and also for the many other problems that it generalizes, including the well-known Graph Coloring Problem. With the introduction of the concept of indistinguishable colors, some theoretical results are presented which are later incorporated into the algorithm. Extensive computational experimentation on a wide variety of instances shows the effectiveness of this approach and evidences the different behaviors that the algorithm can have according to the structure of each type of instance.
This is joint work with Mauro Lucci and Daniel Severín.
Previous talks
Date: Thursday, 18 April, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: An analytic insight on the Condorcet Paradox and other social choice problems
Speaker: Emma Caizergues (Nokia Bell Labs)
Abstract:
The phenomenon described by Condorcet in 1785, known as the Condorcet Paradox, arises when people express their preferences among candidates, yet a clear-cut winner cannot be determined.
In this talk, after introducing some required knowledge in social choice theory, I will show two methods to calculate the limiting probability of the Condorcet paradox. Additionally, this discussion will serve as an avenue to introduce other classical social choice problems, such as the No-show paradox.
Date: Thursday, 4 April, 2024
Time: 15.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Mini-workshop on Open Science
Speaker: Arantxa Sanz and Gerard Gutiérrez (CRM)
Abstract:
Since the issue of the Declaration of San Francisco (DORA) in 2012, the method to evaluate the quality of academic research has been under discussion.
This discussion has been largely centred on the overuse of the journal impact factor (JIF; ref: https://blogs.lse.ac.uk/impactofsocialsciences/2019/04/26/the-impact-of-the-journal-impact-factor-in-the-review-tenure-and-promotion-process) as an evaluation metric for researchers and institutions.
The open science paradigm and its multiple benefits cannot be successfully achieved unless such evaluation method is adapted. Significant policy and culture changes have taken place in 2021-2023 in this direction, at European/Spanish/Catalan level, which aim to facilitate such change and will impact the career assessment of academics significantly.
TALKS:
"Reforming research assessment to (actually) open science", Arantxa Sanz (Director of Strategy, Centre de Recerca Matemàtica)
"Open Science - Policy and practice at CRM", Gerard Gutiérrez (Data Steward, Centre de Recerca Matemàtica)
Date: Thursday, 21 March, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Reasoning about complexity
Speaker: Antonina Kolokolova (Memorial University)
Abstract:
What is the bound on the length of possible proofs of propositional formulas? Is P = NP? These questions, while deceptively simple to state, have eluded over half a century of concerted effort to resolve them. Could it be that the complexity of the meta-problem, of proving such computational complexity statements, is itself high -- in a formal logical sense? In this talk, I will survey what is known about the complexity of reasoning about computational complexity, in particular in the setting of bounded arithmetic, including exciting new results that appeared in the last several years.
Date: Thursday, 14 March, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Planar graphs indeed require 4-pages
Speaker: Fabian Klute (UPC)
Abstract:
An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. Accordingly, the book thickness of a class of graphs is the maximum book thickness over all its members. In this talk, I address a problem concerning the exact book thickness of the class of planar graphs, which previously was known to be either three or four.
In this talk I present planar graphs that require four pages in all of their book embeddings. Our proof uses a mix of computer-based methods and combinatorial arguments, demonstrating how computer tools can be successfully employed when tackling problems of this kind.
Date: Thursday, 29 February, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: The Erdös–Rényi random graph conditioned on being a cluster graph
Speaker: Marc Noy (UPC)
Abstract:
A cluster graph is a disjoint union of complete graphs. We consider the random G(n,p) graph on n vertices with connection probability p, conditioned on the rare event of being a cluster graph. There are three main motivations for our study.
1) For p = 1/2, each random cluster graph occurs with the same probability, resulting in the uniform distribution over set partitions. Interpreting such a partition as a graph adds additional structural information.
2) To study how the law of a well-studied object like G(n,p) changes when conditioned on a rare event; an evidence of this fact is that the conditioned random graph overcomes a phase transition at p=1/2 (not present in the dense G(n,p) model).
3) The original motivation was an application to community detection. Loosely speaking, a community is a subgraph that is more densely connected than the whole graph. From that perspective, a cluster graph has a strong community structure.
This is joint work with Martijn Gösgens, Lukas Lüchtrath, Elena Magnanini and Élie de Panafieu
Date: Thursday, 22 February, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Enumeration, structure and generation of triangular partitions and their generalizations
Speaker: Alejandro Galván (UPC)
Abstract:
An integer partition is said to be triangular if its Ferrers diagram can be separated from its complement as a subset of N² by a straight line. In this talk, we will explore various characterizations and properties of these objects. We will study the poset of triangular partitions ordered by containment and we will derive some enumeration formulas, obtaining, as a byproduct, a new proof of Lipatov's enumeration theorem for balanced words. We will also present an algorithm that generates all the triangular partitions of a given size, which is significantly more efficient than previous ones. Finally, we will briefly comment on how this research can be extended to higher dimensional analogues, as well as to other generalizations which arise by allowing convex or concave curves (instead of straight lines) to separate the diagram.
Date: Thursday, 15 February, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Reconstruction of token graphs
Speaker: Ana Trujillo (Universidad de Chile)
Abstract:
Let $k$ and $n$ be positive integers with $1\le k\le n-1$, and let $G$ be a graph of order $n$. The $k$-token graph, denoted $F_k(G)$, of a graph $G$ is the graph whose vertices are all the $k$-subsets of vertices of $G$, and two such $k$-subsets are adjacent whenever their symmetric difference is an edge of $G$. Token graphs have been used to study the Isomorphism Problem in graphs, and they have some applications in Coding Theory and Physics. We say that $G$ is a $(C_4,D_4)$-free graph if $G$ does not contain a copy of $C_4$ nor $D_4$ as a subgraph, where $C_4$ denotes the cycle on four vertices and $D_4$ is the diamond graph (a $4$-cycle with a chord). In 2012, Fabila-Monroy et al. conjectured that if $G$ and $H$ are two graph such that $F_k(G)$ and $F_k(H)$ are isomorphic for some $k$, then $G$ and $H$ are also isomorphic. In this talk, we will show this conjecture for the family of $(C_4,D_4)$-free graphs, and moreover, we will discuss how this reconstruction problem is related to the automorphism group of token graphs.
Date: Thursday, 1 February, 2024
Time: 16.15h (Barcelona time)
Where: Room A6104 in Campus Nord UPC and Meet link
Title: On numerical semingroups
Speaker: Maria Bras Amorós (URV)
Abstract:
A numerical semigroup is a subset of the nonnegative integers that is closed under addition and has a finite complement in $N$. This complement of the numerical semigroup is called its gap set and the number of gaps is its genus. Numerical semigroups arise in algebraic geometry, coding theory, privacy models, and in musical analysis. It has been shown that the sequence counting the number of semigroups of each given genus g, denoted $n_g$, for $g\geq 0$, has a Fibonacci-like asymptotic behavior. It is still not proved that, for each g, $n_{g+2} >= n_{g+1} + n_g$ or, even more simple, $n_{g+1} >= n_g$. We will explain these conjectures together with some classical problems on numerical semigroups and we will explain the approach of counting semigroups by means of trees.
Date: Thursday, 25 January, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Logics for Algorithmic Graph Minors
Speaker: Dimitrios Thilikos (CNRS)
Abstract:
The Graph Minors series of Robertson and Seymour, apart from its seminal importance in modern combinatorics, offered a wealth of graph algorithmic techniques. These techniques were mainly developed for the derivation of a cubic-time algorithm for the disjoint paths problem (for fixed number of terminals) and have been extensively used for the design of parametrized graph algorithms. We present a series of meta-algorithmic results that attempt to abstract away these algorithmic techniques and make them automatically applicable to wide families of problems. For this we present two logics whose expressive power lies between FOL an MSOL. Problems expressible in these logics admits a parametrized algorithm on classes of graphs excluding some graph as a (topological) minor.
Date: Thursday, 14 December, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Moser-Tardos Algorithm with small number of random bits
Speaker: Oleg Pikhurko (University of Warwick)
Abstract:
We present a variant of the parallel Moser-Tardos Algorithm and show that, for a class of problems whose dependency graphs have some subexponential growth, the expected number of random bits used by the algorithm is constant. In particular the expected number of used random bits is independent from the total number of variables. This is achieved by using the same random bits to resample variables which are far enough in the dependency graph.
Joint work with E.Csoka, L.Grabowski, A.Mathe and K.Tyros.
Date: Thursday, 30 November, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Problems in NP can Admit Double-Exponential Lower Bounds when
Parameterized by Treewidth and Vertex Cover
Speaker: Fionn Mc Inerney (Technical University of Vienna)
Abstract:
Treewidth serves as an important parameter that, when bounded, yields tractability for a wide class of problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and QUANTIFIED SAT are fixed-parameter tractable parameterized by the treewidth of the input's (primal) graph plus the length of the MSO-formula [Courcelle, Information & Computation 1990] and the quantifier rank [Chen, ECAI 2004], respectively. The algorithms generated by these (meta-)results have running times whosedependence on treewidth is a tower of exponents. A conditional lower bound by Fichte, Hecher, and Pfandler [LICS 2020] shows that, for QUANTIFIED SAT, the height of this tower is equal to the number of quantifier alternations. These types of lower bounds, which show that at least double-exponential factors in the running time are necessary are rare: there are only a handful of such lower bounds (for treewidth and vertex cover parameterizations) and all of them are for problems that are #NP-complete, Sigma_2^p-complete, Pi_2^p-complete, or complete for even higher levels of the polynomial hierarchy.
We demonstrate, for the first time, that it is not necessary to go higher up in the polynomial hierarchy to achieve such lower bounds: we derive double-exponential lower bounds in the treewidth (tw) and the vertex cover number (vc) for well-studied NP-complete graph problems. Specifically, we design a technique to obtain such lower bounds and show its versatility by applying it to three different problems: METRIC DIMENSION, STRONG METRIC DIMENSION, and GEODETIC SET. We prove that these problems do not admit 2^{2^{o(tw)}} * n^{O(1)}-time algorithms, even on bounded diameter graphs, unless the ETH fails. In fact, for STRONG METRIC DIMENSION, the double-exponential lower bound holds even for the vertex cover number. Such a phenomenon is not possible for METRIC DIMENSION and GEODETIC SET as they admit simple 2^{O(vc^2)} * n^{O(1)}-time algorithms. We further show that, unless the ETH fails, they do not admit 2^{o(vc^2)} * n^{O(1)}-time algorithms, thereby adding to the sparse list of problems that admit such lower bounds. We note that our lower bounds for the vertex cover parameterizations also yield lower bounds on the vertex-kernel sizes of these problems, which are very rare results as well. We further complement all our lower bounds with matching upper bounds.
In particular, for the lower bounds, we design and use a novel, yet simple technique based on Sperner families of sets. Most importantly, we are convinced that the amenability of our technique will lead to obtaining such lower bounds for many other problems in NP.
Date: Thursday, 23 November, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: The chromatic number of a random lift of K_d
Speaker: Xavier Pérez-Giménez (University of Nebraska-Lincoln)
Abstract:
An n-lift of a graph G is a graph from which there is an n-to-1 covering map onto G. Amit, Linial, and Matousek (2002) raised the question of whether the chromatic number of a random n-lift of K_5 is concentrated on a single value. We consider a more general problem, and show that for fixed d>=3 the chromatic number of a random lift of K_d is (asymptotically almost surely) either k or k+1, where k is the smallest integer satisfying d < 2k log k. Moreover, we show that, for roughly half of the values of d, the chromatic number is concentrated on k. The argument for the upper-bound on the chromatic number uses the small subgraph conditioning method, and it can be extended to random n-lifts of G, for any fixed d-regular graph G. (This is joint work with JD Nir.)
Date: Thursday, 16 November, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Separating path systems of graphs
Speaker: Tássio Naia (CRM)
Abstract:
A set S separates elements a, b if S intersects {a,b} in a single element. How many sets are needed to separate all pairs of (distinct) elements in a set? What if restrictions are placed on which sets can be used? The study of the so-called separating families dates back to information-theoretic problems investigated by Rényi [On random generating elements of a finite boolean algebra, Acta Scientiarum Mathematicarum Szeged 22 (1961), no. 1--2, pp. 75--81].
About 10 years ago, G.O.H. Katona proposed the problem of finding the smallest size of a separating family P for the edges of an arbitrary graph G, where each member of P is a path in $G$.
We shall discuss recent developments in this area, confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhár [On the path separation number of graphs, Discrete Applied Mathematics. 213 (2016), 26--33] and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan [Separating path systems, Journal of Combinatorics. 5 (2014), no. 3, 335--354].
This is joint work with Fábio Botler, Marthe Bonamy, François Dross and Jozef Skokan.
Date: Tuesday, 7 November, 2023
Time: 17.10h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Cycle Partitions in Regular Directed Graphs
Speaker: Mehmet Akif Yildiz (University of Amsterdam)
Abstract:
A Hamilton cycle in a (directed) graph is a (directed) cycle that visits every vertex. A conjecture of Jackson from 1981 states that every d-regular oriented graph (directed graph with no 2-cycles) on n vertices with d >= n/4 has a Hamilton cycle. We verify this conjecture for large n by proving a more general result about cycle partitions in (dense) regular directed graphs and oriented graphs: for k>1 and sufficiently large n,
- every d-regular directed graph on n vertices with d>=n/k can be covered by at most k-1 vertex-disjoint cycles.
- every d-regular oriented graph on n vertices with d>=n/2k can be covered by at most k-1 vertex disjoint cycles.
This is joint work with Allan Lo (University of Birmingham) and Viresh Patel (Queen Mary University of London).
Date: Tuesday, 7 November, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Sidon Ramsey Numbers
Speaker: Amanda Montejano (Universidad Nacional Autónoma de México)
Abstract:
A subset S of an additive group G is called a Sidon set if the sum of any two elements (possibly equal) of S are distinct; equivalently, the differences of any two distinct elements of S are unique. We present several results concerning the Sidon set problem and it’s corresponding version in Ramsey theory.
Date: Thursday, 26 October, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Finding and counting patterns in sparse graphs.
Speaker: Suchismita Mishra (Universidad Andrés Bello)
Abstract:
In this talk, we are interested in finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in fast, constant-space and polynomial-time algorithms respectively. We discover two new parameters that we call matched treedepth and matched treewidth. We show that, for many patterns, finding and counting patterns with low matched treedepth and low matched treewidth can be done asymptotically faster than the existing algorithms when the host graphs are sparse.
Date: Tuesday, 31 October, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Cover and Hitting Times of Hyperbolic Random Graphs
Speaker: Marcos Kiwi (U. Chile)
Abstract:
We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range (2,3). In particular, we focus on the expected times for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that, a.a.s. (with respect to the HRG), up to multiplicative constants: the cover time is n*(log(n))^2, the maximum hitting time is n*log(n), and the average hitting time is n. We then determine the expected time to commute between two given vertices a.a.s., up to a small factor polylogarithmic in n, and under some mild hypothesis on the pair of vertices involved. We prove these results by determining the effective resistance either between a typical vertex and the well-connected "center" of HRGs or between an appropriately chosen collection of extremal vertices.
In order to make the talk self-contained, no previous background on HRGs will be assumed.
Joint work with Markus Schepers (Johannes-Gutenberg-U. Mans, Mainz, Germany) and John Sylvester (U. of Liverpool, UK).
Date: Thursday, 5 October, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: The probability of non-existence of small substructures in moderately sparse random objects.
Speaker: Rui Zhang (UPF)
Abstract:
I will talk about the asymptotic probability of non-existence of small substructures in random objects.
In particular, we will cover the following topics:
the non-existence of small subhypergraphs in random hypergraphs,
the limiting distribution of maxima of various extension counts in random graphs,
and the asymptotic enumeration of Eulerian orientations, Eulerian digraphs, and Eulerian oriented graphs.
The content is based on papers with my coauthors:
Mikhail Isaev, Brendan McKay, Igor Rodionov, Nick Wormald and Maksim Zhukovskii
Date: Thursday, 28 September, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: New limits of trees, graphs and partitions
Speaker: Benedikt Stufler (TUWien)
Abstract:
We discuss new limits of selected classes of combinatorial structures. This includes stochastic process limits of composition schemes, a new family of scaling limits for random trees, and the first scaling limit of a planar graph model (as opposed to planar maps).
Date: Thursday, 21 September, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: The canonical Ramsey theorem in random graphs: even cycles and list constraints
Speaker: Patrick Morris (UPC)
Abstract:
The celebrated canonical Ramsey theorem of Erd\H{o}s and Rado implies that for a given graph $H$, if $n$ is sufficiently large then any colouring of the edges of $K_n$ gives rise to copies of $H$ that exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions of this result and the threshold at which the random graph $G(n,p)$ inherits the canonical Ramsey properties of $K_n$. We will discuss a theorem that pins down this threshold when we focus on colourings that are constrained by some prefixed lists and also a related result on the threshold for the canonical Ramsey property (with no list constraints) in the case that $H$ is an even cycle. This represents joint work with José D. Alvarado, Yoshiharu Kohayakawa and Guilherme O. Mota.
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.
Date: Thursday, 20 April, 2023
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Transversal cycle factors in multipartite graphs
Speaker: Amarja Kathapurkar (Birmingham)
Abstract:
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
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Refuting Graph Colorability with Semi-definite Programming
Speaker: Kilian Rothmund (UPC - Ulm University)
Abstract:
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 Kt-minor free graphs by Robertson and Seymour as follows: we identify a (parameterized) graph Ht and we prove that if we replace Kt by Ht, 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 Ht, the appearance of vortices is unavoidable. Using the above decomposition theorem, we design an algorithm that, given an Ht-minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. This algorithm yields, on Ht-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 Ht 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.
Date: Tuesday, 28 June, 2022
Time: 11:30 (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: The Kahn-Kalai conjecture on thresholds
Speaker: Patrick Morris (UPC)
Abstract:
Ever since the work of Erdős and Rényi pioneering the study of random graphs, one of the central themes of the subject has been to determine the location of the threshold for certain graph properties; the critical probability at which the property switches from being very unlikely to very likely. For many examples of interest, such as the appearance of (possibly spanning) subgraphs, one can obtain lower bounds on thresholds by running simple expectation calculations. In this reading seminar, we will discuss the recent solution of a surprising conjecture of Kahn and Kalai from 2006, that states that these expectation calculations are actually never far from the truth and that they differ from the true value of the threshold by at most a factor of log n. The conjecture is very general and has many important implications in the study of random graph thresholds.
Until a couple of years ago this conjecture seemed far out of reach and it was not even clear whether one should try to prove it or try to find a counterexample. This makes the solution of this conjecture, posted by Park and Pham in March this year, a truly remarkable result and perhaps even more surprising is that their proof is only 5 pages and, by all accounts, a very elegant argument using no heavy machinery. Although this result came as a huge surprise in the community, it builds on the ideas of several big breakthroughs in recent years. Indeed, in 2019, Frankston, Kahn, Narayanan and Park posted the proof of a fractional version of the Kahn-Kalai conjecture, a weaker form of the conjecture that still has far-reaching implications. In turn, the proof in that paper (now in Annals) adopts ideas of another big breakthrough (also in Annals) to a seemingly unrelated problem known as the Erdős-Rado Sunflower problem.
This talk is a taster session for an upcoming reading seminar where we will look at the remarkable recent proof of the Kahn-Kalai conjecture, due to Park and Pham, and several papers that led to this breakthrough. This seminar is planned to start in September.
Date: Thursday, 2 June, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Perfect codes of circulant graphs of degree $p^l-1$
Speaker: Xiaomeng Wang (Lanzhou University, UPC)
Abstract:
A perfect code in a graph is an independent set $D$ such that every vertex not in $D$ is adjacent to exactly one vertex in $D$. We will review the known results on perfect codes in circulant graphs and present a new characterization on the existence and structure of perfect codes in circulant graphs of degree a power of a prime minus one.
Date: Thursday, 26 May, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Absolutely maximally entangled states: a combinatorial and geometric view
Speaker: Simeon Ball (UPC)
Abstract:
I will assume no prior knowledge of Hilbert spaces or quantum mechanics. This talk is aimed at researchers in graphs and combinatorial geometry.
In this talk I will briefly explain the concept of entanglement in quantum mechanics and define what is an absolutely maximally entangled state of the Hilbert space $({\mathbb C}^q)^{\otimes n}$. In the qubit case ($q=2$) I will sketch a link between such states and simple graphs and by doing so, we will see that it is not difficult to classify all absolutely maximally entangled states of $({\mathbb C}^2)^{\otimes n}$ that have a stabiliser group.
The case $q>2$ is more complicated as simple graphs can no longer be used to describe the states. We can however, find an equivalence to a set of $n$ lines $\mathcal X$ in the finite projective space PG$(n-1,q)$.
In the case $q=2$ (and for simplicity assuming $n$ is even), it is well known that this set of lines $\mathcal X$ has two properties namely, that every co-dimensional two subspace intersects an even number of lines of $\mathcal X$ and any subset of $\frac{1}{2}n$ lines of $\mathcal X$ span the entire space.
The smallest parameters for which it is not known if there is an absolutely maximally entangled state is the Hilbert space $({\mathbb C}^4)^{\otimes 8}$.
In this talk I will explain ongoing work with Edgar Moreno in which we prove that for $q=4$ an
absolutely maximally entangled state (which has a stabiliser group) is equivalent to a set of lines in a finite projective space with a property similar to that for $q=2$. I will explain how we hope to classify all such sets of lines and thereby determine if there is an absolutely maximally entangled state in the Hilbert space $({\mathbb C}^4)^{\otimes 8}$ or not.
Date: Thursday, 19 May, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: The Semi-Random Tree Process
Speaker: Sofiya Burova (ENS Lyon)
Abstract:
The online semi-random graph process is a one-player game which starts with the empty graph on n vertices. At every round, a player (called Builder) is presented with a vertex v chosen uniformly at random and independently from previous rounds, and constructs an edge of his choice that is incident to v. Inspired by recent advances on the semi-random graph process, we define a family of generalised online semi-random models. Then, we analyse a particular instance that shares similar features with the original semi-random graph process and study the hitting times of classical graph properties.
Joint work with Lyuben Lichev.
Date: Thursday, 12 May, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Moore's problem in its bipartite biregular version
Speaker: Gabriela Araujo-Pardo (Instituto de Matemáticas, UNAM)
Abstract:
Date: Thursday, 28 Apr, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Optimization, Testing, Learning of Deterministic Finite State Machines
Speaker: Alberto Larrauri (TU Graz)
Abstract:
Finite state machines are a formalism used to describe a wide array of
reactive systems. Among them, finite automata are machines that either
accept or reject each input word. We give an overview of three closely-
linked problems related to deterministic finite automata (DFA):
optimization, testing and learning. In the optimization problem, we are
given a classification of input words and the goal is to obtain a
smallest automaton consistent with that information. In conformance
testing, we begin with a DFA A and a bound k, and we are asked to
produce a small set of words distinguishing A from all other (non-
equivalent) automata containing at most k states. Lastly, in active
learning the task is to infer a model of a black-box automaton through
limited interaction with an oracle called a "minimally adequate
teacher". Finally, we briefly discuss extensions of these problems
where instead of considering a single machine in isolation, we study
multiple ones that interact with each other and showcase some recent
results.
Date: Thursday, 21 Apr, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Ramsey Multiplicity and Search Heuristics
Speaker: Christoph Spiegel (Zuse Institute Berlin)
Abstract:
We present several new improved and tight asymptotic bounds relating both to the minimum number of monochromatic cliques contained in any edge-coloring of a complete graph as well as the minimum number of cliques in graphs with bounded independence number. Most notably, we present an improvement in the upper bound of the K4 and K5 Ramsey multiplicity and introduce a notion of off-diagonal Ramsey multiplicity. The upper bounds are established through graph and Cayley graph constructions found through well-established computer search heuristics.
Date: Thursday, 21 Apr, 2022
Time: 17.00h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Stability of Erdős-Ko-Rado Theorems in Circle Geometries
Speaker: Sam Adriaensen (Vrije Universiteit Brussel)
Abstract:
Techniques from algebraic graph theory have proven to be quite powerful in solving combinatorial problems. Especially for solving Erdős-Ko-Rado problems. There, one takes an incidence structure consisting of points and blocks (which are sets consisting of points), and one wonders what the largest families of blocks is such that they have pairwise non-empty intersection. In a lot of cases, the largest families are the trivial ones, where you fix a point and just take all blocks containing this point. In a lot of settings, one can prove that these are the only examples of maximum size, using the Hoffman ratio bound.
Often, the limitations of these techniques are that you can only say something about the intersecting families of maximum size. In this talk I will show that we can do better. The incidence structures under investigation are circle geometries. They are typically constructed by taking a quadratic surface Q in 3-dimensional projective space PG(3,q). The non-trivial plane sections of Q are called circles. The points and blocks of the circle geometries are the points and circles respectively of Q. Using the expander mixing lemma, we cannot only prove that the largest intersecting families are of size q² ± O(q), but that all intersecting families of size 1/√2 q² + O(q) are trivial (i.e. they consist of circles through a fixed point).
Date: Thursday, 7 Apr, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Número Sidon-Ramsey en Z_n
Speaker: Luis Miguel Delgado Ordoñez (Universidad del Cauca)
Abstract:
El problema de los conjuntos de Sidon es un problema clásico en la Teoría Combinatoria de Números, del cual daré una breve introducción. Posteriormente, expondré la versión en coloraciones de dicho problema y explicaré su conexión con el teorema de Rado en la teoría de Ramsey donde apareció el denominado Número Sidon-Ramsey. Finalmente, presentaré los resultados obtenidos en la investigación adelantada del Número de Sidon-Ramsey en grupos cíclicos.
Date: Thursday, 7 Apr, 2022
Time: 17.00h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Construcciones combinatorias de códigos
ortogonales ópticos
Speaker: Hamilton Mauricio Ruiz (Universidad del Cauca)
Abstract:
Los códigos ortogonales ópticos COOs, se definen como un conjunto de secuencias de peso constante con buenas propiedades de autocorrelación y correlación cruzada. Desde su aparición en 1989, varias son las áreas de las matemáticas encargadas de la búsqueda y diseño de construcciones explícitas de COOs, una de ellas es la combinatoria. En esta charla explicaremos algunas herramientas combinatorias utilizadas en la construcción de códigos ortogonales ópticos, especialmente aquellas construcciones que utilizan el concepto de cuadrados latinos mutuamente ortogonales y conjuntos de Sidon modulares.
Date: Thursday, 31 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Schur properties of randomly perturbed sets
Speaker: Patrick Morris (UPC)
Abstract:
A set $A$ of integers is said to be Schur if any two-colouring of $A$ results in monochromatic $x,y$ and $z$ with $x+y=z$. We discuss the following problem: how many random integers from $[n]$ need to be added to some $A\subseteq [n]$ to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when $|A|> \ceil{4n/5}$, no random integers are needed, as $A$ is already guaranteed to be Schur. Recently, Aigner-Horev and Person showed that for any dense set of integers $A\subseteq [n]$, adding $\omega(n^{1/3})$ random integers suffices, noting that this is optimal for sets $A$ with $|A|\leq \ceil{n/2}$.
We close the gap between these two results by showing that if $A\subseteq [n]$ with $|A|=\ceil{n/2}+t<\ceil{4n/5}$, then adding $\omega(\min\{n^{1/3},nt^{-1}\})$ random integers will with high probability result in a set that is Schur. Our result is optimal for all $t$, and we further initiate the study of perturbing sparse sets of integers $A$ by providing nontrivial upper and lower bounds for the number of random integers that need to be added in this case.
Joint work with Shagnik Das and Charlotte Knierim.
Date: Thursday, 24 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Characterization of the extremal families for the Kruskal-Katona's inequality
Speaker: Lluís Vena (UPC)
Abstract:
Given $S$ a family of sets of size $k$ in $[n]$, its lower shadow $\Delta(S)$ is the family of sets of size $k-1$ which are contained in at least one set of the family. The celebrated Kruskal-Katona theorem gives the minimum size of $\Delta(S)$ in terms of the size of $S$. F\"uredi and Griggs (and M\"ors) showed that the extremal families for this shadow minimization problem in the Boolean lattice are unique for some cardinalities and asked for a general characterization of these extremal families.
In this talk we present a new combinatorial inequality from which yet another simple proof of the Kruskal--Katona theorem can be derived. The inequality can be used to obtain a characterization of the extremal families for this minimization problem, giving an answer to the question of F\"uredi and Griggs. Some known and new additional properties of extremal families can also be easily derived from the inequality.
Join work with Oriol Serra.
Date: Thursday, 17 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Path decompositions of random directed graphs
Speaker: Alberto Espuny (TU Ilmenau)
Abstract:
In this talk we consider the problem of decomposing the edges of a directed graph into as few paths as possible. The minimum number of paths needed in such an edge decomposition is called the path number of the digraph.
The problem of determining the path number is generally NP-hard. However, there is a simple lower bound for the path number of a digraph in terms of its degree sequence, and a conjecture of Alspach, Mason, and Pullman from 1976 states that this lower bound gives the correct value of the path number for any even tournament. The conjecture was recently resolved, and in this talk I will discuss to what extent the conjecture holds for other digraphs. In particular, I will discuss some of the ingredients of a recent result showing that the conjecture holds with high probability for the random directed graph D(n,p) for a large range of p.
This is joint work with Viresh Patel and Fabian Stroh.
Date: Thursday, 10 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Higher sumsets and approximate groups
Speaker: Arindam Biswas (U. of Copenhagen)
Abstract:
Let G be an abelian group and A be any non-empty, finite subset. For the integers, the structure of the higher sumsets mA with $m\geq 1$ was investigated by Nathanson in the 1970s. Recent works of Granville-Walker, Lev, etc. have improved some of the bounds of Nathanson and Granville-Shakan-Walker also investigated higher sumsets in $Z^d$. We will discuss these results and their relationship to approximate groups.
Date: Thursday, 3 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Marked graphs and the chromatic symmetric function
Speaker: Anna de Mier (UPC)
Abstract:
In the mid 90s Stanley introduced the chromatic symmetric function, a
symmetric function analogue of the chromatic polynomial, and he asked
whether it determines trees up to isomorphism. Motivated by this
question and with the aim of better understanding the chromatic
symmetric function, we introduce a class of marked graphs (that is,
graphs with vertices weighted by elements of a semigroup) and a
polynomial on them defined via deletion-contraction. From this
polynomial, that we call the M-polynomial, one can compute the expansion
of the chromatic symmetric function in terms of the chromatic symmetric
functions of stars (which give rise to a basis for symmetric functions).
We then explain how these results could be used to approach Stanley's
question and carry out the program for trees up to diameter five
satisfying a mild extra condition.
This is joint work with José Aliste-Prieto, Rosa Orellana and José Zamora.
Date: Thursday, 24 Feb, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Some problems on randomly perturbed graphs
Speaker: Alberto Espuny (TU Ilmenau)
Abstract:
The theory of randomly perturbed graphs has seen tremendous growth in recent years. This theory serves to interpolate between classical results in extremal graph theory and the theory of random graphs. Given some property P that we wish to study (say, the containment of a given spanning structure), the idea is to consider a deterministic graph H which does not satisfy P and a random graph G=G(n,p) which is very unlikely to satisfy P, and study whether the union of H and G will satisfy P. In particular, we aim to obtain the best possible combinations of parameters for H and G that will yield P with high probability.
Date: Wednesday, 26 Jan, 2022
Time: 14.30h (Barcelona time)
Where: G-meet: meet.google.com/fty-utgm-qxq
Title: Probabilistic and Extremal studies in Additive Combinatorics
Speaker: Max Wötzel (UPC)
Ph.D. defence, Thesis director: Rué, Juanjo | Serra, Oriol
Abstract:
The results in this thesis concern extremal and probabilistic topics in number theoretic settings. We prove sufficient conditions on when certain types of integer solutions to linear systems of equations in binomial random sets are distributed normally, results on the typical approximate structure of pairs of integer subsets with a given sumset cardinality, as well as upper bounds on how large a family of integer sets defining pairwise distinct sumsets can be. In order to prove the typical structural result on pairs of integer sets, we also establish a new multipartite version of the method of hypergraph containers, generalizing earlier work by Morris, Saxton and Samotij.
Date: Monday, 20 Dec, 2021
Time: 15.00h (Barcelona time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: Deviation Probabilities for arithmetic progressions
Speaker: Oriol Serra (UPC)
Abstract:
The study of large deviations on the expected number of arithmetic
progressions on a random set of the first N positive integers has a rich
history, parallel to the study of large deviations on subgraph counts of
the random graph G(n,p).
Goldsmith, Griffiths and Scott introduced a new approach using
martingale methods to analyze moderate deviations in subgraph counts in
G(n,m). In the talk an adaption of the method to count arithmetic
structures given by solutions of a linear system in an abelian group is
presented. The method reduces to the general problem of counting edges
in random hypergraphs. Exponential bounds for moderate deviations in
edge counting are then translated to the arithmetic setting. The bounds
for the counting of edges in hypergraphs are seen to be essentially best
possible.
Joint work with Gonzalo Fiz-Pontiveros, Simon Griffiths and Mattheus Secco
Date: Monday, 13 Dec, 2021
Time: 14.00h (Barcelona time)
Where: online at https://meet.google.com/uve-zvxj-wdr
Title: Threshold phenomena involving the connected components of random graphs and digraphs
PhD Defense COULSON, MATTHEW JOHN
Advisor: PERARNAU LLOBET, GUILLEM
Speaker: Mathew Coulson (UPC)
Abstract:
We consider some models of random graphs and directed graphs and investigate their behavior near thresholds for the appearance of certain types of connected components. Firstly, we look at the critical window for the appearance of a giant strongly connected component in binomial random digraphs. We provide bounds on the probability that the largest strongly connected component is very large or very small. Next, we study the configuration model for graphs and show new upper bounds on the size of the largest connected component in the subcritical and barely subcritical regimes. We also show that these bounds are tight in some instances. Finally we look at the configuration model for random digraphs. We investigate the barely sub-critical region and show that this model behaves similarly to the binomial random digraph whose barely sub- and super-critical behaviour was studied by Luczak and Seierstad. Moreover, we show the existence of a threshold for the existence of a giant weak component, as predicted by Kryven.
Date: Monday, 29 Nov, 2021
Time: 15.00h (Barcelona time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: Four families of polynomials in spectral graph theory
Speaker: Miquel Àngel Fiol (UPC)
Abstract:
In this talk we describe four families of polynomials related to the spectrum of a graph. First, some known main results involving such polynomials, such as the spectral excess theorem characterizing distance-regularity, are discussed. Second, some new results giving bounds for the $k$-independence number $\alpha_k$ of a graph are presented. In this context, we comment on some relationships between the inertia (Cvetkovi\`c) and ratio (Hoffman) bounds of $\alpha_k$.
Date: Wednesday, 24 Nov, 2021
Time: 15.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Roberto Imbuzeiro Oliveira (IMPA)
Link: https://randnet.upc.edu/seminar/
Date: Monday, 22 Nov, 2021
Time: 14.00h (Barcelona time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: Hermitian self-orthogonal codes
Speaker: Simeon Ball (UPC)
Abstract:
Let $C$ be a $[n,k]_{q^2}$ linear code, i.e. a $k$-dimensional subspace of ${\mathbb F}_{q^2}^n$.
$C$ is linearly equivalent to a Hermitian self-orthogonal code if and only if there are non-zero $\lambda_i \in {\mathbb F}_{q}$ such that $$\sum_{i=1}^n \lambda_{i} u_{i}v_{i}^q=0,$$ for all $u,v \in C$.
For any linear code $C$ over ${\mathbb F}_{q^2}$ of length $n$, Rains defined the {\em puncture code} $P(C)$ to be $$P(C)=\{\lambda=(\lambda_{1},\ldots,\lambda_n) \in {\mathbb F}_q^n \ | \ \sum_{{i}=1}^n \lambda_{i} u_{i}v_{i}^q=0, \ \mathrm{for} \ \mathrm{all} \ u,v \in C \}.$$
There is a truncation of a linear code $C$ over ${\mathbb F}_{q^2}$ of length $n$ to a linear over ${\mathbb F}_{q^2}$ of length $r \leqslant n$ which is linearly equivalent to a Hermitian self-orthogonal code if and only if there is an element of $P(C)$ of weight $r$.
Rains was motivated to look for Hermitian self-orthogonal codes, since there is a simple way to construct a $ [\![ n,n-2k]\!] _q$ quantum code, given a Hermitian self-orthogonal code. This construction is due to Ketkar et al, generalising the ${\mathbb F}_4$-construction of Calderbank et al.
In this talk, I will detail an effective way to calculate the puncture code. I will outline how to prove various results about when a linear code has a truncation which is linearly equivalent to a Hermitian self-orthogonal linear code and how to extend it to one that does in the case that it has no such truncation. In the case that the code is a Reed-Solomon code, it turns out that the existence of such a truncation of length $r$ is equivalent to the existence of a polynomial $g(X)$ of degree at most $(q-k)q-1$ with the property that $g(X)+g(X)^q$ has $q^2-r$ distinct zeros.
(joint work with Ricard Vilar)
Date: Monday, 15 Nov, 2021
Time: 15.00h (Barcelona time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: Counting rooted 3-connected bipartite planar maps
Speaker: Marc Noy (UPC)
Abstract:
We provide the first solution to the problem of counting (rooted) 3-connected bipartite planar maps. Our starting point is the enumeration of bicolored planar maps by number of monochromatic edges, following the work of Bernardi and Bousquet-Mélou in J. Comb. Theory Ser. B, 101 (2011), 315--377. The decomposition of a map into 2- and 3-connected components allows us to obtain the generating functions of 2- and 3-connected bicolored maps. Setting to zero the variable marking monochromatic edges we obtain the generating function of 3-connected bipartite maps, which is algebraic of degree 26. We deduce from it an asymptotic estimate for the number of 3-connected bipartite planar maps of the form g^n/n^(5/2), where g = 1/r = 2.40958 and r is an explicit algebraic number of degree 10.
This is joint work in progress with Clément Requilé and Juanjo Rué.
Date: Monday, 8 Nov, 2021
Time: 15.00h (Barcelona time)
Where: Room C3001 Campus Nord UPC
Title: On a notion of homomorphisms for graphs embedded on surfaces, and its poset of cores
Speaker: Lluís Vena (UPC)
Abstract: A graph homomorphism between two graphs is a mapping between the corresponding vertex sets that sends edges to edges. We present a homomorphism notion between graphs embedded on (non-necessarily orientable) surfaces, also known as maps, that is graph homomorphism between graphs, yet it preserves the topology they are embedded in (namely its sign genus). Furthermore, we define a core of a map in an analogous way as for graphs, give a characterization of when a map is a core (in terms of the contractible cycles of the map), and we study the properties of the poset of cores, showing that it behaves radically different than in the case of graphs (for instance, there is no dense totally ordered interval).
Joint work with Delia Garijo and Andrew Goodall.
Date: Wednesday, 27 Oct, 2021
Time: 14.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Martin Balko (Charles University Prague)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 29 Sep, 2021
Time: 16.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Louigi Addario-Berry (McGill University)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 15 Sep, 2021
Time: 15.00h (Barcelona time) (Watch out: exceptional time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: (Maximal) Independet Sets in Various Random Graph Classes
Speaker: Michael Drmota (TU Wien)
Abstract:
The purpose ot this talk is to discuss the following two questions for
random series-parallel graphs and random co-graphs:
- How many (maximal) independent sets can we expect for a typical graph of this kind?
- Does there typically exist an independent set of linear size?
Interestingly, in both graph classes we can expect exponentially many independent sets,
whereas independent sets of linear size exist typically only for series-parallel graphs.
This talk is based on the following two papers:
M. Drmota, L. Ramos, C. Requile, and J. Rue, Maximal independent sets and maximal matchings in series-parallel and related graph classes, The Electronic Journal of Combinatorics 27 (1), P1.5, 2020.
Frédérique Bassino, Mathilde Bouvel, Michael Drmota, Valentin Féray, Lucas Gerin, Mickaël Maazoun, Adeline Pierrot, Linear-sized independent sets in random cographs and increasing subsequences in separable permutations, arXiv:2104.07444.
Date: Wednesday, 30 Jun, 2021
Time: 15.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Maya Stein (Santiago de Chile) and James Martin (Oxford)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 02 Jun, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Geometry of high genus maps
Speaker: Baptiste Louf (Uppsala)
Abstract: Maps are discrete surfaces built by gluing polygons along their sides (or, alternatively, they can be seen as graphs embedded in surfaces). They have been given a lot of attention for several decades now, and in this talk we will be interested in the geometric properties of large random maps.
This question has been well studied in the case of planar maps (i.e. maps of the sphere), and more recently extended to any surface when the topology is fixed. Here, we are interested in yet another regime, that we call high genus maps, in which the genus of the surface grows at the same time as the size. These objects naturally exhibit hyperbolic properties. I will give an overview of the existing results and open problems.
Date: Wednesday, 26 May, 2021
Time: 15.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Lutz Warnke (GATech)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 19 May, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: On Motzkin's problem in the circle group
Speaker: Pablo Candela (UAM)
Abstract: Given a finite subset $D$ of the interval $(0,1)$, if a Borel set $A\subset [0,1)$ contains no pair of elements whose difference modulo 1 is in $D$, then how large can the Lebesgue measure of $A$ be? This is the analogue in the circle group of a well-known problem of Motzkin, originally posed for sets of integers. We make a first treatment of this circle-group analogue, for finite sets $D$ of missing differences, using techniques from ergodic theory, graph theory and the geometry of numbers. Our results include an exact solution when $D$ has two elements, at least one of which is irrational. When every element of $D$ is rational, the problem is equivalent to estimating the independence ratio of a circulant graph. In the case of two rational elements, we give an estimate for this ratio in terms of the odd girth of the graph, which is asymptotically sharp and also recovers a classical solution of Cantor and Gordon to Motzkin's original problem for two missing differences. This is joint work with Carlos Catalá, Juanjo Rué and Oriol Serra.
Date: Wednesday, 05 May, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Nested cycles with no geometric crossings.
Speaker: Irene Gil (Warwick)
Abstract: In this talk, we answer the following question posed by Erdös in 1975: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders. This is joint work with Jaehoon Kim, Younjin Kim and Hong Liu.
Date: Wednesday, Apr 28, 2021
Time: 15.00h (Barcelona time)
Title: RandNET Seminar: Rui Castro
Speakers: Detecting a planted community in an inhomogeneous random graph
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 21 Apr, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Quotientopes
Speaker: Vincent Pilaud (LIX-Polytechnique and CNRS, Paris)
Abstract: This talk will survey combinatorial and geometric properties of lattice quotients of the weak order on permutations, whose prototype is the classical Tamari lattice on binary trees. We will see in particular that any weak order quotient can be realized by a convex polytope called quotientope, generalizing the associahedron. Based on joint work with Francisco Santos, Arnau Padrol and Julian Ritter.
Date: Wednesday, 14 Apr, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Bounding Obstructions sets: the cases of apices of minor closed classes
Speaker: Dimitrios M. Thilikos (LIRMM and CNRS, Montpellier)
Abstract: Given a minor-closed graph class {\cal G}, the (minor) obstruction of {\cal G} is the set of all minor-minimal graphs not in {\cal G}. Given a non-negative integer k, we define the k-apex of {\cal A} as the class containing every graph G with a set S of vertices whose removal from G gives a graph on {\cal G}. We prove that every obstruction of the k-apex of {\cal G} has size bounded by some 4-fold exponential function of p(k) where p is a polynomial function whose degree depends on the size of the minor-obstructions of {\cal G}. This bound drops to a 2-fold exponential one when {\cal G} excludes some apex graph as a minor (i.e., a graph in the $1$-apex of planar graphs). Joint work with Ignasi Sau and Giannos Stamoulis
Date: Wednesday, 07 Apr, 2021
Time: 12.45h (Barcelona time) (NOTE THE UNUSUAL TIME)
Video: here (UPC login required)
Title: On the complexity of finding large odd induced subgraphs and odd colorings
Speaker: Ignasi Sau (LIRMM and CNRS, Montpellier)
Abstract: This talk is about the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters $mos(G)$ and $\chi_{odd}(G)$, respectively. We will discuss (some of) the following results:
- Deciding whether $\chi_{odd}(G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise.
- FPT algorithms in time $2^{O(rw)}poly(n)$ and $2^{O(q \cdot rw)}poly(n)$ to compute $mos(G)$ and to decide whether $\chi_{odd}(G) \leq q$ on an $n$-vertex graph $G$ of rank-width at most $rw$, respectively. The dependency on rank-width is asymptotically optimal under the ETH.
- Some tight bounds for these parameters on restricted graph classes or in relation to other parameters.
Joint work with Rémy Belmonte, available at arXiv:2002.06078.
Date: Wednesday, Mar 24, 2021
Time: 15.00h (Barcelona time)
Title: 2-session RandNET Seminar: "Random planar graphs - results and conjectures" and "Maps of unfixed genus and blossoming trees"
Speakers: Benedikt Stuffler (TUWien, Vienna) and Eric Fusy (LIX-Polytechnique, Paris)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 10 Mar, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Algorithmic extensions of the Bollobás-Häggkvist conjecture
Speaker: Viresh Patel (UVA, Amsterdam)
Abstract: Dirac's Theorem is a classical result in graph theory stating that every n-vertex graph with minimum degree at least n/2 has a Hamilton cycle. If we restrict to regular graphs (and impose some mild connectivity conditions), we might hope to lower the degree threshold: in that direction, Bollobás and Häggkvist independently conjectured that every k-connected, D-regular, n-vertex graph with D≥n/(k+1) has a Hamilton cycle. Although the conjecture turns out to be false for k≥4, one might still wonder whether Hamiltonicity is easier to detect in regular (dense) graphs. We investigate this question. This is joint work with Fabian Stroh.
Video: here (UPC login required)
Date: Wednesday, Feb 24, 2021
Time: 15.00h (Barcelona time)
Title: 2-session RandNET Seminar: "Network archeology: a few results and many questions" and "The design of algorithms for the production of training data"
Speakers: Gábor Lugosi (UPF, Barcelona) and Élie de Panafieu (Nokia-Bell Labs)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, Jan 20, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: On the expected number of perfect matchings in cubic planar graphs
Speaker: Marc Noy
Abstract: A well-known conjecture by Lovász and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with n vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically c γ^n, where c>0 and γ~1.14196 is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations.
Joint work with Clément Requilé and Juanjo Rué.
Video: here
Date: Wednesday, Jan 13, 2021
Time: 12.15h (Barcelona time)
Where: Zoom
Title: A canonical polynomial Van der Waerden's theorem.
Speaker: António Girão
Abstract: In this talk, we will give a brief overview of some fundamental results in Arithmetic Ramsey theory. Starting with the now famous Van der Waerden’s theorem we intend to give a sketch of a new proof of the canonical version of Van der Waerden’s theorem, originally proved by Erdös and Graham, since it already contains important ideas which are used in our proof of the canonical version of the Polynomial Van der Waerden’s Theorem.
Finally, we hope to give a short sketch of a proof of the canonical version of the Polynomial Van der Waerden’s Theorem which was proved in the 90’s by Bergelson and Leibman. Our proof uses beautiful ideas of Walters in his purely combinatorial proof of Bergelson and Leibman’s result.
Video: here
Date: Wednesday, Dec 16, 2020
Time: 12.15h (Barcelona time)
Where: Zoom
Title: Graph polynomials and choosability of planar graphs
Speaker: Jarek Grytczuk (Warsaw University of Technology)
Abstract: A graph G is k-choosable if it is colorable from arbitrary lists of colors, each of size k, assigned to the vertices of G. A famous theorem of Thomassen asserts that every planar graph is 5-choosable, whereas Voigt found planar graphs that are not 4-choosable. Recently, Zhu reproved Thomassen's theorem by using graph polynomials and the celebrated Combinatorial Nullstellensatz. By using a similar approach we proved that every planar graph can be made 4-choosable by deleting a suitable matching. This strengthens some earlier results on defective choosability of planar graphs and perhaps kindles some hope for a computer-free proof of the Four Color Theorem. We will discuss some possible directions towards this extravagant goal.
This is joint work with Xuding Zhu.
Video: here
Date: Wednesday, Dec 09, 2020
Time: 12.15h (Barcelona time)
Where: Zoom
Title: On the minimum bisection of random 3−regular graphs
Speaker: Lyuben Lichev (ENS Lyon)
Slides: here
Video: here
Abstract: A minimum bisection of a graph with even number of vertices is a partition of the vertices of the graph in two equal parts, which induce a bipartite graph with minimal number of edges (that is, of minimal size). Finding the size of a minimum bisection is a classical (and in general difficult) problem in graph theory and computer science. In this talk, we will concentrate on the methods, used in the recent paper https://arxiv.org/abs/2009.00598 (joint work with Dieter Mitsche) to give better asymptotically almost sure lower and upper bounds on the minimum bisection of a 3-regular graph, chosen uniformly at random. In the proof of the lower bound, we will look for a rather precise information on the structure of the two parts of a minimum bisection. In the upper bound, we will partially reuse this information in combination with classical spectral ideas.
Date: Wednesday, Dec 02, 2020
Time: 12.15h (Barcelona time)
Slides: here
Video: here
Title: Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
Speaker: Miguel Àngel Fiol (UPC)
Abstract: The k-th power G^k of a graph G=(V,E) is the graph whose vertex set is V, and in which two distinct vertices are adjacent if and only if their distance in G is at most k. In this talk we present various eigenvalue bounds for the independence number and chromatic number of G^k, which purely depend on the spectrum of G, together with a method to optimize them. In particular, such bounds are shown to be tight for some of the so-called k-partially walk-regular, which can be seen as a generalization of distance-regular graphs. In this case, the bounds are obtained via a new family of polynomials obtained from the spectrum of a graph, called minor polynomials. Moreover these results coincide with the Delsarte's linear programming bound and, in fact, the given bounds also apply also for the Lovász theta number \theta, and the Shannon capacity of a graph \Theta. In general, our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. In some cases, our approach has the advantage of yielding closed formulas and, so, allowing asymptotic analysis. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well.
(Joint work with A. Abiad, G. Coutinho, B. D. Nogueira, and S. Zeijlemaker)
Date: Wednesday, Nov 11, 2020
Time: 12.15h (Barcelona time)
Slides: here
Video: Link to Video (UPC login required)
Title: Hamiltonicity of random subgraphs of the hypercube.
Speaker: Alberto Espuny-Díaz (Technische Universität Ilmenau)
Abstract: The study of Hamiltonicity has been one of the driving forces in the development of random graph theory. I will briefly survey some of the classical benchmark results in the $G_{n,p}$ model (thresholds and hitting time results) and then discuss the analogous problem for (binomial) random subgraphs of the hypercube. Here, we have very recently obtained threshold and hitting time results for Hamiltonicity, resolving and extending a long-standing conjecture. Our proofs rely on perturbation results for subgraphs of the hypercube, which I will also discuss. The main goal of the talk will be to explain some of the main ideas behind the proof, which involves branching processes, the Rödl nibble, and absorption.
Date: Wednesday, Oct 21, 2020
Time: 12.15h (Barcelona time)
Where: Zoom
Title: A compactification result for the set of positive sequences (with applications to graph limits).
Speaker: Lluís Vena (UPC, Barcelona)
Abstract: The graph limits aims to provide a better understanding of large graphs by giving a limit object which is linked to a convergence
notion for a sequence of graphs. One of the problems that arise is the following: even when the convergent notions care about similar parameters, the different convergence notions either only works for certain families of graphs, or they trivialize for others. The best known example of this behaviour is the left-convergence introduced by Lovasz et. al., and the Benjamini-Schramm convergence for bounded degree graphs: in both cases the convergence of the sequence involves the subgraph counts (we fix the subgraph to count, such as the triangle K_3, and let the parameter of the sequence grow). For the left-convergence, if the graphs G_n are not dense, then the limit trivializes; for the Benjamini-Schramm convergence, we can only consider sequences of graphs with bounded maximum degree.
We present the following 'compactification' result: assuming the continuum hypothesis, there exists a set of positive sequences A (with the property that the quotient of every pair of sequences in A has a limit (possibly infinite)), for which, for any subsequence b of positive numbers, there exist an a in A, a constant \infty>c>0, and a subsubsequence d (indexed by I) of b such that d_n/a_n \to_{n\to \infty, n\in I} c (the limit of d along the subsequence is comparable to a). With this, we give a convergence notion that is the common generalization of the Benjamini-Schramm convergence and the left-convergence for graphs, and has the property that any sequence of graphs (with growing number of vertices) has a convergence subsequence.
This is a joint work with David Chodounsky.
Video: here (UPC login required)
Date: Thursday, June 25, 2020
Time: 15h (Barcelona time)
Where: Zoom
Title: Faster k-SAT algorithms using biased-PPSZ
Speaker: Or Zamir, Tel Aviv University, Israel
Abstract: The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every k>3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k≥3. For k=3 we also improve on Hertli’s result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308^n to 1.307^n.
Joint work with Thomas Dueholm Hansen, Haim Kaplan and Uri Zwick.
Date: Wednesday June 17, 2020
Time: 11h (watch the time)
Where: Zoom
Speaker: Ross Kang (Radboud Univ, The Netherlands)
Title: New investigations into the structure of locally sparse graphs (Slides available here)
Abstract: The structure of triangle-free graphs has deeply influenced the development of combinatorial mathematics. Both fundamental results of Mantel (1907) and of Ramsey (1930) yield global structure from the local property of having no edges in any neighbourhood.
I recently began some basic explorations in this classic area. This has led to unexpected and novel questions and developments, especially with respect to structural aspects related to independent sets and colourings in graphs. To begin I will give an overview of the history including the focus of current/recent activities.
Then I will present a new general framework for structure in locally sparse graphs. This generalises and strengthens many notable results in the area, including those of Ajtai, Komlós, Szemerédi (1980/1), Shearer (1983/1996), Kim (1995), Johansson (1996), Alon (1996), Alon, Krivelevich, Sudakov (1999), Molloy (2019), Bernshteyn (2019), and Achlioptas, Iliopoulos, Sinclair (2019). The methodology underlying this framework asymptotically cannot be improved in general, by a consideration of random regular graphs. The framework is built around a technique inspired by statistical physics --namely, a local analysis of the hard-core model-- as well as the suitable application of the Lovász local lemma. It essentially reduces the main task to a routinely verified property of the hard-core model we call local occupancy.
This talk touches on joint work with, variously, Wouter Cames van Batenburg, Ewan Davies, Louis Esperet, Rémi de Joannis de Verclos, François Pirot, Jean-Sébastien Sereni, and Stéphan Thomassé.
Date: Wednesday June 10, 2020
Time: 15h (watch the time)
Where: Zoom link
Speaker: Marcelo Soares Campos (IMPA, Rio de Janeiro)
Title: On the number of sets with a given doubling constant
Abstract: We study the number of $k$-element subsets $A$ of a given abelian group $G$, such that $|A+A|\leq \lambda|A|$. Proving a conjecture of Alon, Balogh, Morris and Samotij, and improving a result of Green and Morris, who proved the conjecture for $\lambda$ fixed, we provide an upper bound on the number of such sets, when $\lambda=o(k/(\log n)^3)$, which is tight up to a factor of $2^{o(k)}$ in many cases. The main technical result we will prove, which has found other applications, is a "Container Theorem for sumsets" proved using the asymmetric container lemma, introduced by Morris, Samotij and Saxton.
Date: Wednesday February 26, 2020
Time: 12h
Where: Room C3-005, Campus Nord UPC
Speaker: Miquel Àngel Fiol (UPC Barcelona)
Title: On d-Fibonacci digraphs.
Abstract: The d-Fibonacci digraphs F(d,k), introduced in this work, have the number of vertices following generalized Fibonacci-like sequences. They can be defined both as digraphs on alphabets and as iterated line digraphs. Here we study some of their nice properties. For instance, F(2,k) has diameter d+k-2 and is semi-pancyclic, that is, it has a cycle of every length between 1 and \ell, with \ell\in\{2k-2,2k-1\}. Moreover, it turns out that several other numbers of F(d,k) (of closed l-walks, classes of vertices, etc.) also follow the same linear recurrences as the numbers of
vertices of the d-Fibonacci digraphs.
Joint work with C. Dalfó
Date: Wednesday January 22, 2020
Time: 12h
Where: Room C3-005, Campus Nord UPC
Speaker: Alberto Larrauri (UPC Barcelona)
Title: On the evolution of the set of limiting probabilities of first order properties for sparse random graphs.
Abstract: It is known that for any first order property of graphs P, the limit probability that the random graph G(n,c/n) satisfies P as n tends to infinity exists and varies in a smooth way with c. An immediate consequence of this is that first order properties cannot individually ``capture'' the phase transition that occurs in G(n,c/n) when c=1. For each c we consider the set of limiting probabilities L_c={lim Pr(G(n,c/n) satisfies P): P first order property} We ask the question of whether we can ``detect" the phase transition in G(n,c/n) through the changes in L_c. We arrive at a negative answer and show that there is a constant c_0\approx 0.93... such that the closure of L_c is the whole interval [0,1] when c>= c_0 and this closure is a finite union of disjoint intervals when c< c_0. Moreover, the number of intervals forming the closure tends to infinity as c tends to zero. The same question can be asked in the setting of random uniform hypergraphs and similar results are obtained.
This is joint work with Marc Noy and Tobias Muller.
Date: Wednesday December 18, 2019
Time: 12h
Where: Room C3-005, Campus Nord UPC
Speaker: Lluís Alemany (UPC Barcelona)
Title: Edge crossings in random linear arrangements
Abstract: In spatial networks, vertices are arranged in some space and edges may cross. Here study two statistical properties of edge crossings in general spaces, with a special focus on one-dimensional layouts, where edges may cross when drawn above the vertex sequence as it happens in linguistic and biological networks.
Here we investigate the distribution of edge crossings under the null hypothesis of a uniformly random arrangement of the vertices. We generalize the existing formula for the expectation of this number in trees to any network and derive a general expression for the variance of the number of crossings relying on a novel characterization of the algebraic structure of that variance in an arbitrary space. We provide compact formulae for the expectation and the variance in complete graphs, cycle graphs, one-regular graphs and various kinds of trees (star trees, quasi-star trees and linear trees). In these networks, the scaling of expectation and variance as a function of network size is asymptotically power-law-like.
I will also outline some applications and future research directions beyond the current arxiv version of this work (https://arxiv.org/abs/1910.03926).
____________________________
Date: Wednesday December 11, 2019
Time: 12h
Where: Room C3-005, Campus Nord UPC
Speaker: Juanjo Rué (UPC Barcelona)
Title: An Erdös–Fuchs Theorem for Ordered Representation Functions
Abstract: This is a joint work with Gonzalo Cao-Labora and Christoph Spiegel (UPC).
____________________________
Date: Wednesday November 13, 2019
Time: 12h
Where: Room C3-005, Campus Nord UPC
Speaker: Pablo Oviedo (UPC Barcelona)
Title: Universal intervals in the homomorphism order of directed graphs
Abstract: We show a density theorem for the class of finite proper trees ordered by the homomorphism order. We strengthen this result by showing
that every interval of proper trees (not homomorphic to paths)is in fact universal, that is, it contains every countable partial order as a suborder. We also show that every interval of the class of cyclic digraphs ordered by the homomorphism order is universal. We end bydiscussing the consequences of these results on the class of all finite digraphs.
This is joint work with Jan Hubicka and Jaroslav Nesetril.
____________________________
Date: Wednesday November 6, 2019
Time: 12h
Where: Room C3-005, Campus Nord UPC
Speaker: Jaroslav Nesetril (Institute of Theoretical Computer Science, Charles University, Prague)
Title: Sparse representations of algebras
Abstract: Representations of groups, monoids and categories by isomorphisms and homomorphisms of graphs in a surprisingly close relatinship to sparse hierarchy of classes of graphs.
A joint work with P. Ossona de Mendez (Paris,Prague).
____________________________
Title: Minimal nets in metric spaces and minimal complements in groups
Date: Thursday October 3, 2019
Time: 12h
Where: Room C3-005, Campus Nord UPC
Speaker: Miquel Angel Fiol (Department of Mathematics, UPC Barcelona)
Title: A new class of polynomials from the spectrum of a graph, and its application to bound the k-independence number
Abstract: The k-independence number of a graph is the maximum size of a set of vertices at pairwise distance greater than $k$. A graph is called walk-regular, if the number of closed walks of a given length l, rooted at a vertex v, only depends on l. In particular, a distance-regular graph is also walk-regular (but the converse does not hold). In this work, we introduce a new family of polynomials obtained from the spectrum of a graph. These polynomials, together with the interlacing technique, allow us to give tight spectral bounds on the $k$-independence number of a walk-regular graph.
Date: Wednesday September 25, 2019
Time: 12h
Where: Room C3-005, Campus Nord UPC
Speaker: Maryam Sharifzadeh (Mathematics Institute, Warwick)
Title: Asymptotic Structure for the Clique Density Theorem
Abstract: The famous Erdös-Rademacher problem asks for the smallest number of r-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all r was determined only recently, by Reiher. In this talk, we describe the asymptotic structure of all almost extremal graphs. This task for r=3 was previously accomplished by Pikhurko and Razborov. This is joint work with Jaehoon Kim, Hong Liu, and Oleg Pikhurko.
Date: Wednesday September 18, 2019
Time: 12h
Where: Room C3-005, Campus Nord UPC
Speaker: Marc Vinyals (Tata Institute of Fundamental Research, Mumbai)
Title: Equality Alone Does not Simulate Randomness
Abstract: Randomness can provide an exponential saving in the amount of communication needed to solve a distributed problem, and the canonical example of this is equality. However, in all examples where randomness helps having access to an equality oracle would be enough to solve the problem efficiently. Is equality all there is to randomness?
In this talk we show that equality is not enough. More precisely, we exhibit a function that can be solved efficiently using randomized protocols but not with only access to an equality oracle.
Joint work with Arkadev Chattopadhyay and Shachar Lovett.
Abstract: For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f(tw) n^{O(1)}, where tw is the treewidth of G. We determine the asymptotically optimal function f(tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw)=2^{Θ(tw)} if H is a contraction of the chair or the banner, and f(tw)=2^{Θ(tw log tw)} otherwise.
The proof combines several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Joint work with Julien Baste and Ignasi Sau
____________________________
This seminar is partially supported by ERC Consolidator Research Grant ERC-2014-CoG 648276 AUTAR 
____________________________
Share: