2010/09/18 by Richard Ehrenborg, Gábor Hetyei, Margaret Readdy · 3 citations
Computer Science · Mathematics · #Adjacency matrix #Advanced Combinatorial Mathematics #Bipartite graph #Commutative Algebra and Its Applications #Eulerian path #Indecomposable module #Matrix (chemical analysis) #Partially ordered set #Polynomial and algebraic computation #Property (philosophy) #Star product #math.CO #msc:05A15 #msc:05C30 #msc:06A07 #msc:52B22 #msc:57M15
paper · pdf · doi:10.1007/s00373-012-1173-z
published in Graphs and Combinatorics 29(4), 857-882 (Springer Science+Business Media)
arxiv created 2010/09/18 · openalex publication_date 2012/04/23 · arxiv updated 2014/06/10 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
The notion of level posets is introduced. This class of infinite posets has the property that between every two adjacent ranks the same bipartite graph occurs. When the adjacency matrix is indecomposable, we determine the length of the longest interval one needs to check to verify Eulerianness. Furthermore, we show that every level Eulerian poset associated to an indecomposable matrix has even order. A condition for verifying shellability is introduced and is automated using the algebra of walks. Applying the Skolem--Mahler--Lech theorem, the \bf ab-series of a level poset is shown to be a rational generating function in the non-commutative variables \bf a and \bf b. In the case the poset is also Eulerian, the analogous result holds for the \bf cd-series. Using coalgebraic techniques a method is developed to recognize the \bf cd-series matrix of a level Eulerian poset.