Peleg Michaeli

activity

20152026

most citedColour-biased Hamilton cycles in random graphs

7 citations · 14 across the 15 of their papers we have counts for

collaborators

20 papers

math.CO2026

Rigidity of complements of bounded-degree graphs

John Haslegrave, Peleg Michaeli, Anthony Nixon

Maxwell observed that the graph of any rigid generic framework in $R^{d}$ on $n$ vertices has at least $d n - (2 d + 1)$ edges. In this article we prove that graphs whose…

math.CO2026

Rigidity of expanders and pseudorandom graphs

Michael Krivelevich, Alan Lew, Peleg Michaeli

A graph $G = (V, E)$ is called $d$ -rigid if, for a generic embedding of its vertices in $R^{d}$ , the only continuous motions of the vertices preserving the distances between al…

math.CO2026

A very robust Ramsey theorem for matchings

Peter Keevash, Peleg Michaeli

Our main result is a robust generalisation of the Cockayne-Lorimer theorem on the multicolour Ramsey number of matchings. It is moreover a generalisation of the transference genera…

math.CO2026

Combinatorial sufficient conditions for graph rigidity and applications to random graphs

Michael Krivelevich, Alan Lew, Peleg Michaeli

A graph $G = (V, E)$ is called $d$ -rigid if, for a generic embedding of its vertices in $R^{d}$ , every edge-length preserving continuous motion of the vertices preserves the di…

math.CO2025

A generalised Ramsey--Turán problem for matchings

Peter Keevash, Peleg Michaeli

We prove a generalised Ramsey--Turán theorem for matchings, which (a) simultaneously generalises the Cockayne--Lorimer Theorem (Ramsey for matchings) and the Erdős--Gallai Theorem…

math.CO2025

Defect and transference versions of the Alon-Frankl-Lovasz theorem

Lior Gishboliner, Stefan Glock, Peleg Michaeli +1

Confirming a conjecture of Erdős on the chromatic number of Kneser hypergraphs, Alon, Frankl and Lovász proved that in any $q$ -colouring of the edges of the complete $r$ -uniform hy…

math.CO2024

Minimum degree conditions for graph rigidity

Michael Krivelevich, Alan Lew, Peleg Michaeli

We study minimum degree conditions that guarantee that an $n$ -vertex graph is rigid in $R^{d}$ . For small values of $d$ , we obtain a tight bound: for $d = O (n)$ , ever…

math.CO2023★ 1 cited

Rigid partitions: from high connectivity to random graphs

Michael Krivelevich, Alan Lew, Peleg Michaeli

A graph is called $d$ -rigid if there exists a generic embedding of its vertex set into $R^{d}$ such that every continuous motion of the vertices that preserves the lengths o…

math.CO2023

Discrepancies of subtrees

Tarun Krishna, Peleg Michaeli, Michail Sarantis +2

We study multicolour, oriented and high-dimensional discrepancies of the set of all subtrees of a tree. As our main result, we show that the $r$ -colour discrepancy of the subtrees…

math.CO2022

Karp's patching algorithm on random perturbations of dense digraphs

Alan Frieze, Peleg Michaeli

We consider the following question. We are given a dense digraph $D_{0}$ with minimum in- and out-degree at least $α n$ , where $α > 0$ is a constant. We then add random edges $R$ to $D_…

math.CO2022★ 1 cited

Fast construction on a restricted budget

Alan Frieze, Michael Krivelevich, Peleg Michaeli

We introduce a model of a controlled random graph process. In this model, the edges of the complete graph $K_{n}$ are ordered randomly and then revealed, one by one, to a player call…

math.CO2022

Oriented discrepancy of Hamilton cycles

Lior Gishboliner, Michael Krivelevich, Peleg Michaeli

We propose the following conjecture extending Dirac's theorem: if $G$ is a graph with $n \geq 3$ vertices and minimum degree $δ (G) \geq n /2$ , then in every orientation of $G$ there is…

math.CO2020

Discrepancies of Spanning Trees and Hamilton Cycles

Lior Gishboliner, Michael Krivelevich, Peleg Michaeli

We study the multicolour discrepancy of spanning trees and Hamilton cycles in graphs. As our main result, we show that under very mild conditions, the $r$ -colour spanning-tree disc…

math.CO2020

Spanning trees at the connectivity threshold

Yahav Alon, Michael Krivelevich, Peleg Michaeli

We present an explicit connected spanning structure that appears in a random graph just above the connectivity threshold with high probability.

math.CO2020★ 7 cited

Colour-biased Hamilton cycles in random graphs

Lior Gishboliner, Michael Krivelevich, Peleg Michaeli

We prove that a random graph $G (n, p)$ , with $p$ above the Hamiltonicity threshold, is typically such that for any $r$ -colouring of its edges there exists a Hamilton cycle with at l…

math.PR2019★ 4 cited

The diameter of uniform spanning trees in high dimensions

Peleg Michaeli, Asaf Nachmias, Matan Shalev

We show that the diameter of a uniformly drawn spanning tree of a connected graph on $n$ vertices which satisfies certain high-dimensionality conditions typically grows like $Θ(\sq…

math.CO2019

Thresholds in random motif graphs

Michael Anastos, Peleg Michaeli, Samantha Petti

We introduce a natural generalization of the Erdős-Rényi random graph model in which random instances of a fixed motif are added independently. The binomial random motif graph $G(H…

math.CO2019

Greedy maximal independent sets via local limits

Michael Krivelevich, Tamás Mészáros, Peleg Michaeli +1

The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the c…

math.CO2016

Small subgraphs in the trace of a random walk

Michael Krivelevich, Peleg Michaeli

We consider the combinatorial properties of the trace of a random walk on the complete graph and on the random graph $G (n, p)$ . In particular, we study the appearance of a fixed sub…

math.CO2015★ 1 cited

On the trace of random walks on random graphs

Alan Frieze, Michael Krivelevich, Peleg Michaeli +1

We study graph-theoretic properties of the trace of a random walk on a random graph. We show that for any $ε > 0$ there exists $C > 1$ such that the trace of the simple rando…