Julien Portier

activity

20212026

most citedThe odd chromatic number of a planar graph is at most 8

22 citations · 36 across the 26 of their papers we have counts for

collaborators

28 papers

math.CO2026

Cliques in minimally globally rigid graphs

Julien Portier

We show that every minimally generically globally rigid graph in $R^{d}$ which contains a subgraph isomorphic to $K_{d + 2}$ is itself isomorphic to $K_{d + 2}$ , confirming a con…

math.CO2026

Reconstructing a giant component of a point set in $R$

Julien Portier

Let $V \subset R$ be a finite set with $∣ V ∣ = n$ and suppose we are given each pairwise distance independently with probability $p$ . We show that if $p = (1 + ε) / n$ , for so…

math.CO2025

Tight bounds for expected propagation time of probabilistic zero forcing

Mehdi Jelassi, Julien Portier, Rik Sarkar

We study the probabilistic zero forcing process, a probabilistic variant of the classical zero forcing process. We show that for every connected graph $G$ on $n$ vertices, there ex…

math.CO2025

Nearly tight bounds for MaxCut in hypergraphs

Oliver Janzer, Julien Portier

An $r$ -cut of a $k$ -uniform hypergraph is a partition of its vertex set into $r$ parts, and the size of the cut is the number of edges which have at least one vertex in each part.…

math.CO2025

Approximate Itai-Zehavi conjecture for random graphs

Lawrence Hollom, Lyuben Lichev, Adva Mond +2

A famous conjecture by Itai and Zehavi states that, for every $d$ -vertex-connected graph $G$ and every vertex $r$ in $G$ , there are $d$ spanning trees of $G$ such that, for every v…

math.CO2025

Monotonicity and decompositions of random regular graphs

Lawrence Hollom, Lyuben Lichev, Adva Mond +2

In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameter…

math.CO2025

Double-jump phase transition for the reverse Littlewood--Offord problem

Lawrence Hollom, Julien Portier, Victor Souza

Erdős conjectured in 1945 that for any unit vectors $v_{1}, \dots, v_{n}$ in $R^{2}$ and signs $ε_{1}, \dots, ε_{n}$ taken independently and uniformly in $\{-1…

math.CO2024

A note on high-dimensional discrepancy of subtrees

Lawrence Hollom, Lyuben Lichev, Adva Mond +1

For a tree $T$ and a function $f : E (T) \to S^{d}$ , the imbalance of a subtree $T^{'} \subseteq T$ is given by $∣ \sum_{e \in E (T^{'})} f (e) ∣$ . The $d$ -dimensional discrepancy o…

math.CO2024

Exponential odd-distance sets under the Manhattan metric

Alberto Espuny Díaz, Emma Hogan, Freddie Illingworth +3

We construct a set of $2^{n}$ points in $R^{n}$ such that all pairwise Manhattan distances are odd integers, which improves the recent linear lower bound of Golovanov, Kupavsk…

math.CO2024

Discrepancies of spanning trees in dense graphs

Lawrence Hollom, Lyuben Lichev, Adva Mond +1

We address several related problems on combinatorial discrepancy of trees in a setting introduced by Erdős, Füredi, Loebl and Sós. Given a fixed tree $T$ on $n$ vertices and an edg…

math.CO2024

Almost colour-balanced spanning forests in complete graphs

Lawrence Hollom, Adva Mond, Julien Portier

Given $K_{n}$ whose edges are coloured red and blue, and a forest $F$ of order $n$ , we seek embeddings of $F$ with small imbalance, that is, difference between the numbers of red and…

math.CO2024

Packing and finding paths in sparse random graphs

Vesna Iršič, Julien Portier, Leo Versteegen

Let $G \sim G (n, p)$ be a (hidden) Erdős-Rényi random graph with $p = (1 + ε) / n$ for some fixed constant $ε > 0$ . Ferber, Krivelevich, Sudakov, and Vieira showed tha…

math.CO2024

The asymptotic of off-diagonal online Ramsey numbers for paths

Adva Mond, Julien Portier

We prove that for every $k \geq 10$ , the online Ramsey number for paths $P_{k}$ and $P_{n}$ satisfies $r ~ (P_{k}, P_{n}) \geq \frac{5}{3} n + \frac{k}{9} - 4$ , matching up to a linear te…

math.CO2024

Global rigidity of random graphs in $R$

Richard Montgomery, Rajko Nenadov, Julien Portier +1

We investigate the problem of reconstructing a set $P \subseteq R$ of distinct points, where the only information available about $P$ consists of the distances between some…

