Thresholds for families of multisets, with an application to graph pebbling

Airat Bekmetjev; Graham Brightwell; Andrzej Czygrinow; Glenn Hurlbert

doi:10.1016/S0012-365X(02)00745-8

Thresholds for families of multisets, with an application to graph pebbling

Airat Bekmetjev, Graham Brightwell, Andrzej Czygrinow, Glenn Hurlbert

Mathematical and Statistical Sciences, School of (SoMSS)

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

18 Scopus citations

Abstract

In this paper we prove two multiset analogs of classical results. We prove a multiset analog of Lovász's version of the Kruskal-Katona Theorem and an analog of the Bollobás-Thomason threshold result. As a corollary we obtain the existence of pebbling thresholds for arbitrary graph sequences. In addition, we improve both the lower and upper bounds for the, 'random pebbling' threshold of the sequence of paths.

Original language	English (US)
Pages (from-to)	21-34
Number of pages	14
Journal	Discrete Mathematics
Volume	269
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(02)00745-8
State	Published - Jul 28 2003

Keywords

Multiset lattice
Pebbling number
Shadow
Threshold

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(02)00745-8

Cite this

@article{cb907049a745403cb12e6ae3a98bb9af,

title = "Thresholds for families of multisets, with an application to graph pebbling",

abstract = "In this paper we prove two multiset analogs of classical results. We prove a multiset analog of Lov{\'a}sz's version of the Kruskal-Katona Theorem and an analog of the Bollob{\'a}s-Thomason threshold result. As a corollary we obtain the existence of pebbling thresholds for arbitrary graph sequences. In addition, we improve both the lower and upper bounds for the, 'random pebbling' threshold of the sequence of paths.",

keywords = "Multiset lattice, Pebbling number, Shadow, Threshold",

author = "Airat Bekmetjev and Graham Brightwell and Andrzej Czygrinow and Glenn Hurlbert",

year = "2003",

month = jul,

day = "28",

doi = "10.1016/S0012-365X(02)00745-8",

language = "English (US)",

volume = "269",

pages = "21--34",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Thresholds for families of multisets, with an application to graph pebbling

AU - Bekmetjev, Airat

AU - Brightwell, Graham

AU - Czygrinow, Andrzej

AU - Hurlbert, Glenn

PY - 2003/7/28

Y1 - 2003/7/28

N2 - In this paper we prove two multiset analogs of classical results. We prove a multiset analog of Lovász's version of the Kruskal-Katona Theorem and an analog of the Bollobás-Thomason threshold result. As a corollary we obtain the existence of pebbling thresholds for arbitrary graph sequences. In addition, we improve both the lower and upper bounds for the, 'random pebbling' threshold of the sequence of paths.

AB - In this paper we prove two multiset analogs of classical results. We prove a multiset analog of Lovász's version of the Kruskal-Katona Theorem and an analog of the Bollobás-Thomason threshold result. As a corollary we obtain the existence of pebbling thresholds for arbitrary graph sequences. In addition, we improve both the lower and upper bounds for the, 'random pebbling' threshold of the sequence of paths.

KW - Multiset lattice

KW - Pebbling number

KW - Shadow

KW - Threshold

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

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

U2 - 10.1016/S0012-365X(02)00745-8

DO - 10.1016/S0012-365X(02)00745-8

M3 - Article

AN - SCOPUS:0037803608

SN - 0012-365X

VL - 269

SP - 21

EP - 34

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Thresholds for families of multisets, with an application to graph pebbling

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this