P. Prałat

activity

20062024

most citedClustering via Hypergraph Modularity

83 citations · 346 across the 78 of their papers we have counts for

collaborators

Showing math.COShow all

72 papers · 1 filter

math.CO2024

Hopping Forcing Number in Random $d$ -regular Graphs

Pawel Pralat, Harjas Singh

Hopping forcing is a single player combinatorial game in which the player is presented a graph on $n$ vertices, some of which are initially blue with the remaining vertices being w…

math.CO2024★ 2 cited

Creating Subgraphs in Semi-Random Hypergraph Games

Natalie Behague, Pawel Pralat, Andrzej Rucinski

The semi-random hypergraph process is a natural generalisation of the semi-random graph process, which can be thought of as a one player game. For fixed $r < s$ , starting with an e…

math.CO2024

Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model

Michael Molloy, Pawel Pralat, Gregory B. Sorkin

We study the 2-offer semirandom 3-uniform hypergraph model on $n$ vertices. At each step, we are presented with 2 uniformly random vertices. We choose any other vertex, thus creati…

math.CO2023

Linear Colouring of Binomial Random Graphs

Austin Eide, Paweł Prałat

We investigate the linear chromatic number $χ_{lin} (G (n, p))$ of the binomial random graph $G (n, p)$ on $n$ vertices in which each edge appears independently with probability…

math.CO2023★ 2 cited

Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than $2 n$ Rounds

Alan Frieze, Pu Gao, Calum MacRury +2

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

math.CO2023

Cliques, Chromatic Number, and Independent Sets in the Semi-random Process

David Gamarnik, Mihyun Kang, Pawel Pralat

The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the pla…

math.CO2023

Power of $k$ Choices in the Semi-Random Graph Process

Paweł Prałat, Harjas Singh

The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the pla…

math.CO2022★ 1 cited

Almost all 9-regular graphs have a modulo-5 orientation

Michelle Delcourt, Reaz Huq, Pawel Pralat

In 1972 Tutte famously conjectured that every 4-edge-connected graph has a nowhere zero 3-flow; this is known to be equivalent to every 5-regular, 4-edge-connected graph having an…

math.CO2022

Rainbow spanning trees in randomly coloured $G_{k - o u t}$

Deepak Bal, Alan Frieze, Pawel Pralat

Given a graph $G = (V, E)$ on $n$ vertices and an assignment of colours to its edges, a set of edges $S \subseteq E$ is said to be rainbow if edges from $S$ have pairwise different co…

math.CO2022

The Erdős-Gyárfás function $f (n, 4, 5) = \frac{5}{6} n + o (n)$ -- so Gyárfás was right

Patrick Bennett, Ryan Cushman, Andrzej Dudek +1

A $(4, 5)$ -coloring of $K_{n}$ is an edge-coloring of $K_{n}$ where every $4$ -clique spans at least five colors. We show that there exist $(4, 5)$ -colorings of $K_{n}$ using $\frac 56 n…

math.CO2022

A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process

Pu Gao, Calum MacRury, Pawel Pralat

The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the pla…

math.CO2022

Edge and Pair Queries -- Random Graphs and Complexity

Dariusz Dereniowski, Przemysław Gordinowicz, Paweł Prałat

We investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random gr…

math.CO2021★ 2 cited

Perfect Matchings in the Semi-random Graph Process

Pu Gao, Calum MacRury, Pawel Pralat

The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the pla…

math.CO2021★ 1 cited

Subgraph Games in the Semi-Random Graph Process and Its Generalization to Hypergraphs

Natalie C. Behague, Trent G. Marbach, Pawel Pralat +1

The semi-random graph process is a single-player game that begins with an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and unif…

math.CO2021

Localization Game for Random Geometric Graphs

Lyuben Lichev, Dieter Mitsche, Pawel Pralat

The localization game is a two player combinatorial game played on a graph $G = (V, E)$ . The cops choose a set of vertices $S_{1} \subseteq V$ with $∣ S_{1} ∣ = k$ . The robber then chooses a…

math.CO2020

