Passer au contenu

/ Research

Je donne

Rechercher

Natural Sciences and Engineering; Applied Sciences

Gena Hahn

Graphes : existence, propriétés, applications

Professeur titulaire

Faculté des arts et des sciences - Département d'informatique et de recherche opérationnelle

André-Aisenstadt, room 3351

514 343-6806

gena.hahn@umontreal.ca

Secondary number: 514 343-5834 (Télécopieur)

Media

Gena Hahn (University of Montreal) / Cops, robbers, infinite graphs and related problems

Profile

Research expertise

My main interest is graph theory and related areas, such as combinatorics, algorithms and complexity, communication in interconnection networks. I like theoretical and structural results that lead to better understanding. I do and will think about many different problems.

education

  • 1986 — Doctorat d'état — InformatiqueUniversité de Paris-Sud
  • 1981 — Ph.D. — Mathématiques fondamentalesUniversité McMaster

Affiliations and responsabilities

University service and activities

Activities within organizations or entities of the institution

  • Membre du Laboratoire d'informatique théorique et quantique

Teaching and supervision

Student supervision

Theses and dissertation supervision (Papyrus Institutional Repository)

2025

Sur la cardinalité des graphes ayant un groupe d'automorphismes donné

Graduate : Clavette, Francis
Cycle : Master's
Grade : M. Sc.
2023

Trois résultats en théorie des graphes

Graduate : Ramamonjisoa, Frank
Cycle : Doctoral
Grade : Ph. D.
2022

Une étude des graphes jumeaux via l'auto-abritement

Graduate : Gagnon, Alizée
Cycle : Master's
Grade : M. Sc.
2021

Le jeu de policiers-voleur sur différentes classes de graphes

Graduate : Turcotte, Jérémie
Cycle : Master's
Grade : M. Sc.
2019

Domination éternelle dans les graphes

Graduate : Virgile, Virgélot
Cycle : Master's
Grade : M. Sc.
2015

Droites sur les hypergraphes

Graduate : Bayani, Aryan
Cycle : Master's
Grade : M. Sc.
2012

Complexité des homomorphismes de graphes avec listes

Graduate : Lemaître, Adrien
Cycle : Doctoral
Grade : Ph. D.
2007

Jeu de poursuite sur graphe non réflexif

Graduate : El Ouarari, Amal
Cycle : Master's
Grade : M. Sc.
2007

Reconnaissance des graphes policier-gagnants

Graduate : Thériault, Benoit
Cycle : Master's
Grade : M. Sc.
2006

Études du jeu de poursuite dans les graphes

Graduate : Zine, Youssef
Cycle : Master's
Grade : M. Sc.
2006

Graphe et jeu de poursuite : policiers et voleurs sous contraintes

Graduate : El Harti, Sif El Islam
Cycle : Master's
Grade : M. Sc.
2006

Contribution à la conjecture d'Erdos-Farber-Lovász

Graduate : Akrout, Khaled
Cycle : Master's
Grade : M. Sc.
2005

Jeu de poursuite sur des modèles du web et généralisation

Graduate : Ramanampanoharana, Tantely
Cycle : Master's
Grade : M. Sc.
2004

A survey of graph and subgraph isomorphism problems

Graduate : Lei, Yaohui
Cycle : Master's
Grade : M. Sc.
2003

Problèmes de routages dans les réseaux optiques

Graduate : Houndété, Alfred
Cycle : Master's
Grade : M. Sc.
2001

Le filtrage du protocole SMB

Graduate : Eid, Antoine
Cycle : Master's
Grade : M. Sc.
2000

La Charrue - pour une représentation des données dans l'interface homme-machine

Graduate : Gauthier, Jean-François
Cycle : Master's
Grade : M. Sc.
2000

Symétrie et sens de l'orientation dans les graphes

Graduate : Awwad, Mohamad
Cycle : Master's
Grade : M. Sc.
1993

Codage d'image par automates à états finis, du tétrarbre à l'automate

Graduate : Quenneville, Charles
Cycle : Master's
Grade : M. Sc.
1993

Homomorphisms and the star chromatic number of a graph

Graduate : Gao, Guo-Gang
Cycle : Doctoral
Grade : Ph. D.
1990

Le problème des reines : thème et variations

Graduate : Gauthier, Michel
Cycle : Master's
Grade : M. Sc.

Projects

Research projects

2022 - 2029

Centre de recherches mathématiques (CRM)