math.CO2024

Reconstructing almost all of a point set in $R^{d}$ from randomly revealed pairwise distances

Douglas Barnes, Jan Petr, Julien Portier +2

Let $V$ be a set of $n$ points in $R^{d}$ , and suppose that the distance between each pair of points is revealed independently with probability $p$ . We study when this infor…

math.CO2023

Tight lower bounds for anti-concentration of Rademacher sums and Tomaszewski's counterpart problem

Lawrence Hollom, Julien Portier

In this paper we prove that $P (∣ X ∣ \geq Var (X)) \geq 7/32$ for every finite Rademacher sum $X$ , confirming a conjecture by Hitczenko and Kwapie{ń} from 1994,…

cs.CC2023

The complexity of decomposing a graph into a matching and a bounded linear forest

Agnijo Banerjee, João Pedro Marciano, Adva Mond +2

Deciding whether a graph can be edge-decomposed into a matching and a $k$ -bounded linear forest was recently shown by Campbell, H{ö}rsch and Moore to be NP-complete for every $k \g…

math.CO2023

Bounds for the Competition-Independence game on trees

Jan Petr, Julien Portier

In this paper we prove that Sweller has a strategy so that the Sweller-Start Competition-Independence game lasts at least $(5 n + 3) /13$ moves for every tree. Moreover, we show that t…

math.CO2023★ 1 cited

On interval colourings of graphs

Lawrence Hollom, Julien Portier, Leo Versteegen

An interval colouring of a graph $G = (V, E)$ is a proper colouring $c : E \to Z$ such that the set of colours of edges incident to any given vertex forms an interval of $…

math.CO2023

A note on interval colourings of graphs

Maria Axenovich, António Girão, Lawrence Hollom +5

A graph is said to be interval colourable if it admits a proper edge-colouring using palette $N$ in which the set of colours incident to each vertex is an interval. The in…

math.CO2023

Progress towards the 1/2-Conjecture for the domination game

Julien Portier, Leo Versteegen

The domination game is played on a graph $G$ by two players, Dominator and Staller, who alternate in selecting vertices until each vertex in the graph $G$ is contained in the close…

math.CO2022★ 4 cited

A proof of the 3/4 conjecture for the total domination game

Julien Portier, Leo Versteegen

In this paper we describe a strategy for Dominator that finishes the total domination game in at most $3/4 n$ moves for every graph $G$ on $n$ vertices without any isolated vertices…

math.CO2022

On the number of minimum dominating sets and total dominating sets in forests

Jan Petr, Julien Portier, Leo Versteegen

We show that the maximum number of minimum dominating sets of a forest with domination number $γ$ is at most $5^{γ}$ and construct for each $γ$ a tree with domination number $…

math.CO2022★ 1 cited

A note on Cops and Robbers, independence number, domination number and diameter

Jan Petr, Julien Portier, Leo Versteegen

We study relations between diameter $D (G)$ , domination number $γ (G)$ , independence number $α (G)$ and cop number $c (G)$ of a connected graph $G$ , showing (i.) $c(G) \leq α(G)-\lfloo…

Cliques in minimally globally rigid graphs

Reconstructing a giant component of a point set in R

Tight bounds for expected propagation time of probabilistic zero forcing

Nearly tight bounds for MaxCut in hypergraphs

Approximate Itai-Zehavi conjecture for random graphs

Monotonicity and decompositions of random regular graphs

Double-jump phase transition for the reverse Littlewood--Offord problem

A note on high-dimensional discrepancy of subtrees

Exponential odd-distance sets under the Manhattan metric

Discrepancies of spanning trees in dense graphs

Almost colour-balanced spanning forests in complete graphs

Packing and finding paths in sparse random graphs

The asymptotic of off-diagonal online Ramsey numbers for paths

Global rigidity of random graphs in R

Reconstructing almost all of a point set in Rd from randomly revealed pairwise distances

Tight lower bounds for anti-concentration of Rademacher sums and Tomaszewski's counterpart problem

The complexity of decomposing a graph into a matching and a bounded linear forest

Bounds for the Competition-Independence game on trees

On interval colourings of graphs

A note on interval colourings of graphs

Progress towards the 1/2-Conjecture for the domination game

A proof of the 3/4 conjecture for the total domination game

On the number of minimum dominating sets and total dominating sets in forests

A note on Cops and Robbers, independence number, domination number and diameter

Reconstructing a giant component of a point set in $R$

Global rigidity of random graphs in $R$

Reconstructing almost all of a point set in $R^{d}$ from randomly revealed pairwise distances