RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Algebra Discrete Math.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Algebra Discrete Math., 2014, том 17, выпуск 1, страницы 33–69 (Mi adm458)  

Эта публикация цитируется в 15 научных статьях (всего в 15 статьях)

RESEARCH ARTICLE

Algorithmic computation of principal posets using Maple and Python

Marcin Gąsiorek, Daniel Simson, Katarzyna Zając

Faculty of Mathematics and Computer, Science, Nicolaus Copernicus University, 87-100 Toruń, Poland

Аннотация: We present symbolic and numerical algorithms for a computer search in the Coxeter spectral classification problems. One of the main aims of the paper is to study finite posets $I$ that are principal, i.e., the rational symmetric Gram matrix $G_I : = \frac{1}{2}[C_I+ C^{tr}_I]\in\mathbb{M}_I(\mathbb{Q})$ of $I$ is positive semi-definite of corank one, where $C_I\in\mathbb{M}_I(\mathbb{Z})$ is the incidence matrix of $I$. With any such a connected poset $I$, we associate a simply laced Euclidean diagram $DI\in \{\widetilde{\mathbb{A}}_n, \widetilde{\mathbb{D}}_n, \widetilde{\mathbb{E}}_6, \widetilde{\mathbb{E}}_7, \widetilde{\mathbb{E}}_8\}$, the Coxeter matrix $Cox_I:= - C_I\cdot C^{-tr}_I$, its complex Coxeter spectrum ${\mathbf{specc}}_I$, and a reduced Coxeter number $\check {\mathbf{c}}_I$. One of our aims is to show that the spectrum ${\mathbf{specc}}_I$ of any such a poset $I$ determines the incidence matrix $C_I$ (hence the poset $I$) uniquely, up to a $\mathbb{Z}$-congruence.
By computer calculations, we find a complete list of principal one-peak posets $I$ (i.e., $I$ has a unique maximal element) of cardinality $\leq 15$, together with ${\mathbf{specc}}_I$, $\check {\mathbf{c}}_I$, the incidence defect $\partial_I:\mathbb{Z}^I \to\mathbb{Z}$, and the Coxeter-Euclidean type $DI$. In case when $DI \in \{\widetilde{\mathbb{A}}_n, \widetilde{\mathbb{D}}_n , \widetilde{\mathbb{E}}_6, \widetilde{\mathbb{E}}_7, \widetilde{\mathbb{E}}_8\}$ and $n:=|I|$ is relatively small, we show that given such a principal poset $I$, the incidence matrix $ C_I$ is $\mathbb{Z}$-congruent with the non-symmetric Gram matrix $ \check G_{DI}$ of $DI$, ${\mathbf{specc}}_I = {\mathbf{specc}}_{DI}$ and $\check {\mathbf{c}}_I= \check {\mathbf{c}}_{DI}$. Moreover, given a pair of principal posets $I$ and $J$, with $|I|= |J| \leq 15$, the matrices $C_I$ and $C_J$ are $\mathbb{Z}$-congruent if and only if ${\mathbf{specc}}_I= {\mathbf{specc}}_J$.

Ключевые слова: principal poset; edge-bipartite graph; unit quadratic form; computer algorithm; Gram matrix, Coxeter polynomial, Coxeter spectrum.