Lead researcher : Octavian Cornea
Co-researchers : Yoshua Bengio , François Lalonde , Gilles Brassard , Michel Delfour , Marlène Frigon , Véronique Hussin , Christiane Rousseau , Jacques Bélair , Paul M Gauthier , Sabin Lessard , Alain Vinet , Nadia El-Mabrouk , Gena Hahn , Christian Léger , Fahima Nekka , Iosif Polterovich , Yvan Saint Aubin , Andrew Granville , Sylvie Hamel , Manuel Morales , François Perron , Mylène Bédard , Pierre Duchesne , Matilde Lalin , Robert Gwyn Owens , Manu Paranjape , Dana Schlomiuk , Luc Vinet , Mireille Schnitzer , Karim Jerbi , Alexander Fribergh , Alejandro Murua , Maciej Augustyniak , Benoît Mâsse , Dimitrios Koukoulopoulos , Jun Li , Benjamin Seamone , William Witczak-Krempa , Egor Shelukhin , Morgan Craig , Guillaume Lajoie , Margarida Carvalho , Guy Wolf , Florian Maire , Frédéric Dupont-Dupuis , Michael C. Mackey , Frédéric Lesage , Russell Steele , Erica Moodie , Paul François , Henri Darmon , Maxime Descoteaux , Prakash Panangaden , André Dieter Bandrauk , Peter Bartello , Chantal David , Jean-Marc Lina , Anthony Raymond Humphries , John P. Harnad , Jacques Claude Hurtubise , Pengfei Guan , John A Toth , Niky Kamran , Adrian Iovita , Eyal Goren , Dmitry Jakobson , Vojkan Jaksic , Daniel Tzvi Wise , André Garon , Éric P. Marchand , Debbie Janice Dupuis , Yogendra Chaubey , Pawel Gora , Hershy Kisilevsky , Galia Dafni , D. Korotkin , Marco Bertola , Alina Stancu , Lea Popovic , Ibrahim Assem , Tomasz Kaczynski , Shiping Liu , Vasilisa Shramchenko , Bruno L. Rémillard , Richard Fournier , Alfred Michel Grundland , David Stephens , Xiaowen Chang , Frederic Guichard , Erik P. Cook , Robert Brandenberger , Adrian Vetta , Keshav Dasgupta , Christophe Grova , Gantumur Tsogtgerel , Johanna Neslehova , Jean-Christophe Nave , Anmar Khadra , Adam M. Oberman , Michael Yves Michel Pichot , Alexander Maloney , Dana Louigi Addario-Berry , José Garrido , Alexei Kokotov , Wei Sun , Patrice Gaillardetz , Linan Chen , Piotr Przytycki , Vladimir Makarenkov , Louis-Paul Rivest , François Bergeron , Steven P. Boyer , Line Baribeau , Frédéric Gourdeau , Claude Levesque , Thomas Joseph Ransford , Jean-Marie De Koninck , Javad Mashreghi , Thierry Duchesne , Srecko Brlek , Christophe Reutenauer , Vestislav Apostolov , Steven Lu , Geneviève Lefebvre , Hélène Cossette , Étienne Marceau , José Manuel Urquiza , Hugo Chapdelaine , Michael Lau , Alexandre Girouard , Antonio Lei , Jean-François Renaud , Christophe Hohlweg , Mathieu Boudreault , FRANCO SALIOLA , Alexandre Roch , Frédéric Rochon , Alexandre Blondin-Massé , Clement Hyvrier , Denis Talbot , Alexandre Bureau , Fabrice Larribe , Aurélie Labbe , Cody Hyndman , Khader Khadraoui , Hamed Hatami , Roger Villemaire , Frédéric Godin , Marcin Sabok , Yi Yang , Anne Mackay , Jérôme Vétois , Ting-Huei Chen , Habib Benali , Taoufik Bouezmani , Christian Genest , Xiaowen Zhou , Sorana Froda , Mélina Mailhot , Alexandra Schmidt , Simon Philippe Caron-Huot , Abdoulaye Banire Diallo , Jean-Philippe Lessard , Sarah Harrison , Anne-Sophie Charest , Masoud Asgharian-Dastenael , Rustum Choksi , Abbas Khalili Mahmoudabadi , Simon Gravel , Arusharka Sen , Arthur Charpentier , Mathieu Pigeon , Benoit Larose , Thomas Brüstle , Laurent Charlin , Janosch Ortmann , Tim Hoheisel , Jean Deteix , Jessica Lin , Michael Lipnowski , Giovanni Rosso , Thomas Hugh , Jean-Philippe Burelle , Julien Keller , Félix Camirand Lemyre , Marie-Pier Côté , Damir Kinzebulatov , Duncan McCoy , Klaus Herrmann , Felix Kwok , Courtney Paquette , Anush Tserunyan , Suresh Krishna , Valentino Tosatti , Patrick Brodie Allen , Behrooz Yousefzadeh , Marc-Hubert Nicole , Rober Platt
Funding sources: FRQNT/Fonds de recherche du Québec - Nature et technologies (FQRNT)
Grant programs: PVXXXXXX-(RS) Programme de regroupements stratégiques
2017 - 2027

Graph searching structural properties

Lead researcher : Gena Hahn
Funding sources: CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Grant programs: PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe
2020 - 2021

Supplément COVID-19 CRSNG_Graph searching structural properties

Lead researcher : Gena Hahn
Funding sources: CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Grant programs: PVXXXXXX-Supplément à l’appui des étudiants, des stagiaires postdoctoraux et du personnel de soutien à la recherche COVID-19
2012 - 2018

GRAPH SEARCHING AND APPLICATIONS

Lead researcher : Gena Hahn
Funding sources: CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Grant programs: PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe
2008 - 2016

CENTRE DE RECHERCHES MATHEMATIQUES (CRM)

Lead researcher : Luc Vinet
Co-researchers : Yoshua Bengio , François Lalonde , Gilles Brassard , Michel Delfour , Marlène Frigon , Véronique Hussin , Christiane Rousseau , Pavel Winternitz , Jacques Bélair , Anne Bourlioux , Paul M Gauthier , Sabin Lessard , Jean-François Angers , Abraham Broer , Nadia El-Mabrouk , Gena Hahn , Christian Léger , Fahima Nekka , Jiri Patera , Iosif Polterovich , Yvan Saint Aubin , Andrew Granville , Sylvie Hamel , Manuel Morales , François Perron , Octavian Cornea , Pierre Duchesne , Robert Gwyn Owens , Manu Paranjape , Jonathan Taylor , Michael C. Mackey , Frédéric Lesage , Erica Moodie , Henri Darmon , Maxime Descoteaux , André Dieter Bandrauk , Peter Bartello , Chantal David , Jean-Marc Lina , Johannes Walcher , Anthony Raymond Humphries , John P. Harnad , Jacques Claude Hurtubise , Pengfei Guan , David Avis , James Owen Ramsay , John A Toth , Sherwin A Maslowe , David B Wolfson , Karl Peter Russell , Olga Kharlampovich , Niky Kamran , Adrian Iovita , Eyal Goren , Dmitry Jakobson , Alain C. Vandal , Vojkan Jaksic , Daniel Tzvi Wise , Alexei Miasnikov , Thomas Wihler , Robert Seiringer , André Garon , John Mullins , Éric P. Marchand , Debbie Janice Dupuis , Syed Ali , Yogendra Chaubey , Christopher Cummins , Pawel Gora , Hershy Kisilevsky , John McKay , Galia Dafni , D. Korotkin , Benoit Larose , Marco Bertola , Vasek Chvatal , Alexander Shnirelman , Alina Stancu , Lea Popovic , Ibrahim Assem , Tomasz Kaczynski , Shiping Liu , Virginie Charette , Vasilisa Shramchenko , Bruno L. Rémillard , David Sankoff , Thomas Brüstle , Habib Benali , Nantel Bergeron , Simon Chauve , Francis Clarke , Richard Fournier , Martin Jakob Gander , Nadia Ghazzali , Alfred Michel Grundland , André Fortin , Louis-Paul Rivest , Christian Genest , François Bergeron , Steven P. Boyer , Line Baribeau , Frédéric Gourdeau , Robert Guénette , Claude Levesque , Pierre Mathieu , Thomas Joseph Ransford , Jean-Marie De Koninck , Javad Mashreghi , Thierry Duchesne , Srecko Brlek , André Joyal , Brenda MacGibbon , Christophe Reutenauer , Vestislav Apostolov , Olivier Collin , Steven Lu , Elisa Shahbazia Ohannessian , Yinannis Petridis
Funding sources: FRQNT/Fonds de recherche du Québec - Nature et technologies (FQRNT)
Grant programs: PVXXXXXX-(RS) Programme de regroupements stratégiques

Outreach

Publications and presentations

Publications

B. Bagheri, G. Hahn, A note on the circuit double cover of infinite graphs, Journal of Combinatorics, accepted 2016

A. Bonato, G. Hahn, C. Tardif, « Large classes of infinite k-cop-win graphs », Journal of Graph Theory 65 (2010), 334 - 342

G. Hahn, G. MacGillivray, « A characterisation of k-cop-win graphs and digraphs »,  Discrete Mathematics 306 (2006), 2492 - 2497

G. Hahn, F. Laviolette, N. Sauer, R.E. Woodrow, «On cop-win graphs», Discrete Mathematics 258 (2002), pp. 27 - 41

G. Hahn, J. Siran, D. Sotteau, «On the injective chromatic number of graphs », Discrete Mathematics 256 (2002), pp. 179 - 192

G. Hahn, C. Tardif, «Graph homomorphisms: structure and symmetry», in Graph symmetry, ASI ser C, Kluwer, 1997, pp. 107 -- 166

G. Hahn, P. Hell, S. Poljak, «On the ultimate independence ratio», European Journal of Combinatorics 16 (1995), pp. 253 - 261

G. Hahn, E. Milner, R.E. Woodrow, «Infinite Friendship Graphs with Infinite Parameters», Journal of Combinatorial Theory (B) 52 (1991) pp. 30 - 41

M. Farber, G. Hahn, P. Hell, D. Miller, «Concerning the achromatic number of graphs», Journal of Combinatorial Theory (B) 40 (1986) pp. 21 - 39

Disciplines

  • Computer Science
  • Applied Mathematics
  • Pure Mathematics

Areas of expertise

  • Graph algorithms
  • Graph coloring
  • Cayley graph
  • Infinite graphs
  • Graph homomorphism
  • Pursuit-evasion
  • Discreet Mathematics
  • Graphs Symmetry
  • Graph theory