Ararat Harutyunyan me

Ararat Harutyunyan

Assistant Professor (Maitre de Conference)
LAMSADE ,
University of Paris-Dauphine.
Email: firstname.lastname (AT i.e. the spiral thing) dauphine.fr
Bureau: P626

 

 

 

 

 

 

Background

Curriculum Vitae.

2017 Sept. -:   Assistant Professor, LAMSADE (Computer Science Department), University of Paris-Dauphine.

2015 Sept. - 2017 Sept.:   Postdoctoral researcher, Mathematical Institute of Toulouse, University of Toulouse.

2014 Sept. - 2015 Sept.:   Postdoctoral Researcher, LIP (Computer Science Department), Ecole Normale Supérieure de Lyon.

2013 Sept. - 2014 Sept.:   Postdoctoral Researcher, Mathematical Institute, University of Oxford.

2012 Oct. - 2013 Sept.:   Postdoctoral researcher, LRI (Computer Science Department), University Paris-Sud 11.

2011 Sept. - 2012 June:   Postdoctoral researcher and instructor, Simon Fraser University.

2008 Sept. - 2011 June:   Ph.D. in Mathematics, Simon Fraser University.
Supervisor:   Bojan Mohar.
Thesis Title:   Brooks-type Theorems for Coloring of Digraphs.

2006 Sept. - 2008 Aug.:   MSc. in Mathematics, McGill University.
Supervisors:   Jacques Verstraete and Dmitry Jakobson.
Thesis Title:   Probabilistic Methods and Domination Related Problems in Graphs.

2003 Sept. - 2006 Aug.:   BSc Honours in Mathematics, McGill University.

 

Research Interests

My research interests are in graph theory. In particular, I am interested in structural graph theory, random graphs,
probabilistic methods and combinatorial and randomized graph algorithms. In recent years I have also
become interested and have done some work in other areas of computer science such as social networks and social choice.

Editorial

Associate Editor of Annals of Combinatorics.

Research Grants

I am the PI of the French ANR JC research grant DAGDigDec.

