Bounding the size of square-free subgraphs of the hypercube

被引：19

作者：

Thomason, Andrew ^{[1
]}

Wagner, Peter ^{[1
]}

机构：

[1] DPMMS, Ctr Math Sci, Cambridge CB3 0WB, England

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 06期

关键词：

Hypercube; n-cube; 4-cycle; CUBE;

D O I：

10.1016/j.disc.2008.02.015

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We investigate the maximum size of a Subset of the edges of the n-cube that does not contain a square, or 4-cycle. The size of Such a subset is trivially at most 3/4 of the total number of edges, but the proportion was conjectured by Erdos to be asymptotically 1/2. Following a Computer investigation of the 4-cube and the 5-cube, we improve the known upper bound from 0.62284 ... to 0.62256 ... in the limit. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：1730 / 1735

页数：6

共 8 条

[1] A Ramsey-type result for the hypercube
Alon, Noga
Radoicic, Rados
Sudakov, Benny
Vondrak, Jan
[J]. JOURNAL OF GRAPH THEORY, 2006, 53 (03) : 196 - 208
[2] ON THE MAXIMUM NUMBER OF EDGES IN A C4-FREE SUBGRAPH OF Q(N)
BRASS, P
HARBORTH, H
NIENBORG, H
[J]. JOURNAL OF GRAPH THEORY, 1995, 19 (01) : 17 - 23
[3] SUBGRAPHS OF A HYPERCUBE CONTAINING NO SMALL EVEN CYCLES
CHUNG, FRK
[J]. JOURNAL OF GRAPH THEORY, 1992, 16 (03) : 273 - 286
[4] Erds P., 1984, Graph theory and combinatorics (Cambridge, 1983), P1
[5] Harborth H., 1994, B I COMBIN APPL, V12, P55
[6] LARGEST INDUCED SUBGRAPHS OF THE N-CUBE THAT CONTAIN NO 4-CYCLES
JOHNSON, KA
ENTRINGER, R
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (03) : 346 - 355
[7] Schelp RH, 2000, J GRAPH THEOR, V33, P66, DOI 10.1002/(SICI)1097-0118(200002)33:2<66::AID-JGT2>3.0.CO
[8] 2-L

← 1 →