Dr. Imed Zaguia

Dr. Imed Zaguia
Associate Head
Girouard Building, room 302
(613) 541-6000 ext. 6078
(613) 541-6584
Department of Mathematics and Computer Science

College Address

Royal Military College of Canada
PO Box 17000, Station Forces
Kingston, Ontario, CANADA
K7K 7B4

Research Interests:

  • Ordered sets
  • Linear extensions
  • Graphs
  • Combinatorics
  • Well-quasi-ordering
  • Hereditary Classes
  • Theory of Relations

Short biography

I am an associate Professor of Mathematics and Computer Science. I taught most of the undergraduate courses in Mathematics and several core courses in Computer Science.

My research interests broadly lie in the study of combinatorial and relational structures. One of my research interests is concerned with the study of permutation classes, a very active field of research motivated by the Stanly–Wilf Conjecture, solved in 2004 by Marcus and Tardos. Permutations appear in the study of bichains, permutation graphs and more generally in the study of relational structures. Problems studied in this area include the study of hereditary classes of permutations and their growth functions.

I am also working on a central conjecture related to linear extensions of partially ordered sets: The 1/3-2/3 Conjecture (1968, unsolved). The conjecture states that, if one is comparison sorting a set of objects then, no matter what comparisons may have already been performed, it is always possible to choose the next comparison in such a way that it will reduce the number of possible sorted orders by a factor of 2/3 or better. This problem was listed as a featured unsolved problem in the founding volume of the journal Order, a journal on the Theory of Ordered Sets and its Applications.

Currently, I am especially investigating the question of well-quasi-ordering in combinatorial objects and the corresponding construction of infinite antichains.

Selected Publications:

  • M. Pouzet and I. Zaguia, Metric properties of incomparability graphs with an emphasis on paths. Contrib. Discrete Math. 17 (2022), no. 1, 109–141.
  • M. Pouzet and I. Zaguia, Graphs containing finite induced paths of unbounded length. Discrete Math. Theor. Comput. Sci. 23 ([2021–2022]), no. 2, Paper No. 3, 28 pp.
  • Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, Permutations Avoiding Certain Partially-ordered Patterns. Electron. J. Combin. 28 (2021), no. 3, Paper No. 3.18, 41 pp.
  • I. Zaguia, Greedy balanced pairs in N -free ordered sets . Discrete Applied Mathematics 289 , (2021), 539–544.
  • I. Zaguia, The 1 / 3 − 2 / 3 Conjecture for Ordered Sets whose Cover Graph is a Forest . Order 36 , (2019), 335–347.
  • M. Pouzet and I. Zaguia, Interval orders, semiorders and ordered groups . J. Math. Psych. 89 (2019), 51–66
  • D. Rorabaugh, C. Tardif, D. Wehlau and I. Zaguia, Chromatic numbers of iterated arc graphs . Comment.Math.Univ.Carolin. 59 ,3 (2018) 277–283.
  • C. Delhomme and I. Zaguia, Countable linear orders with disjoint infinite intervals are mutually orthogonal . Discrete Mathematics. 341 , (2018), 1885–1899.
  • T. Bier and I. Zaguia, Some inequalities for orderings of acyclic digraphs . Contrib. Discrete Math. 13 (2018), Pages 150–160.
  • N. Sauer and I. Zaguia, Permutations avoiding connected subgraphs . Contrib. Discrete Math. 12 (2017), Pages 215–230.
  • C. Laflamme, M. Pouzet, N. Sauer and I. Zaguia Pairs of orthogonal countable ordinals . Discrete Mathematics 28 (2014), 35–44.
  • I. Zaguia, The 1 / 3−2 / 3 Conjecture for N -free ordered sets. Electronic Journal of Combinatorics. 19 (2012), #P29

A complete list of his publications can be found on Google Scholar

Date modified: