LARGE INDUCED MATCHINGS IN RANDOM GRAPHS

被引：10

作者：

Cooley, Oliver ^{[1
]}

Draganic, Nemanja ^{[2
]}

Kang, Mihyun ^{[1
]}

Sudakov, Benny ^{[2
]}

机构：

[1] Graz Univ Technol, Inst Discrete Math, A-8010 Graz, Austria

[2] ETH, Dept Math, CH-8092 Zurich, Switzerland

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2021年 / 35卷 / 01期

基金：

奥地利科学基金会;

关键词：

random graphs; induced matchings; Talagrand's inequality; Paley-Zygmund inequality; LARGEST INDUCED TREE;

D O I：

10.1137/20M1330609

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given a large graph H, does the binomial random graph G(n, p) contain a copy of H as an induced subgraph with high probability? This classical question has been studied extensively for various graphs H, going back to the study of the independence number of G(n, p) by Erdos and Bollobas and by Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if C/n <= p <= 0.99 for some large constant C, then G(n, p) contains an induced matching of order approximately 2 log(q)(np), where q = 1/1 - p.

引用

页码：267 / 280

页数：14

共 20 条

[1]

[Anonymous], 2004, PROBABILISTIC METHOD

[2]

BOLLOBAS B, 1976, MATH PROC CAMBRIDGE, V80, P419, DOI 10.1017/S0305004100053056

[3]

CLARK L.H., 2001, Australasian Journal of Combinatorics, V24, P47

[4] INDUCED TREES IN SPARSE RANDOM GRAPHS [J].

DELAVEGA, WF .

GRAPHS AND COMBINATORICS, 1986, 2 (03) :227-231

[5]

delaVega WF, 1996, RANDOM STRUCT ALGOR, V9, P93, DOI 10.1002/(SICI)1098-2418(199608/09)9:1/2<93::AID-RSA6>3.0.CO

[6]

2-6

[7]

Draganic N., 2020, PREPRINT

[8]

Dutta K, 2018, P ANALCO, P168

[9] TREES IN RANDOM GRAPHS [J].

ERDOS, P ;

PALKA, Z .

DISCRETE MATHEMATICS, 1983, 46 (02) :145-150

[10] ON THE INDEPENDENCE NUMBER OF RANDOM GRAPHS [J].

FRIEZE, AM .

DISCRETE MATHEMATICS, 1990, 81 (02) :171-175

← 1 2 →