Boolean complexes for Ferrers graphs

Anders Claesson, Sergey Kitaev, Kari Ragnarsson, Bridget Eileen Tenner

Research output: Contribution to journalArticle

6 Citations (Scopus)

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.
LanguageEnglish
Pages159-173
Number of pages15
JournalAustralasian Journal of Combinatorics
Volume48
Publication statusPublished - Oct 2010

Fingerprint

Graph in graph theory
Stirling numbers of the second kind
Stirling numbers
Complete Bipartite Graph
Homotopy Type
Legendre
Recursion
Explicit Formula

Keywords

  • Ferrers graph
  • boolean complex
  • bipartite graphs

Cite this

Claesson, A., Kitaev, S., Ragnarsson, K., & Tenner, B. E. (2010). Boolean complexes for Ferrers graphs. Australasian Journal of Combinatorics, 48, 159-173.
Claesson, Anders ; Kitaev, Sergey ; Ragnarsson, Kari ; Tenner, Bridget Eileen. / Boolean complexes for Ferrers graphs. In: Australasian Journal of Combinatorics. 2010 ; Vol. 48. pp. 159-173.
@article{ab7450043df947eaac23b00765c07eec,
title = "Boolean complexes for Ferrers graphs",
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.",
keywords = "Ferrers graph, boolean complex, bipartite graphs",
author = "Anders Claesson and Sergey Kitaev and Kari Ragnarsson and Tenner, {Bridget Eileen}",
year = "2010",
month = "10",
language = "English",
volume = "48",
pages = "159--173",
journal = "Australasian Journal of Combinatorics",
issn = "1034-4942",
publisher = "University of Queensland Press",

}

Claesson, A, Kitaev, S, Ragnarsson, K & Tenner, BE 2010, 'Boolean complexes for Ferrers graphs' Australasian Journal of Combinatorics, vol. 48, pp. 159-173.

Boolean complexes for Ferrers graphs. / Claesson, Anders; Kitaev, Sergey; Ragnarsson, Kari; Tenner, Bridget Eileen.

In: Australasian Journal of Combinatorics, Vol. 48, 10.2010, p. 159-173.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Boolean complexes for Ferrers graphs

AU - Claesson, Anders

AU - Kitaev, Sergey

AU - Ragnarsson, Kari

AU - Tenner, Bridget Eileen

PY - 2010/10

Y1 - 2010/10

N2 - 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.

AB - 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.

KW - Ferrers graph

KW - boolean complex

KW - bipartite graphs

UR - http://ajc.maths.uq.edu.au/?page=get_volumes&volume=48

UR - http://arxiv.org/abs/0808.2307

M3 - Article

VL - 48

SP - 159

EP - 173

JO - Australasian Journal of Combinatorics

T2 - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

SN - 1034-4942

ER -

Claesson A, Kitaev S, Ragnarsson K, Tenner BE. Boolean complexes for Ferrers graphs. Australasian Journal of Combinatorics. 2010 Oct;48:159-173.