HOME

RESEARCH

TEACHING

PERSONAL



Book

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


Journal publications and chapters in books


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

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

4. 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

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

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

7. 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

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

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

10. 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

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

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

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

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

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

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

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

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

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

20. 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

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

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

23. 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

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

25. 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

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

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

28. 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

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

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

31. 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

32. 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

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

34. 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

35. 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

36. 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

37. 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

38. 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

39. 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

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

41. (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

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

43. 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

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

45. 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

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

47. 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

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

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

50. 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

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

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

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

54. 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

55. 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

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

57. 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

58. 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

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

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

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

62. 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

63. 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

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

65. 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

66. 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

67. 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

68. 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

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

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

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

72. (a,b)-rectangle patterns in permutations and words, Discrete Applied Mathematics, to appear, with J. Remmel. pdf

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

74. Marked mesh patterns in 132-avoiding permutations II, Integers: Electronic Journal of Combinatorial Number Theory, to appear, with J. Remmel and M. Tiefenbruck. pdf

75. S-crucial and bicrucial permutations with respect to squares, Journal of Integer Sequences, to appear, with I. Gent, A. Konovalov, S. Linton, and P. Nightingale. pdf


Preprints


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

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

78. Representing graphs via pattern avoiding words, submitted, with M. Jones, A. Pyatkin and J. Remmel. pdf

79. Semi-transitive orientations and word-representable graphs, submitted, with M. Halldorsson and A. Pyatkin. pdf

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

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

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

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


Conference proceedings and abstracts


84. 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.

85. 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)

86. 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)

87. 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.

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

89. 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)

90. 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.

91. 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.

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

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

94. 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.

95. 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.

96. 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.

97. 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.

98. 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.

99. 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.

100. 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.

101. 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

102. 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.

103. 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.

104. 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

105. 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

106. 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

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

108. 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.

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


Unpublished


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


Miscellaneous


111. 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

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

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

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

115. 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, ...]