Полный текст: PDF файл (446 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
Тип публикации: Статья
MSC: 06A11, 15A63, 68R05, 68W30
Поступила в редакцию: 08.08.2013
Исправленный вариант: 08.08.2013
Язык публикации: английский

Образец цитирования: Marcin Gąsiorek, Daniel Simson, Katarzyna Zając, “Algorithmic computation of principal posets using Maple and Python”, Algebra Discrete Math., 17:1 (2014), 33–69

Цитирование в формате AMSBIB
\RBibitem{GasSimZaj14}
\by Marcin~G{\k a}siorek, Daniel~Simson, Katarzyna~Zaj{\k a}c
\paper Algorithmic computation of principal posets using Maple and Python
\jour Algebra Discrete Math.
\yr 2014
\vol 17
\issue 1
\pages 33--69
\mathnet{http://mi.mathnet.ru/adm458}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3288184}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000352198400003}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/adm458
  • http://mi.mathnet.ru/rus/adm/v17/i1/p33

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Polak A., Simson D., “Coxeter Spectral Classification of Almost Tp-Critical One-Peak Posets Using Symbolic and Numeric Computations”, Linear Alg. Appl., 445 (2014), 223–255  crossref  mathscinet  zmath  isi  elib  scopus
    2. Marczak G., Simson D., Zajac K., “on Computing Non-Negative Loop-Free Edge-Bipartite Graphs”, 2013 15Th International Symposium on Symbolic and Numeric Algorithms For Scientific Computing (Synasc 2013), eds. Bjorner N., Negru V., Ida T., Jebelean T., Petcu D., Watt S., Zaharie D., IEEE, 2014, 68–75  crossref  isi  scopus
    3. Gasiorek M. Simson D. Zajac K., “On Corank Two Edge-Bipartite Graphs and Simply Extended Euclidean Diagrams”, 16Th International Symposium on Symbolic and Numeric Algorithms For Scientific Computing (Synasc 2014), ed. Winkler F. Negru V. Ida T. Jebelean T. Petcu D. Watt S. Zaharie D., IEEE Computer Soc, 2014, 66–73  crossref  isi  scopus
    4. Gasiorek M., “Efficient Computation of the Isotropy Group of a Finite Graph: a Combinatorial Approach”, 2013 15Th International Symposium on Symbolic and Numeric Algorithms For Scientific Computing (Synasc 2013), International Symposium on Symbolic and Numeric Algorithms For Scientific Computing, eds. Bjorner N., Negru V., Ida T., Jebelean T., Petcu D., Watt S., Zaharie D., IEEE, 2014, 104–111  crossref  isi  scopus
    5. Felisiak M., Simson D., “Applications of Matrix Morsifications To Coxeter Spectral Study of Loop-Free Edge-Bipartite Graphs”, Discrete Appl. Math., 192:SI (2015), 49–64  crossref  mathscinet  zmath  isi  elib  scopus
    6. Gasiorek M., Simson D., Zajac K., “on Coxeter Type Study of Non-Negative Posets Using Matrix Morsifications and Isotropy Groups of Dynkin and Euclidean Diagrams”, Eur. J. Comb., 48:SI (2015), 127–142  crossref  mathscinet  zmath  isi  elib  scopus
    7. Gasiorek M. Simson D. Zajac K., “Structure and a Coxeter-Dynkin Type Classification of Corank Two Non-Negative Posets”, Linear Alg. Appl., 469 (2015), 76–113  crossref  mathscinet  zmath  isi  elib  scopus
    8. Kasjan S., Simson D., “Mesh Algorithms For Coxeter Spectral Classification of Cox-Regular Edge-Bipartite Graphs With Loops, i. Mesh Root Systems”, Fundam. Inform., 139:2 (2015), 153–184  crossref  mathscinet  zmath  isi  elib  scopus
    9. Kasjan S., Simson D., “Mesh Algorithms For Coxeter Spectral Classification of Cox-Regular Edge-Bipartite Graphs With Loops, II. Application To Coxeter Spectral Analysis”, Fundam. Inform., 139:2 (2015), 185–209  crossref  mathscinet  zmath  isi  elib  scopus
    10. Kasjan S., Simson D., “Algorithms For Isotropy Groups of Cox-Regular Edge-Bipartite Graphs”, Fundam. Inform., 139:3 (2015), 249–275  crossref  mathscinet  zmath  isi  elib  scopus
    11. M. Gasiorek, D. Simson, K. Zajac, “A Gram classification of non-negative corank-two loop-free edge-bipartite graphs”, Linear Alg. Appl., 500 (2016), 88–118  crossref  mathscinet  zmath  isi  elib  scopus
    12. D. Simson, “Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, I. A Gram classification”, Fundam. Inform., 145:1 (2016), 19–48  crossref  mathscinet  zmath  isi  scopus
    13. D. Simson, “Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, II. Isotropy mini-groups”, Fundam. Inform., 145:1 (2016), 49–80  crossref  mathscinet  zmath  isi  scopus
    14. D. Simson, K. Zajac, “Inflation algorithm for loop-free non-negative edge-bipartite graphs of corank at least two”, Linear Alg. Appl., 524 (2017), 109–152  crossref  mathscinet  zmath  isi  scopus
    15. K. Zajac, “Numeric algorithms for corank two edge-bipartite graphs and their mesh geometries of roots”, Fundam. Inform., 152:2 (2017), 185–222  crossref  mathscinet  isi  scopus
  • Algebra and Discrete Mathematics
    Просмотров:
    Эта страница:362
    Полный текст:53
    Литература:34
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020