On the Ramsey number of sparse 3-graphs

被引：17

作者：

Nagle, Brendan ^{[2
]}

Olsen, Sayaka ^{[3
]}

Roedl, Vojtech ^{[4
]}

Schacht, Mathias ^{[1
]}

机构：

[1] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany

[2] Univ S Florida, Dept Math, Tampa, FL 33620 USA

[3] Univ Nevada, Dept Math & Stat, Reno, NV 89557 USA

[4] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA

来源：

GRAPHS AND COMBINATORICS | 2008年 / 24卷 / 03期

基金：

美国国家科学基金会;

关键词：

Ramsey theory; hypergraphs; Burr-Erdos conjecture;

D O I：

10.1007/s00373-008-0784-x

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider a hypergraph generalization of a conjecture of Burr and Erdos concerning the Ramsey number of graphs with bounded degree. It was shown by Chvatal, Rodl, Trotter, and Szemeredi [The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), no. 3, 239-243] that the Ramsey number R(G) of a graph G of bounded maximum degree is linear in vertical bar V(G)vertical bar. We derive the analogous result for 3-uniform hypergraphs.

引用

页码：205 / 228

页数：24

共 50 条

[41] Anti-Ramsey properties of random graphs
Bohman, Tom
Frieze, Alan
Pikhurko, Oleg
Smyth, Cliff
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2010, 100 (03) : 299 - 312
[42] Ramsey Number of a Connected Triangle Matching
Gyarfas, Andras
Sarkozy, Gabor N.
JOURNAL OF GRAPH THEORY, 2016, 83 (02) : 109 - 119
[43] DIRECTED GRAPHS WITH LOWER ORIENTATION RAMSEY THRESHOLDS
Barros, Gabriel Ferreira
Cavalar, Bruno Pasqualotto
Kohayakawa, Yoshiharu
Mota, Guilherme Oliveira
Naia, Tassio
RAIRO-OPERATIONS RESEARCH, 2024, 58 (04) : 3607 - 3619
[44] A LOWER BOUND ON THE HYPERGRAPH RAMSEY NUMBER R(4,5;3)
Dybizbanski, Janusz
CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2018, 13 (02) : 112 - 115
[45] The on-line degree Ramsey number of cycles
Rolnick, David
DISCRETE MATHEMATICS, 2013, 313 (20) : 2084 - 2093
[46] An upper bound for the restricted online Ramsey number
Gonzalez, David
He, Xiaoyu
Zheng, Hanzhi
DISCRETE MATHEMATICS, 2019, 342 (09) : 2564 - 2569
[47] Ramsey degrees of bipartite graphs:: A primitive recursive proof
Fouché, WL
Pretorius, LM
Swarlepoel, CJ
DISCRETE MATHEMATICS, 2005, 293 (1-3) : 111 - 119
[48] ON THE SIZE-RAMSEY NUMBER OF TIGHT PATHS
Lu, Linyuan
Wang, Zhiyu
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (03) : 2172 - 2179
[49] ON THE LOVASZ THETA FUNCTION FOR INDEPENDENT SETS IN SPARSE GRAPHS
Bansal, Nikhil
Gupta, Anupam
Guruganesh, Guru
SIAM JOURNAL ON COMPUTING, 2018, 47 (03) : 1039 - 1055
[50] The Ramsey number of loose cycles versus cliques
Meroueh, Ares
JOURNAL OF GRAPH THEORY, 2019, 90 (02) : 172 - 188

← 1 2 3 4 5 →