Zobrazeno 1 - 10
of 65
pro vyhledávání: '"Vincent Vatter"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 18 no. 2, Permutation..., Iss Permutation Patterns (2016)
The Permutation Pattern Matching problem, asking whether a pattern permutation $\pi$ is contained in a permutation $\tau$, is known to be NP-complete. In this paper we present two polynomial time algorithms for special cases. The first algorithm is a
Externí odkaz:
https://doaj.org/article/c4a82c70b05e44ed8b99bccd9f615910
Autor:
Vincent Vatter
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 18 no. 2, Permutation..., Iss Permutation Patterns (2016)
Let $\mathcal{C}$ be a permutation class that does not contain all layered permutations or all colayered permutations. We prove that there is a constant $c$ such that every permutation in $\mathcal{C}$ of length $n$ contains a monotone subsequence of
Externí odkaz:
https://doaj.org/article/6b5374ad53e2402283c6df94706fb20c
Autor:
Jay Pantone, Vincent Vatter
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AT,..., Iss Proceedings (2014)
The Rearrangement Conjecture states that if two words over $\mathbb{P}$ are Wilf-equivalent in the factor order on $\mathbb{P}^{\ast}$ then they are rearrangements of each other. We introduce the notion of strong Wilf-equivalence and prove that if tw
Externí odkaz:
https://doaj.org/article/8a5d9199235843c6b573e0b38bbbdcfa
The study of permutation patterns is a thriving area of combinatorics that relates to many other areas of mathematics, including graph theory, enumerative combinatorics, model theory, the theory of automata and languages, and bioinformatics. Arising
Autor:
Bogdan Alecu, Robert Ferguson, Mamadou Moustapha Kanté, Vadim V. Lozin, Vincent Vatter, Victor Zamaraev
Publikováno v:
SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, 2022, 36 (4), pp.2774-2797. ⟨10.1137/21M1449646⟩
SIAM Journal on Discrete Mathematics, 2022, 36 (4), pp.2774-2797. ⟨10.1137/21M1449646⟩
International audience; We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d11b453c5b495b9f5d920c73f7b195ac
https://doi.org/10.1137/21m1449646
https://doi.org/10.1137/21m1449646
Autor:
Robert Ferguson, Vincent Vatter
Publikováno v:
Discrete Applied Mathematics. 309:215-220
We prove that if the prime graphs in a graph class have bounded lettericity, then the entire class has bounded lettericity if and only if it does not contain arbitrary large matchings, co-matchings, or a family of graphs that we call stacked paths.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::01e3299bb9ff228937da21118459e12d
https://doi.org/10.1016/j.dam.2021.11.007
https://doi.org/10.1016/j.dam.2021.11.007
Autor:
Vincent Vatter
Publikováno v:
Math Horizons. 30:18-19
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::df5b93184440a719eee4c4cbbcc2f123
https://doi.org/10.1080/10724117.2022.2145784
https://doi.org/10.1080/10724117.2022.2145784
Autor:
Vincent Vatter, Michael Engen
Publikováno v:
The American Mathematical Monthly. 128:4-24
Numerous versions of the question "what is the shortest object containing all permutations of a given length?" have been asked over the past fifty years: by Karp (via Knuth) in 1972; by Chung, Diaconis, and Graham in 1992; by Ashlock and Tillotson in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4b0269c6f1c81527a8dc21038ef81ab5
https://doi.org/10.1080/00029890.2021.1835384
https://doi.org/10.1080/00029890.2021.1835384
Autor:
Vincent Vatter
Publikováno v:
Math Horizons. 29:5-7
Harry Dweighter is a longtime restaurant owner who is famous for pondering the mathematics behind flipping pancakes (Problem E2569, Amer. Math. Monthly, 82 [1975], 1010). With the COVID-19 pandemic...
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f362ee75a34311bc0b9127fc89485749
https://doi.org/10.1080/10724117.2021.1940520
https://doi.org/10.1080/10724117.2021.1940520
Graphs & Digraphs, Seventh Edition masterfully employs student-friendly exposition, clear proofs, abundant examples, and numerous exercises to provide an essential understanding of the concepts, theorems, history, and applications of graph theory. Th