Generalized Rank Functions and an Entropy Argument

Jeff Kahn; Alexander Lawrenz

doi:10.1006/jcta.1999.2965

Generalized Rank Functions and an Entropy Argument

Jeff Kahn, Alexander Lawrenz

School of Arts and Sciences, Mathematics

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

A rank function is a function f:2^[d]→N such that f()=0 and f(A)≤ f(A∪x)≤f(A)+1 for all A⊆[d], x∈[d]\A. Athanasiadis conjectured an upper bound on the number of rank functions on 2^[d]. We prove this conjecture and generalize it to functions with bounded jumps.

Original language	English (US)
Pages (from-to)	398-403
Number of pages	6
Journal	Journal of Combinatorial Theory. Series A
Volume	87
Issue number	2
DOIs	https://doi.org/10.1006/jcta.1999.2965
State	Published - Aug 1999

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jcta.1999.2965

Cite this

@article{323af1798942445aa83772fe31e186b4,

title = "Generalized Rank Functions and an Entropy Argument",

abstract = "A rank function is a function f:2[d]→N such that f()=0 and f(A)≤ f(A∪x)≤f(A)+1 for all A⊆[d], x∈[d]\A. Athanasiadis conjectured an upper bound on the number of rank functions on 2[d]. We prove this conjecture and generalize it to functions with bounded jumps.",

author = "Jeff Kahn and Alexander Lawrenz",

note = "Funding Information: * Supported by NSF.",

year = "1999",

month = aug,

doi = "10.1006/jcta.1999.2965",

language = "English (US)",

volume = "87",

pages = "398--403",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Generalized Rank Functions and an Entropy Argument

AU - Kahn, Jeff

AU - Lawrenz, Alexander

N1 - Funding Information: * Supported by NSF.

PY - 1999/8

Y1 - 1999/8

N2 - A rank function is a function f:2[d]→N such that f()=0 and f(A)≤ f(A∪x)≤f(A)+1 for all A⊆[d], x∈[d]\A. Athanasiadis conjectured an upper bound on the number of rank functions on 2[d]. We prove this conjecture and generalize it to functions with bounded jumps.

AB - A rank function is a function f:2[d]→N such that f()=0 and f(A)≤ f(A∪x)≤f(A)+1 for all A⊆[d], x∈[d]\A. Athanasiadis conjectured an upper bound on the number of rank functions on 2[d]. We prove this conjecture and generalize it to functions with bounded jumps.

UR - http://www.scopus.com/inward/record.url?scp=0000741333&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000741333&partnerID=8YFLogxK

U2 - 10.1006/jcta.1999.2965

DO - 10.1006/jcta.1999.2965

M3 - Article

AN - SCOPUS:0000741333

SN - 0097-3165

VL - 87

SP - 398

EP - 403

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

IS - 2

ER -

Generalized Rank Functions and an Entropy Argument

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this