2023-24 LIMDA Seminar
Date: Friday, 19 July 2024
Time: 11:00h (Barcelona time)
Where: Room A3-106(40) Campus Nord UPC and Meet link
Title: Explicit constructions of minimal codes and strong blocking sets
Speaker: Shagnik Das (National Taiwan University)
Abstract:
A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. In this talk we present a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the (k−1)-dimensional projective space over F_q that have size O(qk). Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of F_q-linear minimal codes of length n and dimension k, for every prime power q, for which n=O(qk). This is joint work with Noga Alon, Anurag Bishnoi and Alessandro Neri.
Date: Thursday, 27 June, 2024
Time: 15.00h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Categorification of Flag Algebras
Speaker: Aldo Kiem (Zuse Institute Berlin)
Abstract:
Flag Algebras are an essential tool in modern extremal combinatorics. In this talk, we will explore some new connections between this subject and category theory. This category theoretic framework subsumes previously considered extensions of Flag Algebras to hypercubes and finite vector spaces. In particular, we show that the Flag Algebra vector space is a colimit built out of a very naturally defined presheaf. Beyond this, we will consider a more in-depth study of maps between the algebras, leading to higher-order differential methods. No prior knowledge of category theory will be assumed.
Date: Thursday, 20 June, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: Subtractive random forests with two choices
Speaker: Francisco Calvillo (LPSM - Sorbonne Université)
Abstract:
We present a model for a multi-choice recommendation system, enabling users to select from two independent suggestions based on past interactions. The one-choice scenario was previously introduced by Broutin, Devroye, Lugosi and I. Oliveira, leading to the study of a family of random forests which they called Subtractive Random Forests (SURF). By superposing two independent copies of this random forest, we are able to evaluate the effectiveness and robustness of the two-choice system across diverse scenarios.
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.
Date: Thursday, 23 May, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: A canonical van der Waerden theorem in random sets
Speaker: Miquel Ortega (UPC)
Abstract:
The canonical van der Waerden theorem states that, for large enough $n$, any colouring of $[n]$ gives rise to monochromatic or rainbow $k$-APs. In this work, we are interested in sparse random versions of this result. More concretely, we determine the threshold at which the binomial random set $[n]_p$ inherits the canonical van der Waerden properties of $[n]$.
Date: Thursday, 16 May, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: A hypergraph bandwidth theorem
Speaker: Richard Lang (Hamburg)
Abstract:
A classic result of Dirac states a graph has a Hamilton path provided that every vertex is adjacent to at least half of the other vertices. The Bandwidth Theorem asserts that under mildly stronger assumptions one can even embed all bipartite graphs with sublinear bandwidth and constant maximum degree. Analogous statements are known to hold for embedding graphs with higher chromatic number.
In this talk, I present a new proof of this result with an alternative quantification and then discuss its generalisation to hypergraphs.
Date: Thursday, 2 May, 2024
Time: 16.15h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Meet link
Title: On additive codes over finite fields
Speaker: Tabriz Popatia (UPC)
Abstract:
In this talk we prove a Griesmer type bound for additive codes over finite fields. This new bound gives an upper bound on the length of fractional maximum distance separable (MDS) codes, codes which attain the Singleton bound. We prove that this bound can be obtained in some cases and give example of specific codes reaching the bound. These code surpass the length of the longest known codes in the non-fractional or linear case. We also explore the dual of an additive code, and give a necessary condition on when the dual of an additive MDS code will also be an MDS code.
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, 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.
Share: