HOME

RESEARCH

TEACHING

PERSONAL



Books

1. Patterns in permutations and words, Springer Verlag (EATCS monographs in Theoretical Computer Science book series) 2011; ISBN: 978-3-642-17332-5.

2. Words and Graphs, Springer Verlag (EATCS monographs in Theoretical Computer Science book series), to appear, with V. Lozin


Journal publications and chapters in books


3. Generalized pattern avoidance with additional restrictions, Seminaire Lotharingien de Combinatoire B48e (2003), 19 pp. pdf

4. Multi-avoidance of generalised patterns, Discrete Mathematics 260 (2003), 89-100. pdf

5. There are no iterated morphisms that define the Arshon sequence and the sigma-sequence, Journal of Automata, Languages and Combinatorics 8 (2003) 1, 43-50. pdf

6. Partially ordered generalized patterns and k-ary words, Annals of Combinatorics 7 (2003), 191-200, with T. Mansour. pdf

7. The sigma-sequence and counting occurrences of some patterns, subsequences and subwords, The Australasian Journal of Combinatorics 29 (2004), 187-200. pdf

8. Crucial words and the complexity of some extremal problems for sets of prohibited words, Journal of Combinatorial Theory - Series A 105/2 (2004), 273-289, with A. Evdokimov. ps

9. The problem of the pawns, Annals of Combinatorics 8 (2004), 81-91, with T. Mansour. ps

10. On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp. ps

11. Generating the Peano curve and counting occurrences of some patterns, Journal of Automata, Languages and Combinatorics 9 (2004) 4, 439-455, with T. Mansour and P. Seebold. ps

12. Pattern avoidance in matrices, Journal of Integer Sequences 8, no. 2 (2005), Article 05.2.2, 16pp, with T. Mansour and A. Vella. pdf

13. Simultaneous avoidance of generalized patterns, Ars Combinatoria 75 (2005), 267-288, with T. Mansour. pdf

14. Partially ordered generalized patterns, Discrete Mathematics 298 (2005), 212-229. pdf

15. On multi-avoidance of generalized patterns, Ars Combinatoria 76 (2005), 321-350, with T. Mansour. pdf

16. Linear sequences and Chebyshev polynomials, The Fibonacci Quarterly 43.3 (2005), 256-261, with T. Mansour. pdf

17. On unavoidable sets of word patterns, SIAM Journal on Discrete Mathematics 19 (2005) 2, 371-381, with A. Burstein. ps

18. Segmented partially ordered generalized patterns, Theoretical Computer Science 349 (2005) 3, 420-428. ps

19. Counting independent sets on path-schemes, Journal of Integer Sequences 9, no. 2 (2006), Article 06.2.2, 8pp. pdf

20. Classifying descents according to equivalence mod k, Electronic Journal of Combinatorics 13(1) (2006), #R64, with J. Remmel. pdf

21. Enumerating segmented patterns in compositions and encoding with restricted permutations, Integers: Electronic Journal of Combinatorial Number Theory 6 (2006), A34, 16pp., with T. McAllister and K. Petersen. pdf

22. Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944. pdf

23. Classifying descents according to parity, Annals of Combinatorics 11 (2007), 173-193, with J. Remmel. pdf

24. Partially ordered patterns and compositions, Pure Mathematics and Applications (Pu.M.A.) 17 (2007), No. 1-2, pp. 1-12, with S. Heubach and T. Mansour. pdf

25. On multi-dimensional patterns, Pure Mathematics and Applications (Pu.M.A.) 18 (2007), No. 3-4, 1-9, with J. Robbins. pdf

26. Counting ordered patterns in words generated by morphisms, Integers: Electronic Journal of Combinatorial Number Theory 8 (2008), A03, 28pp., with T. Mansour and P. Seebold. pdf

27. On uniquely k-determined permutations, Discrete Mathematics 308 (2008), 1500-1507, with S. Avgustinovich. pdf

28. On representable graphs, Journal of Automata, Languages and Combinatorics 13 (2008) 1, 45-54, with A. Pyatkin. pdf

29. Counting descents, rises, and levels, with prescribed first element, in words, Discrete Mathematics & Theoretical Computer Science 10:3 (2008) 1-22, with T. Mansour and J. Remmel. pdf

30. Word problem of the Perkins semigroup via directed acyclic graphs, Order 25 (2008) 3, 177-194, with S. Seif. pdf

31. Classification of bijections between 321- and 132-avoiding permutations, Seminaire Lotharingien de Combinatoire B60d (2008), 30 pp., with A. Claesson. pdf

32. Counting independent sets in certain classes of (almost) regular graphs, Pure Mathematics and Applications (Pu.M.A.) 19 (2008), no. 2-3, 17-26, with A. Burstein and T. Mansour. pdf

33. Partially ordered patterns and their combinatorial interpretations, Pure Mathematics and Applications (Pu.M.A.) 19 (2008), no. 2-3, 27-38, with A. Burstein. pdf

34. Counting ordered patterns in words generated by morphisms, Lecture Notes in Computer Science 5196 (2008) 287-298, with T. Mansour and P. Seebold. pdf

35. Decompositions and statistics for beta(1,0)-trees and nonseparable permutations, Advances in Applied Mathematics 42 (2009) 313-328, with A. Claesson and E. Steingrimsson. pdf

36. Equidistribution of descents, adjacent pairs, and place-value pairs on permutations, Journal of Integer Sequences, 12 (2009), Article 09.5.1, 19pp., with E. Deutsch and J. Remmel. pdf

37. Rationality, irrationality, and Wilf equivalence in generalized factor order, Electronic Journal of Combinatorics 16(2) (2009), #R22, Special volume in honor of Anders Bjorner on the occasion of his 60th birthday, with J. Liese, J. Remmel, and B. Sagan. pdf

38. A survey on partially ordered patterns, In Permutation Patterns (2010), S. Linton, N. Ruskuc, and V. Vatter, Eds., vol. 376 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 115-135. pdf

39. On shortest crucial words avoiding abelian powers, Discrete Applied Mathematics 158 (2010) 605-607. doi:10.1016/j.dam.2009.11.010, with A. Avgustinovich, A. Glen, and B. V. Halldorsson. pdf

40. Place-difference-value patterns: A generalization of generalized permutation and word patterns, Integers: Electronic Journal of Combinatorial Number Theory 10 (2010), A11, 129-154, with J. Remmel. pdf

41. On avoidance of V- and Lambda-patterns in permutations, Ars Combinatoria 97 (2010) 203-215, with A. Pyatkin. pdf

42. (2+2)-free posets, ascent sequences and pattern avoiding permutations, Journal of Combinatorial Theory - Series A 117 (2010) 7, 884-909, with M. Bousquet-Melou, A. Claesson, and M. Dukes. pdf

43. Boolean complexes for Ferrers graphs, Australasian Journal of Combinatorics 48 (2010) 159-173, with A. Claesson, K. Ragnarsson, and B. E. Tenner. pdf

44. Crucial abelian k-power-free words, Discrete Mathematics and Theoretical Computer Science 12 (2010) 5, 83-96, with A. Glen and B. V. Halldorsson. pdf

45. Avoiding substrings in compositions, Congressus Numerantium 202 (2010) 87-95, with S. Heubach. pdf

46. A direct encoding of Stoimenow's matchings as ascent sequences, Australasian Journal of Combinatorics 49 (2011) 47-59, with A. Claesson and M. Dukes. pdf

47. Pattern avoidance in partial permutations, Electronic Journal of Combinatorics 18 (2011), #R25, with A. Claesson, V. Jelinek, and E. Jelinkova. pdf

48. Enumerating (2+2)-free posets by indistinguishable elements, Journal of Combinatorics 2 (2011) 1, 139-163, with M. Dukes, J. Remmel, and E. Steingrimsson. pdf

49. On square-free permutations, Journal of Automata, Languages and Combinatorics 16 (2011) 1, 3-10, with S. Avgustinovich, A. Pyatkin, and A. Valyuzhenich. pdf

50. Word-representability of line graphs, Open Journal of Discrete Mathematics 1 (2011) 2, 96-101, with P. Salimov, C. Severs, and H. Ulfarsson. pdf

51. Enumerating (2+2)-free posets by the number of minimal elements and other statistics, Discrete Applied Mathematics 159 (2011) 2098-2108, with J. Remmel. pdf

52. A spectral approach to consecutive pattern-avoiding permutations, Journal of Combinatorics 2 (2011) 305-353, with R. Ehrenborg and P. Perry. pdf

53. Quadrant marked mesh patterns, Journal of Integer Sequences 15 (2012), Article 12.4.7, 29pp., with J. Remmel. pdf

54. Quadrant marked mesh patterns in alternating permutations, Seminaire Lotharingien de Combinatoire B68a (2012), 20pp., with J. Remmel. pdf

55. Crucial and bicrucial permutations with respect to arithmetic monotone patterns, Siberian Electronic Mathematical Reports 9 (2012) 660-671, with S. Avgustinovich and A. Valyuzhenich. pdf

56. Quadrant marked mesh patterns in 132-avoiding permutations, Pure Mathematics and Applications (Pu.M.A.) 23 (2012) 3, 219-256, with J. Remmel and M. Tiefenbruck. pdf

57. Avoidance of boxed mesh patterns on permutations, Discrete Applied Mathematics 161 (2013) 43-51, with S. Avgustinovich and A. Valyuzhenich. pdf

58. Generalized pattern matching conditions for $C_k \wr S_n$, ISRN Combinatorics, Volume 2013, Article ID 634823, 21 pages, with A. Niedermaier, J. Remmel, and M. Riehl. pdf

59. On a pattern avoidance condition for the wreath product of cyclic groups with symmetric groups, ISRN Combinatorics, Volume 2013, Article ID 806583, 17 pages, with J. Remmel and M. Riehl. pdf

60. Harmonic numbers, Catalan's triangle and mesh patterns, Discrete Mathematics 313 (2013) 1515-1531, with J. Liese. pdf

61. Quadrant marked mesh patterns in alternating permutations II, Journal of Combinatorics 4 (2013) 1, 31-65, with J. Remmel. pdf

62. An involution on beta(1,0)-trees, Advances in Applied Mathematics 51 (2013) 276-284, with A. Claesson and E. Steingrimsson. pdf

63. Restricted non-separable planar maps and some pattern avoiding permutations, Discrete Applied Mathematics 161 (2013), no. 16-17, 2514-2526, with P. Salimov, C. Severs, and H. Ulfarsson. pdf

64. Universal graphs and universal permutations, Discrete Mathematics, Algorithms and Applications 5, No. 4 (2013) 1350038 (15 pages), with A. Atminas, V. Lozin and A. Valyuzhenich. pdf

65. On the number of self-dual rooted maps, European Journal of Combinatorics 35 (2014) 377-387, with A. de Mier and M. Noy. pdf

66. The 1-box pattern on pattern-avoiding permutations, Journal of Integer Sequences 17, no. 3 (2014), Article 14.3.3, 19 pp., with J. Remmel. pdf

67. Enumeration of fixed points of an involution on beta(1,0)-trees, Graphs and Combinatorics 30 (2014) 5, 1207-1221, with A. de Mier. pdf

68. An involution on bicubic maps and beta(0,1)-trees, Australasian Journal of Combinatorics 61(1) (2015), 1-18, with A. Claesson and A. de Mier. pdf

69. Number of cycles in the graph of 312-avoiding permutations, Journal of Combinatorial Theory - Series A 129 (2015) 1-18, with R. Ehrenborg and E. Steingrimsson. pdf

70. On word-representability of polyomino triangulations, Siberian Advances in Mathematics 25 (2015) 1, 1-10, with P. Akrobotu and Z. Masarova. pdf

71. Frame patterns in n-cycles, Discrete Mathematics 338 (2015) 1197-1215, with M. Jones and J. Remmel. pdf

72. S-crucial and bicrucial permutations with respect to squares, Journal of Integer Sequences 18 (2015) 6, Article 15.6.5, 22 pp., with I. Gent, A. Konovalov, S. Linton, and P. Nightingale. pdf

73. (a,b)-rectangle patterns in permutations and words, Discrete Applied Mathematics 186 (2015) 128-146, with J. Remmel. pdf

74. Marked mesh patterns in 132-avoiding permutations II, Integers: Electronic Journal of Combinatorial Number Theory 15 (2015) A16, 33 pp., with J. Remmel and M. Tiefenbruck. pdf

75. Representing graphs via pattern avoiding words, Electronic Journal of Combinatorics 22(2) (2015), #P2.53, 20 pp., with M. Jones, A. Pyatkin and J. Remmel. pdf

76. On graphs with representation number 3, Journal of Automata, Languages and Combinatorics, to appear. pdf

77. New results on word-representable graphs, Discrete Applied Mathematics, to appear, with A. Collins and V. Lozin. pdf

78. Semi-transitive orientations and word-representable graphs, Discrete Applied Mathematics, with M. Halldorsson and A. Pyatkin. pdf


Preprints


79. Marked mesh patterns in 132-avoiding permutations III, submitted, with J. Remmel and M. Tiefenbruck. pdf

80. Mahonian STAT on words, submitted, with V. Vajnovszki. pdf

81. p-ascent sequences, submitted, with J. Remmel. pdf

82. Word-representability of triangulations of rectangular polyomino with a single domino tile, submitted, with M. Glen. pdf

83. Word-representability of subdivisions of triangular grid graphs, submitted, with T. Z. Q. Chen and B. Y. Sun. pdf

84. Pattern-avoiding alternating words, submitted, with E. Gao and P. Zhang. pdf

85. Existence of u-representation of graphs, submitted. pdf

86. Avoiding vincular patterns on alternating words, submitted, with E. Gao and P. Zhang. pdf

87. Word-representability of triangulations of grid-covered cylinder graphs, submitted, with T. Z. Q. Chen and B. Y. Sun. pdf


Conference proceedings and abstracts


88. Crucial words for the sets of non-repetitive words, Proceedings of the XXXIV International Scientific Conference "Student and Scientific-Technical Progress", Novosibirsk, Russia (1996), 35-36.

89. On crucial words for some sets of prohibitions, Proceedings of the IX International School-Seminar "Synthesis and Complexity of Management Systems", Nignii Novgorod, Russia (1998)

90. On a property of the Arshon sequence, Problems of Theoretical Cybernetics, Thesis of the Talks on the XII International Conference held in Nignii Novgorod, Russia (1999)

91. On non-existence of morphisms defining symbolic sequences, Proceedings of the XXXVII International Scientific Conference "Student and Scientific-Technical Progress", Novosibirsk, Russia (1999), p. 64.

92. On pattern avoidance, the Fifth Youth Scientific School in Discrete Mathematics and its Applications, Moscow St. University, Moscow, Russia (2001)

93. Partially ordered generalized patterns, Proceedings of the 14th International Conference on Formal Power Series & Algebraic Combinatorics, the University of Melbourne, Australia, July 8-12 (2002)

94. Independent sets on path-schemes, Proceedings of Conference on Discrete Analysis and Operations Research (DAOR'2004), Sobolev Institute of Mathematics, Novosibirsk State University, Novosibirsk, Russia (2004), p. 88.

95. Partially ordered generalized patterns and their combinatorial interpretation, The Third International Conference on Permutation Patterns, University of Florida, Gainesville, Florida, March 7-11, (2005), with A. Burstein.

96. Introduction to partially ordered patterns, Workshop on Permutation Patterns, University of Haifa, Israel, May 29-June 3, 2005.

97. Classifying descents according to equivalence mod k, Permutation Patterns Conference 2006, Reykjavik University, Reykjavik, Iceland, June 12-16 (2006), with J. Remmel.

98. A spectral approach to pattern-avoiding permutations, Proceedings of the 18th International Conference on Formal Power Series & Algebraic Combinatorics, the University of California, San Diego, USA, June 19-23 (2006), with R. Ehrenborg and P. Perry.

99. On uniquely k-determined permutations, Proceedings of the 19th International Conference on Formal Power Series & Algebraic Combinatorics, Nankai University, Tianjin, China, July 2-6 (2007), with S. Avgustinovich.

100. Generalized pattern avoidance, beta(1,0)-trees, and two-stack sortable permutations, Permutation Patterns 2007, St Andrews, Scotland, June 11-15 (2007), with A. Claesson and E. Steingrimsson.

101. Counting ordered patterns in words generated by morphisms, Pre-proceedings of the 2nd International Conference on Language and Automata Theory and Applications (LATA), Tarragona, Spain, March 13-19 (2008), 301-312, with T. Mansour and P. Seebold.

102. Classification of bijections between 321- and 132-avoiding permutations. Proceedings of the 20th International Conference on Formal Power Series & Algebraic Combinatorics, Valparaiso, Chile, June 23-27 (2008), with A. Claesson.

103. Unlabeled (2+2)-free posets, ascent sequences and pattern avoiding permutations, Discrete Math. Theor. Comput. Sci. Proc. AK (2009) 216-228. Proceedings of the 21st International Conference on Formal Power Series & Algebraic Combinatorics, Hagenberg, Austria, July 20-24 (2009), with M. Bousquet-Melou, A. Claesson, and M. Dukes.

104. Rationality, irrationality, and Wilf equivalence in generalized factor order, Discrete Math. Theor. Comput. Sci. Proc. AK (2009) 515-526. Proceedings of the 21st International Conference on Formal Power Series & Algebraic Combinatorics, Hagenberg, Austria, July 20-24 (2009), with J. Liese, J. Remmel, and B. Sagan.

105. Crucial words for abelian powers, V. Diekert, D. Nowotka (Eds.): Lecture Notes in Computer Science 5583 (2009) 264-275. Proceedings of the 13th Conference on Developments in Language Theory, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009, with A. Glen and B. V. Halldorsson. pdf

106. Enumerating (2+2)-free posets by the number of minimal elements and other statistics. Discrete Math. Theor. Comput. Sci. Proc. AK (2010) 689-700. Proceedings of the 22nd International Conference on Formal Power Series & Algebraic Combinatorics, San Francisco State University, San Francisco, USA, August 2-6 (2010), with J. Remmel.

107. Pattern avoidance in partial permutations. Discrete Math. Theor. Comput. Sci. Proc. AK (2010) 493-504. Proceedings of the 22nd International Conference on Formal Power Series & Algebraic Combinatorics, San Francisco State University, San Francisco, USA, August 2-6 (2010), with A. Claesson, V. Jelinek, and E. Jelinkova.

108. Graphs capturing alternations in words, Y. Gao, H. Lu, S. Seki, S. Yu (Eds.): Lecture Notes in Computer Science 6224 (2010) 436-437. Proceedings of the 14th Conference on Dvelopments in Language Theory, DLT 2010, London, Ontario, Canada, August 17-20, 2010, with M. Halldorsson and A. Pyatkin. pdf

109. On the representability of line graphs, Lecture Notes in Computer Science 6795 (2011) 478-479. Proceedings of the 15th Conference on Developments in Language Theory, DLT 2011, University of Milano-Bicocca, Milan, Italy, July 19-22, 2011, with P. Salimov, C. Severs and H. Ulfarsson. pdf

110. Alternation graphs, Lecture Notes in Computer Science 6986 (2011) 191-202. Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Czech Republic, June 21-24, 2011, with M. Halldorsson and A. Pyatkin. pdf

111. On permutation boxed mesh patterns, Permutation Patterns Conference, Strathclyde University, Glasgow, June 11-15 (2012), with S. Avgustinovich and A. Valyuzhenich.

112. Number of cycles in the graph of 312-avoiding permutations. Discrete Math. Theor. Comput. Sci. Proc. AK (2014) 37-48. Proceedings of the 26th International Conference on Formal Power Series & Algebraic Combinatorics, Chicago, Illinois, USA, June 29-July 3 (2014), with R. Ehrenborg and E. Steingrimsson.

113. Word-representable graphs and permutation patterns, Plenary talk at Permutation Patterns Conference, East Tennessee State University, Johnson City, TN, July 7-11 (2014).


Unpublished


114. A survey of certain pattern problems, preprint (2003), with T. Mansour. ps


Miscellaneous


115. Review of "Enumerative Combinatorics" by Charalambos A. Charalambides published by Chapman & Hall/CRC, ISBN L-58488-290-5, Hard Cover, 609 pages, The Book Review Column edited by William Gasarch, Vol 39, No 4 (2008) pdf

116. Generalized Patterns in Words and Permutations, Ph.D. thesis (2003) pdf

117. Symbolic Sequences, Crucial Words and Iterations of a Morphism, thesis for the Degree of Licentiate of Philosophy (2000) pdf

118. Crucial words for some sets of prohibitions, M.Sc. thesis (1998), in Russian.

119. Crucial words, B.Sc. thesis (1996), in Russian.


Sequences


Seventeen of my sequences appear in The On-Line Encyclopedia of Integer Sequences, ed. by N. J. A. Sloane:

A071075: Number of permutations that avoid the generalized pattern 132-4    [1, 1, 2, 6, 23, 107, 585, 3671, 25986, 204738, ...]

A071076: Number of permutations that avoid the generalized pattern 123-4    [1, 1, 2, 6, 23, 108, 598, 3815, 27532, 221708, ...]

A071077: Number of permutations that avoid the generalized pattern 1234-5  [1, 1, 2, 6, 24, 119, 705, 4857, 38142, 336291, ...]

A071088: Number of permutations that avoid the generalized pattern 12345-6 [1, 1, 2, 6, 24, 120, 719,5022, 40064, 359400, ...]

A099003 : Number  of 4 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1), (10;0),  and  (11;0) [16, 46, 106, 226, 466, 946, 1906, 3826, 7666, ...]

A099018 : Number  of 2 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1), (01;0),  and  (01;1) [4, 10, 22, 46, 94, 190, 383, 766, 1534, 3070, ...]

A099041 : Number  of 3 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1), (10;0),  and  (10;1) [8, 24, 58, 128, 270, 556, 1130, 2280, 4582, ...]

A099048 : Number  of 5 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1), (01;0), (10;0),  and  (11;0) [32, 50, 68, 86, 104, 122, 140, 158, 176, 194, ...]

A099054 : Arshon's sequence [1, 2, 3, 1, 3, 2, 3, 1, 2, 3, 2, 1, 3, 1, 2, 1, 3, 2, ...]

A099943 : Number  of 5 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1), (01;1),  and  (11;0)  [72, 98, 124, 150, 176, 202, 228, 254, 280, ...]

A099944 : Number  of 3 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1)  and  (11;0)  [76, 164, 340, 692, 1396, 2804, 5620, 11252, 22516, ...]

A099945 : Number  of 4 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1)  and  (11;0)  [188, 404, 836, 1700, 3428, 6884, 13796, 27620, ...]

A100312 : Number  of 3 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (10;0)  and  (01;1) [8, 32, 104, 304, 832, 2176, 5504, 13568, 32768, ...]

A100313 : Number  of 4 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (10;0)  and  (01;1) [16, 96, 400, 1408, 4480, 13312, 37632, 102400, ...]

A100314 : Number  of 2 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1), (01;0), (10;0),  and  (01;1) [4, 8, 14, 24, 42, 76, 142, 272, 530, 1044, ...]

A100315 : Number  of 3 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1), (01;0), (10;0),  and  (01;1) [8, 14, 22, 34, 54, 90, 158, 290, 550, 1066, ...]

A100316 : Number  of 4 x n  0-1 matrices  avoiding  the  right angled  numbered polyomino patterns  (00;1), (01;0), (10;0),  and  (01;1) [16, 24, 34, 48, 70, 108, 178, 312, 574, 1092, ...]