Tight Bounds on the Probabilistic Zero Forcing on Hypercubes and Grids

Natalie C. Behague, Trent Marbach, Pawel Pralat

Zero forcing is a deterministic iterative graph colouring process in which vertices are coloured either blue or white, and in every round, any blue vertices that have a single whit…

math.CO2020

Broadcasting on Paths and Cycles

Reaz Huq, Pawel Pralat

Consider the following broadcasting process run on a connected graph $G = (V, E)$ . Suppose that $k \geq 2$ agents start on vertices selected from $V$ uniformly and independently at ran…

math.CO2020

The Unit Acquisition Number of Binomial Random Graphs

Konstantinos Georgiou, Somnath Kundu, Pawel Pralat

Let $G$ be a graph in which each vertex initially has weight 1. In each step, the unit weight from a vertex $u$ to a neighbouring vertex $v$ can be moved, provided that the weight…

math.CO2020★ 3 cited

Hamilton Cycles in the Semi-random Graph Process

Pu Gao, Bogumil Kaminski, Calum MacRury +1

The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the pla…

math.CO2020

On the existence of Hamilton cycles with a periodic pattern in a random digraph

Alan Frieze, Xavier Perez-Gimenez, Pawel Pralat

We consider Hamilton cycles in the random digraph $D_{n, m}$ where the orientation of edges follows a pattern other than the trivial orientation in which the edges are oriented in t…

math.CO2019

Localization Game for Random Graphs

Andrzej Dudek, Sean English, Alan Frieze +2

We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding grap…

math.CO2019

Probabilistic Zero Forcing on Random Graphs

Sean English, Calum MacRury, Pawel Pralat

Zero forcing is a deterministic iterative graph coloring process in which vertices are colored either blue or white, and in every round, any blue vertices that have a single white…

math.CO2018★ 1 cited

Zero Forcing Number of Random Regular Graphs

Deepak Bal, Patrick Bennett, Sean English +2

The zero forcing process is an iterative graph colouring process in which at each time step a coloured vertex with a single uncoloured neighbour can force this neighbour to become…

math.CO2018★ 83 cited

Clustering via Hypergraph Modularity

Bogumil Kaminski, Valerie Poulin, Pawel Pralat +2

Despite the fact that many important problems (including clustering) can be described using hypergraphs, theoretical foundations as well as practical algorithms using hypergraphs a…

Hopping Forcing Number in Random d-regular Graphs

Creating Subgraphs in Semi-Random Hypergraph Games

Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model

Linear Colouring of Binomial Random Graphs

Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than 2n Rounds

Cliques, Chromatic Number, and Independent Sets in the Semi-random Process

Power of k Choices in the Semi-Random Graph Process

Almost all 9-regular graphs have a modulo-5 orientation

Rainbow spanning trees in randomly coloured Gk−out​

The Erdős-Gyárfás function f(n,4,5)=65​n+o(n) -- so Gyárfás was right

A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process

Edge and Pair Queries -- Random Graphs and Complexity

Perfect Matchings in the Semi-random Graph Process

Subgraph Games in the Semi-Random Graph Process and Its Generalization to Hypergraphs

Localization Game for Random Geometric Graphs

Tight Bounds on the Probabilistic Zero Forcing on Hypercubes and Grids

Broadcasting on Paths and Cycles

The Unit Acquisition Number of Binomial Random Graphs

Hamilton Cycles in the Semi-random Graph Process

On the existence of Hamilton cycles with a periodic pattern in a random digraph

Localization Game for Random Graphs

Probabilistic Zero Forcing on Random Graphs

Zero Forcing Number of Random Regular Graphs

Clustering via Hypergraph Modularity

Hopping Forcing Number in Random $d$ -regular Graphs

Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than $2 n$ Rounds

Power of $k$ Choices in the Semi-Random Graph Process

Rainbow spanning trees in randomly coloured $G_{k - o u t}$

The Erdős-Gyárfás function $f (n, 4, 5) = \frac{5}{6} n + o (n)$ -- so Gyárfás was right