Source author record

Théo Pierron

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Formal Languages and Automata Theory math.AC

Catalog footprint

Research overview

9works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Extremal Independent Set Reconfiguration

The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the intermediate sets remain independent. Extremal problems on independent sets are widely studied: for example, it is well known that an $n$ -vertex graph has at most $3^{n/3}$ maximum independent sets (and this is tight). This paper investigates the asymptotic behavior of maximum possible length of a shortest reconfiguration sequence for independent sets of size $k$ among all $n$ -vertex graphs. We give a tight bound for $k=2$ . We also provide a subquadratic upper bound (using the hypergraph removal lemma) as well as an almost tight construction for $k=3$ . We generalize our results for larger values of $k$ by proving an $n^{2\lfloor k/3 \rfloor}$ lower bound.

preprint2022arXiv

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity

We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from edge-coloured graph $G$ to edge-coloured graph $H$ is a vertex-mapping from $G$ to $H$ that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph $H$ . The question we are interested in is: given an edge-coloured graph $G$ , can we perform $k$ graph operations so that the resulting graph admits a homomorphism to $H$ ? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are 2-edge-coloured graphs whose colours are the signs $+$ and $-$ . We denote the corresponding problems (parameterized by $k$ ) by VD- $H$ -COLOURING, ED- $H$ -COLOURING and SW- $H$ -COLOURING. These problems generalise $H$ -COLOURING (to decide if an input graph admits a homomorphism to a fixed target $H$ ). Our main focus is when $H$ is an edge-coloured graph with at most two vertices, a case that is already interesting as it includes problems such as VERTEX COVER, ODD CYCLE RANSVERSAL and EDGE BIPARTIZATION. For such a graph $H$ , we give a P/NP-c complexity dichotomy for VD- $H$ -COLOURING, ED- $H$ -COLOURING and SW- $H$ -COLOURING. We then address their parameterized complexity. We show that VD- $H$ -COLOURING and ED- $H$ -COLOURING for all such $H$ are FPT. In contrast, already for some $H$ of order 3, unless P=NP, none of the three problems is in XP, since 3-COLOURING is NP-c. We show that SW- $H$ -COLOURING is different: there are three 2-edge-coloured graphs $H$ of order 2 for which SW- $H$ -COLOURING is W-hard, and assuming the ETH, admits no algorithm in time $f(k)n^{o(k)}$ . For the other cases, SW- $H$ -COLOURING is FPT.

preprint2022arXiv

Improved pyrotechnics : Closer to the burning graph conjecture

The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n} \rceil.$ While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its \emph{growth}, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph $G$ of order $n,$ given by $b(G) \le \sqrt{4n/3} + 1,$ improving on the previously known $\sqrt{3n/2}+O(1)$ bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least $3$ and holds for all large enough graphs with minimum degree at least $4$ . The previous best-known result was for graphs with minimum degree $23$ .

preprint2022arXiv

Square coloring planar graphs with automatic discharging

The discharging method is a powerful proof technique, especially for graph coloring problems. Its major downside is that it often requires lengthy case analyses, which are sometimes given to a computer for verification. However, it is much less common to use a computer to actively look for a discharging proof. In this paper, we use a Linear Programming approach to automatically look for a discharging proof. While our system is not entirely autonomous, we manage to make some progress towards Wegner's conjecture for distance- $2$ coloring of planar graphs, by showing that $12$ colors are sufficient to color at distance $2$ every planar graph with maximum degree $4$ .

preprint2022arXiv

Strengthening a theorem of Meyniel

For an integer $k \geq 1$ and a graph $G$ , let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$ -colorings of $G$ , and an edge between two vertices $α$ and~ $β$ whenever the coloring~ $β$ can be obtained from $α$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$ . We significantly strengthen this result, by showing that there is a positive constant $c$ such that $\mathcal{K}_5(G)$ has diameter $O(|V(G)|^c)$ for every planar graph $G$ .

preprint2022arXiv

What can be certified compactly?

Local certification consists in assigning labels (called \emph{certificates}) to the nodes of a network to certify a property of the network or the correctness of a data structure distributed on the network. The verification of this certification must be local: a node typically sees only its neighbors in the network. The main measure of performance of a certification is the size of its certificates. In 2011, Göös and Suomela identified $Θ(\log n)$ as a special certificate size: below this threshold little is possible, and several key properties do have certifications of this type. A certification with such small certificates is now called a \emph{compact local certification}, and it has become the gold standard of the area, similarly to polynomial time for centralized computing. A major question is then to understand which properties have $O(\log n)$ certificates, or in other words: what is the power of compact local certification? Recently, a series of papers have proved that several well-known network properties have compact local certifications: planarity, bounded-genus, etc. But one would like to have more general results, \emph{i.e.} meta-theorems. In the analogue setting of polynomial-time centralized algorithms, a very fruitful approach has been to prove that restricted types of problems can be solved in polynomial time in graphs with restricted structures. These problems are typically those that can be expressed in some logic, and the graph structures are whose with bounded width or depth parameters. We take a similar approach and prove the first meta-theorems for local certification. (See the abstract of the pdf for more details.)

preprint2020arXiv

Hadwiger meets Cayley

We show that every connected $k$ -chromatic graph contains at least $k^{k-2}$ spanning trees.

preprint2015arXiv

Quantifier Alternation for Infinite Words

We investigate the expressive power of quantifier alternation hierarchy of first-order logic over words. This hierarchy includes the classes $Σ_i$ (sentences having at most $i$ blocks of quantifiers starting with an $\exists$ ) and $\mathcal{B}Σ_i$ (Boolean combinations of $Σ_i$ sentences). So far, this expressive power has been effectively characterized for the lower levels only. Recently, a breakthrough was made over finite words, and decidable characterizations were obtained for $\mathcal{B}Σ_2$ and $Σ_3$ , by relying on a decision problem called separation, and solving it for $Σ_2$ . The contribution of this paper is a generalization of these results to the setting of infinite words: we solve separation for $Σ_2$ and $Σ_3$ , and obtain decidable characterizations of $\mathcal{B}Σ_2$ and $Σ_3$ as consequences.

preprint2015arXiv

Rings of invariants for the three dimensional modular representations of elementary abelian $p$ -groups of rank four

We show that the rings of invariants for the three dimensional modular representations of an elementary abelian $p$ -group of rank four are complete intersections with embedding dimension at most five. Our results confirm the conjectures of Campbell, Shank and Wehlau.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Théo Pierron

Research overview

Is this your work?

9 publications

Extremal Independent Set Reconfiguration

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity

Improved pyrotechnics : Closer to the burning graph conjecture

Square coloring planar graphs with automatic discharging

Strengthening a theorem of Meyniel

What can be certified compactly?

Hadwiger meets Cayley

Quantifier Alternation for Infinite Words

Rings of invariants for the three dimensional modular representations of elementary abelian $p$ -groups of rank four

See the researcher in context

Building this map preview

Théo Pierron

Research overview

Is this your work?

9 publications

Extremal Independent Set Reconfiguration

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity

Improved pyrotechnics : Closer to the burning graph conjecture

Square coloring planar graphs with automatic discharging

Strengthening a theorem of Meyniel

What can be certified compactly?

Hadwiger meets Cayley

Quantifier Alternation for Infinite Words

Rings of invariants for the three dimensional modular representations of elementary abelian ppp-groups of rank four

See the researcher in context

Building this map preview

Rings of invariants for the three dimensional modular representations of elementary abelian $p$ -groups of rank four