Oscar Defrain

During my PhD, I most importantly studied the dualization of monotone Boolean functions, and its generalizations, through the different shapes it takes on graphs, hypergraphs, and lattices: minimal dominating sets enumeration, minimal transversals enumeration, maximal independent sets enumeration, lattice dualization, meet-irreducible enumeration.
The manuscript can be found here, and a handout of the slides here.

Aside from enumeration, I am more generally interested in combinatorics and algorithms: structural graph theory, graph decompositions, FPT, etc.
While in master, I also briefly worked on infinite time computation models.

International journals

• Avoidable paths in graphs
  M. Bonamy, O. Defrain, M. Hatzel, and J. Thiebaut
  Electron. J. Comb. 27(4): P4.46 (2020) [arXiv].
  


• Translating between the representations of a ranked convex geometry
  O. Defrain, L. Nourine, and S. Vilmin
  To appear in Discrete Mathematics [arXiv].
  


• Revisiting a theorem by Folkman on graph colouring
  M. Bonamy, P. Charbit, O. Defrain, G. Joret, A. Lagoutte, V. Limouzy, L. Pastor, and J-S. Sereni
  Electr. J. Comb. 27(1): P1.56 (2020) [arXiv].
  


• Dualization in lattices given by implicational bases
  O. Defrain and L. Nourine
  Theor. Comput. Sci. 814: 169-176 (2020) [arXiv].
  


• On the dualization in distributive lattices and related problems
  O. Defrain, L. Nourine, and T. Uno
  To appear in Discrete Applied Mathematics [arXiv].
  


• Enumerating minimal dominating sets in $K_t$-free graphs and variants
  M. Bonamy, O. Defrain, M. Heinrich, M. Pilipczuk, and J-F. Raymond
  ACM Trans. Algorithms 16(3): 39:1-39:23 (2020) [arXiv].
  

International conference proceedings

• Dualization in lattices given by implicational bases
  O. Defrain and L. Nourine
  In ICFCA 2019 (LNCS 11511, pages 89–98) [arXiv].
  


• Enumerating minimal dominating sets in triangle-free graphs
  M. Bonamy, O. Defrain, M. Heinrich, and J-F. Raymond
  In STACS 2019 (LIPIcs 126, pages 16:1–16:12) [arXiv].
  


• Neighborhood inclusions for minimal dominating sets enumeration:
  Linear and polynomial delay algorithms in $P_7$-free and $P_8$-free chordal graphs
  O. Defrain and L. Nourine
  In ISAAC 2019 (LIPIcs 149, pages 63:1–63:16) [arXiv].
  


• Infinite time busy beavers
  O. Defrain, B. Durand, and G. Lafitte
  In CiE 2017 (LNCS 10307, pages 221–233).
  

Forthcoming works

• On objects dual to tree-cut decompositions
  Ł. Bożyk, O. Defrain, K. Okrasa, M. Pilipczuk
  Submitted [arXiv].
  


• Enumerating minimal dominating sets in the (in)comparability graphs
  of bounded dimension posets
  M. Bonamy, O. Defrain, P. Micek, and L. Nourine
  Submitted [arXiv].
  

Talks

• On the dualization problem in graphs, hypergraphs, and lattices
  ACRO Seminar, March 15, online.
  


• Enumerating minimal dominating sets in the incomparability graphs of bounded dimension posets
  WEPA 2020, December 7–10, online. JGA 2020, November 16–18, online [pdf].
  


• Avoidable paths in graphs
  JGA 2019, November 13–15, Brussels [pdf].
  


• Translating between the representations of a lattice
  RIMS Seminar, Feb 04, 2020, Kyoto [pdf].
  Séminaire des doctorants, June 06, 2019, Clermont-Ferrand.
  


• Dualization in lattices given by implicational bases
  WEPA 2019, October 28–31, Awaji Island [pdf].
  Japanese Week at LIMOS, September 23–27, 2019, Clermont-Ferrand.
  ICFCA 2019, June 25–28, Frankfurt.
  


• Enumerating minimal dominating sets in $K_t$-free graphs and variants
  RIMS Seminar, Feb 04, 2020, Kyoto [pdf].
  STACS 2019, March 13–16, Berlin.
  


• Ideal enumeration toward distributive lattice dualization
  JGA 2018, November 14–16, Grenoble.
  WEPA 2018, November 05–08, Pisa.
  Dagstuhl Seminar 18421, October 14–19, 2018.
  


• Dualization in distributive lattices
  AlCoLoCo Seminar, October 02, 2018, Clermont-Ferrand.
  


• Neighborhood inclusions for minimal dominating sets enumeration
  ISAAC 2019, December 8–11, Shanghai [pdf].
  Séminaire des doctorants, April 27, 2018, Clermont-Ferrand.
  

Groups

• ERC CUTACOMBS Grant
• ANR GraphEn
• AlCoLoCo