Home

Resume

Research

Attachement Trees (2024)

This is a full-time research project financed by the ISM grant (I received an offer for the NSERC grant, but I had to decline it for administrative reasons) and supervised by Prof. Louigi Addario-Berry from McGill University.

The main goal of this research is to study the efficiency of algorithms that find the root of uniform attachment trees with high probability.

A uniform attachment tree is a tree (acyclic graph) that was constructed as follows :
0) Choose any natural number n.
1) Start with a single vertex v0 called the root.
2) Attach a new vertex v1 to v0 with an edge.
3) Randomly choose a vertex in {v0, v1} uniformly and attach a new vertex v2 to it with an edge.
4) Randomly choose a vertex in {v0, v1, v2} uniformly and attach a new vertex v3 to it with an edge.
5) Repeat this process until there are n vertices in your tree. The graph you obtain is the uniform attachment tree.

A root finding algorithm is an algorithm that takes a uniform attachment tree T = ( V , E ) and a positive real number ε>0 as an input. It then outputs a subset W of V of size independent of T such that the probability that the root of T is in W is at least 1 - ε.

Note here that it may seem surprising that the size of W does not depend on T. You are not alone if you felt that way, it is a very nice result!

For such an algorithm to be considered efficient, we want the size of W to be as small as possible as a function of ε. The way we characterize the efficiency of algorithms is by comparing the asymptotic behaviours of the size of W as ε approaches 0 for different algorithms.

The main topic I worked on during this project is trying to upper bound and lower bound the optimal asymptotic behaviour that any root finding algorithm can reach.

This project is still in progress and the final report (maybe a paper??) has not been written yet. I will update this page as soon as it is available!


The Burning Number (2023)

This is a full-time research project financed by the NSERC grant and supervised by Prof. Sergey Norin from McGill University.

The main goal of this research is to improve the advancements that have been made regarding the Burning Number conjecture.

Given any finite connected graph G = ( V , E ), we can define a metric space ( V , d ) where d(u,v) is equal to the length of the shortest path between u and v.

For a vertex v and a natural number r, a ball of radius r around v is defined as Br(v) = {u ∈ V : d(u,v) ≤ r}, i.e. all the vertices that are at distance from v less than or equal to r.

The burning number of a graph G = ( V , E ), denoted B(G), is the minimal natural number k such that there exist v0,v1,...,vk-1∈V with V=B0(v0)⋃B1(v1)⋃...⋃Bk-1(vk-1).
Clearly such a number k must exist since we can enumerate V as V={v0,...,v|V|-1} to get that V=B0(v0)⋃...⋃B|V|-1(v|V|-1).

The Burning Number conjecture states that for any graph G = ( V , E ), B(G) ≤ √|V|.

This conjecture has not been proven nor disproven yet. Our goal during this research was to contribute to the advancement of the knowledge that we have regarding this conjecture.

Here is the final report I wrote at the end of the summer : Link here.


Subelliptic Operators (2022)

This is a full-time research project financed by the NSERC grant and supervised by Prof. Sergey Norin from McGill University.

The main goal of this research is to find eigenfunctions of the Grushin Operator : ∂2/∂x2 + x22/∂x2.

The final report that I wrote for this project can be found : Here.