Title: Boolean complexes for Ferrers graphs
Authors: Anders Claesson, Sergey Kitaev, Kári Ragnarsson, Bridget Tenner
Status: Submitted
Abstract: In this paper we provide an explicit formula for calculating the
boolean number of a Ferrers graph. By previous work of the last two authors,
this determines the homotopy type of the boolean complex of the graph.
Specializing to staircase shapes, we show that the boolean numbers of the
associated Ferrers graphs are the Genocchi numbers of the second kind, and
obtain a relation between the Legendre-Stirling numbers and the Genocchi
numbers of the second kind. In another application, we compute the boolean
number of a complete bipartite graph, corresponding to a rectangular Ferrers
shape, which is expressed in terms of the Stirling numbers of the second
kind. Finally, we analyze the complexity of calculating the boolean number
of a Ferrers graph using these results and show that it is a significant
improvement over calculating by edge recursion.