ON THE LOG CONCAVITY OF RELIABILITY AND MATROIDAL SEQUENCES

被引：10

作者：

BROWN, JI ^{[1
]}

COLBOURN, CJ ^{[1
]}

机构：

[1] UNIV WATERLOO,DEPT COMBINATOR & OPTIMIZAT,WATERLOO N2L 3G1,ON,CANADA

来源：

ADVANCES IN APPLIED MATHEMATICS | 1994年 / 15卷 / 01期

关键词：

D O I：

10.1006/aama.1994.1004

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The reliability of a graph G is the probability that G is connected, given that edges are independently operational with probability p. This is known to be a polynomial in p, and various sequences associated with this polynomial have been conjectured to be unimodal and indeed, log concave. We show that for any graph G, there is a subdivision for which the log concavity conjectures all hold. Further, we provide evidence for the well-known conjecture of the log concavity of the independent set numbers of a matroid. (C) 1994 Academic Press, Inc.

引用

页码：114 / 127

页数：14

共 27 条

[1]

AIGNER M, 1987, COMBINATORIAL GEOMET

[2] BOUNDS ON THE RELIABILITY POLYNOMIAL FOR SHELLABLE INDEPENDENCE SYSTEMS [J].

BALL, MO ;

PROVAN, JS .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (02) :166-181

[3]

Barbeau E.J., 1989, POLYNOMIALS

[4] A PROOF OF THE SUFFICIENCY OF MCMULLEN CONDITIONS FOR F-VECTORS OF SIMPLICIAL CONVEX POLYTOPES [J].

BILLERA, LJ ;

LEE, CW .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1981, 31 (03) :237-255

[5] ROOTS OF THE RELIABILITY POLYNOMIAL [J].

BROWN, JI ;

COLBOURN, CJ .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (04) :571-585

[6]

BROWN JI, 1986, CONGRESSUS NUMERATIU, V56, P71

[7]

Colbourn C., 1987, COMBINATORICS NETWOR

[8]

COMTET L, 1974, ADV COMBINATORICS

[9]

Dowling T. A., 1980, ANN DISCRETE MATH, V8, P21

[10] CHROMATIC ROOTS - SOME OBSERVATIONS AND CONJECTURES [J].

FARRELL, EJ .

DISCRETE MATHEMATICS, 1980, 29 (02) :161-167

← 1 2 3 →