FLIPS IN GRAPHS

被引：1

作者：

Bohman, Tom ^{[1
]}

Dudek, Andrzej ^{[1
]}

Frieze, Alan ^{[1
]}

Pikhurko, Oleg ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2010年 / 24卷 / 03期

基金：

美国国家科学基金会;

关键词：

quantum error-correcting codes; random graphs;

D O I：

10.1137/090752237

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study a problem motivated by a question related to quantum error-correcting codes. Combinatorially, it involves the graph parameter f(G) = min{vertical bar A vertical bar + vertical bar{x is an element of V \ A : d(A)(x) is odd}vertical bar : A not equal empty set}, where V is the vertex set of G and d(A)(x) is the number of neighbors of x in A. We give asymptotically tight estimates of f for the random graph G(n,p) when p is constant. Also, if f(n) = max{f(G) : vertical bar V (G)vertical bar = n}, then we show that f(n) <= (0.382 + o(1))n.

引用

页码：1046 / 1055

页数：10