Paweł Prałat

activity

20122026

collaborators

10 papers

math.CO2026

Triangle-Saturated Graphs in the Semi-Random Graph Process

Felix Christian Clemen, Pawel Pralat

The semi-random graph process is an adaptive random graph process in which an online algorithm is initially given an empty graph on $n$ vertices. In each round, a vertex $u$ is pre…

math.PR2026

The stochastic block model has the overlap graph property for modularity

Shankar Bhamidi, David Gamarnik, Remco van der Hofstad +4

The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to…

math.PR2026

The critical activation density in graph bootstrap percolation

Brett Kolesnik, Tamás Makai, Rajko Nenadov +3

In graph bootstrap percolation, edges of an Erdős-Rényi random graph $G_{n, p}$ are initially active, and activation spreads to other edges of $K_{n}$ via the combinatorics…

math.CO2026

Canonical labelling of random regular graphs

Mikhail Isaev, Tamás Makai, Brendan McKay +3

We prove that whenever $d = d (n) \to \infty$ and $n - d \to \infty$ as $n \to \infty$ , then with high probability for any non-trivial initial colouring, the colour refinement algorithm disti…

math.PR2025

Direct Paths in the Temporal Hypercube

Austin Eide, Martijn Gösgens, Paweł Prałat

We consider the $n$ -dimensional random temporal hypercube, i.e., the $n$ -dimensional hypercube graph with its edges endowed with i.i.d. continuous random weights. We say that a ver…

math.CO2025

Multiset Metric Dimension of Binomial Random Graphs

Austin Eide, Pawel Pralat

For a graph $G = (V, E)$ and a subset $R \subseteq V$ , we say that $R$ is \textit{multiset resolving} for $G$ if for every pair of vertices $v, w$ , the \textit{multisets} $\{d(v,r):…

cs.SI2025

Multilayer Artificial Benchmark for Community Detection (mABCD)

Łukasz Kraiński, Michał Czuba, Piotr Bródka +3

One of the most persistent challenges in network science is the development of various synthetic graph models to support subsequent analyses. Among the most notable frameworks addr…

math.CO2025

Playing Sudoku on random 3-regular graphs

Jack Dippel, Austin Eide, Pawel Pralat +1

The Sudoku number $s (G)$ of graph $G$ with chromatic number $χ (G)$ is the smallest partial $χ (G)$ -colouring of $G$ that determines a unique $χ (G)$ -colouring of the entire graph. We…

math.CO2024

Burning Random Trees

Luc Devroye, Austin Eide, Pawel Pralat

Let $T$ be a Galton-Watson tree with a given offspring distribution $ξ$ , where $ξ$ is a $Z_{\geq 0}$ -valued random variable with $E [ξ] = 1$ and $0 < σ^{2}:=Var[ξ] < \inft…

math.CO2012

Sparse graphs are not flammable

Paweł Prałat

In this paper, we consider the following \emph{ $k$ -many firefighter problem} on a finite graph $G = (V, E)$ . Suppose that a fire breaks out at a given vertex $v \in V$ . In each subseq…