Preprints

  • F. Galliot, S. Gravier and I. Sivignon,"Maker-Breaker is solved in polynomial time on hypergraphs of rank 3", 2022. Submitted. [PDF]
    We introduce structural tools for the study of the Maker-Breaker game, based on intersections of subhypergraph collections. Applying them in the case of hypergraphs of rank 3, we get a structural characterization for the winner of the game and for both players' optimal moves, from which we derive a polynomial-time algorithm. This validates a conjecture by Rahman and Watson (2020).
  • F. Galliot, S. Gravier and I. Sivignon,"(k−2)-linear connected components in hypergraphs of rank k", 2021. Submitted. [PDF]
    Introducing q-linear paths in hypergraphs, we detail the structure of the connected components associated to (k-2)-linear paths in hypergraphs of rank k, and we show that they can be computed in polynomial time. In the case k=3, this coincides with the well-known notion of linear path, and the obtained algorithm is key to prove our result on the Maker-Breaker game (see above). We also explore links with the "PAFP" problem in graphs.
  • F. Galliot, S. Gravier and I. Sivignon,"An update on the coin-moving game on the square grid", 2021. Accepted. [PDF]
    We pursue the study of some coin-moving puzzles which was started by Demaine et. al. (2002). We study the case of the square grid, for which we go back on an inaccuracy in the original article and we bring some new contributions. We present a new algorithm to solve some puzzles and we exhibit a family of worst-case unsolvable puzzles, moreover we initiate the study of puzzles with a single "bonus coin".

Master's theses

  • F. Galliot, "A coin-moving game on graphs", 2019. Master's thesis in operations research, optimization and combinatorics at Université Grenoble Alpes, under the supervision of Sylvain Gravier and Isabelle Sivignon. [PDF]
  • F. Galliot, "Mélange d'un jeu de cartes : le riffle shuffle" (in French), 2018. Master's thesis in probability theory at Sorbonne Université, under the supervision of Justin Salez. [PDF]

Miscellaneous

  • A note sent to Persi Diaconis in 2018, detailing the resolution of his conjecture about the guessing game (with feedback) on a deck of cards shuffled by one or several riffle shuffles, as well as some further comments.
  • My M1 TER (in French, 2016) in measure theory at Sorbonne Université, under the supervision of Jean-François Babadjian.