Publications

  1. A. Harutyunyan, C. McDiarmid, G.P.Surroca, Acyclic sets and Coloring of digraphs under restrictions on degrees and cycle lengths, submitted .
  2. A. Harutyunyan, G.P.Surroca, Colouring complete multipartite and Kneser-type digraphs , submitted .
  3. A. Harutyunyan, H. Harutyunyan, A. Khanlari, Broadcasting in highly connected graphs , submitted .
  4. L. Taieb, M. Roucairol, T. Cazenave, A. Harutyunyan, Automated Refutation with Monte Carlo Search of Graph Theory Conjectures on the Maximum Laplacian Eigenvalue , submitted .
  5. H. Abgaryan, A. Harutyunyan, T. Cazenave, LLMs can schedule , submitted .
  6. H. Abgaryan, A. Harutyunyan, T. Cazenave, Randomized Greedy Sampling for JSSP , LION 2024 .
  7. R. Belmonte, A. Harutyunyan, N. Kohler, N. Melissinos, Odd chromatic number of graph classes , (journal version of WG 2023), to appear in Journal of Graph Theory .
  8. R. Belmonte, A. Harutyunyan, N. Kohler, N. Melissinos, Odd chromatic number of graph classes , WG 2023, LNCS 14093, pp. 44–58 .
  9. A. Harutyunyan, L. Harutyunyan, N. Hovhannisyan, Coloring k-partite sparse digraphs , Discrete Applied Mathematics 353: pp. 1--3, 2024.
  10. T. Denat, A. Harutyunyan, V. Paschos, Average-case complexity of a branch-and-bound algorithm for Min Dominating Set , Discrete Applied Mathematics 345, pp.4--8, 2024
  11. A. Harutyunyan, M. Lampis, N. Melissinos, Digraph Coloring and Distance to acyclicity , Theory of Computing Systems, 2022
    (a conference version of this paper with some of the results appeared in STACS 2021)
  12. L. Gourvès, A. Harutyunyan, M. Lampis, N. Melissinos, Filling Crosswords is Very Hard , ISAAC 2021: 36:1--36:16
  13. A. Harutyunyan, M. Lampis, N. Melissinos, Digraph Coloring and Distance to acyclicity , STACS 2021 41:1-41:15.
  14. A. Harutyunyan, P. Horn, J. Verstraete, Independent dominating sets in graphs of girth five ,Combinatorics, Probability and Computing 30 (3):, pp. 344-359, 2021 .
  15. A. Harutyunyan, L. Pastor, S. Thomassé Disproving the normal graphs conjecture , Journal of Combinatorial Theory (Ser. B) 147, 238-251, 2021 .
  16. A. Harutyunyan, M.K.Ghadikolaei, N. Melissinos, J. Monnot, A. Pagourtzis, On the Complexity of the Upper r-Tolerant Edge Cover Problem , TTCS 2020: Topics in Theoretical Computer Science, pp 32--47.
  17. A. Harutyunyan, M. Lampis, V. Lozin, J. Monnot, Maximum independent sets in subcubic graphs: new results, Theoretical Computer Science 846, 14-26, 2020.
    (a conference version with a more complicated proof appeared in WG 2019).
  18. A. Harutyunyan, T.-N. Le, A. Newman, S. Thomassé, Coloring dense digraphs , Combinatorica 39(5): 1021-1053, 2019 .
  19. N. Bousquet, L. Esperet, A. Harutyunyan, R. de Joannis de Verclos, Exact distance coloring in trees , Combinatorics, Probability and Computing 28(2): 177--186, 2019.
  20. A. Harutyunyan, T.-N. Le, S. Thomassé, H. Wu, Coloring tournaments: from local to global , Journal of Combinatorial Theory (Ser. B) 138: 166--171, 2019.
  21. J. Bensmail, A. Harutyunyan, T.-N. Le, S. Thomassé, Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture , Combinatorica 39(2): 239--263, 2019.
  22. A. Beynier, Y. Chevaleyre, L. Gourvès, A. Harutyunyan, J. Lesca, N. Maudet, A. Wilczynski, Local envy-freeness in house allocation problems , Autonomous Agents and Multi-Agent Systems 33(5): 591--627, 2019.
  23. A. Harutyunyan, M. Lampis, V. Lozin, J. Monnot, Maximum independent sets in subcubic graphs: new results , WG 2019:40--52.
  24. A. Harutyunyan, T.-N. Le, A. Newman, S. Thomassé, Domination and fractional domination in digraphs , Electronic Journal of Combinatorics 25(3): P3.32, 2018.
  25. J. Bensmail, A. Harutyunyan, N.-K. Le, List coloring digraphs , Journal of Graph Theory, 87(4): 492--508, 2018.
  26. J. Bensmail, A. Harutyunyan, T.-N. Le, M. Merker, S. Thomassé, A proof of the Barát-Thomassen conjecture , Journal of Combinatorial Theory, Ser. B 124, pp. 39 – 55, 2017.
  27. J. Bensmail, A. Harutyunyan, N.-K. Le, B. Li, N. Lichiardopol, Disjoint cycles of different lengths in graphs and digraphs, Electronic Journal of Combinatorics 24(4): P4.37, 2017.
  28. F. Foucaud, A. Harutyunyan, P. Hell, S. Legay, R. Naserasr, Y. Manoussakis, The complexity of tropical graph homomorphisms , Discrete Applied Mathematics 229: 64--81 (2017) .
  29. A. Harutyunyan, B. Mohar, Planar digraphs of digirth five are 2-colorable , Journal of Graph Theory 84(4): 408 - 427, 2017 .
  30. J-A. Angles d'Auriac, N. Cohen, A. El Maftouhi, A. Harutyunyan, S. Legay, Y. Manoussakis, Connected tropical subgraphs in vertex-colored graphs , Discrete Mathematics and Theoretical Computer Science 17:3, pp. 327-348, 2016 .
  31. A. Harutyunyan, R. Naserasr, M. Petrusevski, R. Skrekovski, Q. Sun, Mapping planar graphs into the Coxeter graph, Discrete Mathematics 339, pp. 839 - 849, 2016 .
  32. A. Harutyunyan, S. Legay, Linear time algorithms for weighted offensive and powerful alliances in trees , Theoretical Computer Science 582, pp. 17 - 26, 2015.
  33. A. El Maftouhi, A. Harutyunyan, Y. Manoussakis, Weak balance in random signed graphs , Internet Mathematics 11(2), pp. 143-154, 2015.
  34. J. Bensmail, A. Harutyunyan, H. Hocquard, P. Valicov, Strong-edge coloring of planar graphs , Discrete Applied Mathematics 179, pp. 229-234, 2014.
  35. A. Harutyunyan, Global Offensive Alliances in Graphs and Random Graphs. , Discrete Applied Mathematics 164, pp. 522-526, 2014.
  36. A. Harutyunyan, Some bounds on global alliances in trees , Discrete Applied Mathematics 161, pp. 1739-1746, 2013 .
  37. A. Harutyunyan, P.M. Kayll, B. Mohar, L. Rafferty, Uniquely D-colorable digraphs with large girth , The Canadian Journal of Mathematics 64, 1310-1328, 2012.
  38. A. Harutyunyan, B. Mohar, Planar graphs have exponentially many 3-arboricities , SIAM Journal on Discrete Mathematics 26(3), pp. 1269-1280, 2012.
  39. A. Harutyunyan, B. Mohar, Two results on the digraph chromatic number , Discrete Mathematics 312(10), pp. 1823-1826, 2012 .
  40. A. Harutyunyan, B. Mohar, Gallai's Theorem for List Coloring of Digraphs , SIAM Journal on Discrete Mathematics 25(1), pp. 170-180, 2011.
  41. A. Harutyunyan, B. Mohar, Strengthened Brooks Theorem for digraphs of girth three , The Electronic Journal of Combinatorics 18 (2011), #P195.
  42. A. Harutyunyan, A Fast Algorithm for Powerful Alliances in Trees , 4th International Conference on Combinatorial Optimization and Applications ( COCOA 2010 ), Kailua-Kona, HI, USA,
    LNCS 6508 (1) 2010: 31-40.
  43. A. Harutyunyan, Global Offensive Alliances in Graphs via Degree Sequences , VI Latin-American Conference Algorithms, Graphs and Optimization Symposium ( LAGOS 2011 ).
  44. A. Harutyunyan, Some Bounds on Alliances in Trees, 9th Cologne Twente Workshop on Graphs and Combinatorial Optimization ( CTW 2010 ), Cologne, Germany, 2010: 83-86.

