Гафниан был введён в середине XX в. в работах италвянского физика-теоретика Э.Р. Каянвелло в связи с задачами квантовой теории поля. В дальнейшем гафниан нашёл применение в комбинаторике как перечисляющая функция числа совершенных паросочетаний графов. По своему виду гафниан близок к такой более известной функции, как пфаффиан. В отличие от последней, он задаётся на симметричных, а не кососимметричных матрицах и не учитывает знаки перестановок индексов в соответствующих мономах. В данной работе рассмотрен q-гафниан - обобщение гафниана, зависящее от формальных параметров и совпадающее с исходной функцией при единичных значениях параметров. Указан комбинаторный смысл q-гафниана как производящей функции числа перестановок и числа дуговых (линейных хордовых) диаграмм определённых классов. Доказаны несколько свойств одно- и двупараметрического q-гафниана, которые являются обобщениями свойств обычного гафниана. В частности, мы приводим аналог свойства разложения по строке и аналог свойства, выражающего гафниан матрицы смежности двудольного взвешенного графа с равными долями через перманент матрицы бисмежности. Данные понятия и свойства, помимо чисто теоретического интереса, могут быть использованы при разработке алгоритмов, изучающих статистику числа инверсий определённых классов перестановок и статистику числа взаимных пересечений и вложений рёбер определённых классов дуговых диаграмм.
- Title Комбинаторные аспекты q-гафниана
- Headline Комбинаторные аспекты q-гафниана
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 69
- Date:
- DOI 10.17223/20710410/69/1
Ключевые слова
q-aналог, гафниан, дуговая диаграмма, перестановкаАвторы
Ссылки
Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. 384 с.
Смирнов Е. Ю. Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы. М.: МНИМО. 2014. 64с.
Игнатьев М. В. Квантовая комбинаторика // Матем. проев. Сер. 3. 2014. Вып. 18. С.66-111.
Haglund J. The q,t-Catalan Numbers and the Space of Diagonal Harmonics. AMS, 2007. 167 p.
Manin Yu. I. Quantum Groups and Non-Commutative Geometry. Montreal: CRM, 1988. 91 p.
Демидов E. E. Квантовые группы. M.: Факториал, 1998. 128 с.
Yang K.-W. q- Determinants and permutations // Fibonacci Quart. 1991. V. 29. No. 2. P. 160-163.
Tagawa H. A multivariable quantum determinant over a commutative ring // RIMS Kokvuroku. 1991. V. 765. P.91-103.
Shevelev V.Combinatorial minors for matrix functions and their applications // Zeszvtv Naukowe Politechniki Politech. Śląskiej. Seria: Matematvka Stosowana. 2014. No.4. P.5-16.
Bapat R. B. and Lal A.K. Inequalities for the q-permanent // Linear Algebra Appl. 1994. V.197/198. P.397-409.
Lal A. K. Inequalities for the q-permanent. II // Linear Algebra Appl. 1998. V. 274. P. 1-16.
Da Fonseca С. M. The μ-permanent of a tridiagonal matrix, orthogonal polynomials, and chain sequences // Linear Algebra Appl. 2010. V. 432. P. 1258-1266.
Da Fonseca С. M. The μ-permanent, a new graph labeling, and a known integer sequence // Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie . 2018. V.61(109). No.3. P.255-262.
De Sá E.M. Noncrossing partitions, noncrossing graphs, and q-permanental equations // Linear Algebra Appl. 2018. V. 541. P. 36-53.
De Sá E. M. Linear preservers for the q-permanent, cycle q-permanent expansions, and positive crossings in digraphs // Linear Algebra Appl. 2019. V. 561. P. 228-252.
Kocharovsky Vit. V., Kocharovsky V. V., and Tarasov S. V. The Hafnian Master Theorem // Linear Algebra Appl. 2022. V. 651. P. 144-161.
Efimov D. B. Enumeration of even and odd chord diagrams // J. Appl. Industr. Math. 2024. V. 18. No. 2. P. 216-226.
Strickland E. Classical invariant theory for the quantum symplectic group // Adv. Math. 1996. V. 123. P. 78-90.
Jing N. and Zhang J. Quantum Pfaffians and Hyper-Pfaffians // Adv. Math. 2014. V. 265. P. 336-361.
Jing N. and Zhang J. Quantum permanents and Hafnians via Pfaffans // Lett. Math. Phys. 2016. V. 106. P. 1451-1464.
Barvinok A. Combinatorics and Complexity of Partition Functions. Cham: Springer, 2016. 309 p.
Tribe R. and Zaboronski O. Pfaffian formulae for one dimensional coalescing and annihilating systems // Electronic J. Probability. 2011. V. 16. P. 2080-2103.
Sullivan E. Linear chord diagrams with long chords // Electronic J. Combinatorics. 2017. V. 24. No. 4. Article #P4.20.
Cameron N. T. and Killpatrick K. Statistics on linear chord diagrams // Discrete Math. Theoret. Computer Sci. 2019. V. 21. No. 2. Article #11.
Краско E. С., Лабутин И. H., Омельченко А. В. Перечисление помеченных и непомеченных гамильтоновых циклов в полных k- дольных графах // Зап. научн. сем. ПОМП. 2019. Т. 488. С. 119-142.
Nalli A. and Haukkanen P. On generalized Fibonacci and Lucas polynomials // Chaos, Solitons and Fractals. 2009. V. 42. P. 3179-3186.
Bednarz U. and M.M. Wołowiec-Musiał Distance Fibonacci polynomials // Symmetry. 2020. V. 12. No. 9. P. 1540.
Klazar M. On identities concerning the numbers of crossing and nesting of two edges in matchings // SIAM J. Discret. Math. 2005. V. 20. P. 960-976.
Björklund A., Gupt B., and Quesada N. A faster Hafnian formula for complex matrices and its benchmarking // J. Experimental Algorithmics. 2019. V. 24. Art. No. 1.11. P. 1-17.
Perepechko S. N. Counting near-perfect matchings on Cm ×Cn tori of odd order in the Maple system // Programming and Computer Software. 2019. V. 45. No. 2. P. 65-72.
Chmutov S., Duzhin S., and Mostovoy J. Introduction to Vassiliev Knot Invariants. Cambridge University Press, 2012. 504 p.
Reidys C. Combinatorial Computational Biology of RNA. N.Y.: Springer, 2011. 257 p.
Léger S., Costa M. B. W., and Tulpan D. Pairwise visual comparison of small RNA secondary structures with base pair probabilities. BMC Bioinformatics, 2019, vol. 20, article no. 293.
Комбинаторные аспекты q-гафниана | Прикладная дискретная математика. 2025. № 69. DOI: 10.17223/20710410/69/1
Скачать полнотекстовую версию
Загружен, раз: 56