Boolean Lattices: Ramsey Properties and Embeddings

被引:13
作者
Axenovich, Maria [1 ]
Walzer, Stefan [1 ]
机构
[1] Karlsruhe Inst Technol, Karlsruhe, Germany
来源
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS | 2017年 / 34卷 / 02期
关键词
Ramsey; Poset; Embeddings; Boolean lattice; Boolean algebra; FINITE POSETS; NUMBERS; HYPERGRAPHS; SETS;
D O I
10.1007/s11083-016-9399-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A subposet Q (') of a poset Q is a copy of a poset P if there is a bijection f between elements of P and Q (') such that x ae<currency> y in P iff f(x) ae<currency> f(y) in Q. For posets P, P ('), let the poset Ramsey number R(P, P (')) be the smallest N such that no matter how the elements of the Boolean lattice Q (N) are colored red and blue, there is a copy of P with all red elements or a copy of P (') with all blue elements. We provide some general bounds on R(P, P (')) and focus on the situation when P and P (') are both Boolean lattices. In addition, we give asymptotically tight bounds for the number of copies of Q (n) in Q (N) and for a multicolor version of a poset Ramsey number.
引用
收藏
页码:287 / 298
页数:12
相关论文
共 23 条
[1]  
[Anonymous], 1992, Combinatorics and Partially Ordered Sets: Dimension Theory
[2]  
[Anonymous], 2000, INTRO GRAPH THEORY
[3]  
[Anonymous], 1892, J. reine angew. Math.
[4]   Multicolor Ramsey numbers for triple systems [J].
Axenovich, Maria ;
Gyarfas, Andras ;
Liu, Hong ;
Mubayi, Dhruv .
DISCRETE MATHEMATICS, 2014, 322 :69-77
[5]   QUANTITATIVE FORMS OF A THEOREM OF HILBERT [J].
BROWN, TC ;
ERDOS, P ;
CHUNG, FRK ;
GRAHAM, RL .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1985, 38 (02) :210-216
[6]   An improved bound for the stepping-up lemma [J].
Conlon, David ;
Fox, Jacob ;
Sudakov, Benny .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (09) :1191-1196
[7]   HYPERGRAPH RAMSEY NUMBERS [J].
Conlon, David ;
Fox, Jacob ;
Sudakov, Benny .
JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2010, 23 (01) :247-266
[8]   Ramsey Numbers of Sparse Hypergraphs [J].
Conlon, David ;
Fox, Jacob ;
Sudakov, Benny .
RANDOM STRUCTURES & ALGORITHMS, 2009, 35 (01) :1-14
[9]   Embeddings and Ramsey numbers of sparse κ-uniform hypergraphs [J].
Cooley, Oliver ;
Fountoulakis, Nikolaos ;
Kuehn, Daniela ;
Osthus, Deryk .
COMBINATORICA, 2009, 29 (03) :263-297
[10]   Extremal problems for sets forming Boolean algebras and complete partite hypergraphs [J].
Gunderson, DS ;
Rödl, V ;
Sidorenko, A .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1999, 88 (02) :342-367