This is a project ran by a subset of my research lab during my Master's degree under Prof. Adrian Vetta.
The main goal of this research is to find the dimension of the popular matching problem.
We are given a graph \(G = (V,E)\) where each agent \(v \in V\) has a weight \(w(v) \ge 0\) and preferences \(\preceq_v\) over its neighbors \(\Gamma(v)\). It is assumed that an agent strictly prefers being matched with anybody than being unmatched.
A set \(M \subseteq E\) is called a matching if no two edges of \(M\) are adjacent to a common vertex. Given two matchings \(M,M'\), we write \(M \succ_v M'\) if \(v\) preferes its neighbor in \(M\) over its neighbor in \(M'\) or if \(v\) is matched in \(M\) but not in \(M'\). We then denote \(\phi(M,M') = \sum_{v : M \succ_v M'} w(v)\).
A matching \(M\) is called popular if \(\phi(M,M') \ge \phi(M',M)\) for any matching \(M'\). Unfortunately, such a popular matching does not always exist. Consider for example a complete graph with vertices \(\{0,1,2\}\) where agent \(i\)'s top choice is \(i+1 \pmod 3\) and \(w(i) = 1\). If \(M\) was a popular matching, we may assume it is non-empty and contains an edge from \(0\) to \(1\) by symmetry, and that is the only edge \(M\) can contain. Then, the matching \(M'\) containing an edge from \(1\) to \(2\) violates the condition for being a popular matching.
For this reason, we generalize the notion of popular matchings. Given a set of matchings \(\mathcal{M} = \{M_1,\ldots,M_k\}\) and a matching \(M\), we write \(\mathcal{M} \succ_v M\) if agent \(v\) prefers its best match in \(\mathcal{M}\) over its match in \(M\). Then, we call \(\mathcal{M}\) a popular winning set if \(\phi(\mathcal{M},M') \ge \phi(M',\mathcal{M})\) for any matching \(M'\).
The popular dimension of an instance of this problem is the minimum interger \(k\) such that a popular winning set \(\mathcal{M} = \{M_1,\ldots,M_k\}\) exists. Given some sets of instances of this problem, we are trying to find the maximum possible popular dimension among those sets.
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 \(v_0\) called the root.
2) Attach a new vertex \(v_1\) to \(v_0\) with an edge.
3) Randomly choose a vertex in {\(v_1\), \(v_0\)} uniformly and attach a new vertex \(v_2\) to it with an edge.
4) Randomly choose a vertex in {\(v_2\), \(v_1\), \(v_0\)} uniformly and attach a new vertex \(v_2\) 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 \(\varepsilon > 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 - \varepsilon\).
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 \(\varepsilon > 0\). The way we characterize the efficiency of algorithms is by comparing the asymptotic behaviours of the size of \(W\) as \(\varepsilon \to 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 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 \(B_r(v) = \{u \in V : d(u,v) \le 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 \(v_0,v_1,\ldots,v_{k-1} \in V\) with \(V = \bigcup_{i=0}^{k-1} B_i(v_i)\).
Clearly such a number \(k\) must exist since we can enumerate \(V\) as \(V = \{v_0,\ldots,v_{|V|-1}\}\) to get that \(V = \bigcup_{i=0}^{|V|-1} B_i(v_i)\).
The Burning Number conjecture states that for any graph \(G = ( V , E )\), \(B(G) \le \sqrt{|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.
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 : \(\frac{\partial^2}{\partial x^2} + x^2\frac{\partial^2}{\partial y^2}\).
The final report that I wrote for this project can be found : Here.