Useful homepages

Noga Alon , Bojan Mohar, Stéphan Thomassé , Jacques Verstraete, Pavol Hell, Alex Scott, Jacob Fox

 

Journals

Upcoming conferences 2019/2020

First Armenian Workshop on Graphs, Combinatorics and Probability and their applications to machine learning , Armenia, June 1-7, 2019.

Journees Graphes et Algorithmes , Bruxelles (ULB), November 13-15, 2019.

Teaching

 

Graph Theory, Winter 2021.

Probabilistic Methods in Discrete Mathematics (PhD course), Winter 2019, University Paris-Dauphine.

Probability Theory, Fall 2018, University Paris-Dauphine.

Combinatorial Optimisation, Winter 2018, University Paris-Dauphine.

Data Analysis, Fall 2018, 2019, 2020 University Paris-Dauphine.

Graph algorithms with applications, Fall 2017, 2018, 2019, University Paris-Dauphine.

Graph Theory, Winter 2016 and 2017, Supaero-Isae, Toulouse.

MACM 201 (Discrete Mathematics II), Winter 2012, SFU. Teaching Evaluation .

MATH 150 (Calculus I), Fall 2011, SFU. Teaching Evaluation .

Some slides of talks

A proof of the Barat-Thomassen Conjecture, 3rd Bordeaux Graph Workshop, Bordeaux, France, November 7-10, 2016 Slides .

Colorings in planar graphs and digraphs, SIAM conference on Discrete Mathematics, Minneapolis, USA, June 16-19, 2014 Slides .

Sparsity and homomorphisms of digraphs, Slides .

Miscellaneous

Erdos number: 2 (through Pavol Hell )

Personal

Other.