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.