Large cliques and independent sets all over the place
Large cliques and independent sets all over the place
复制标题
到处都是大派系和独立派
DOI：
10.1090/proc/15323
复制
发表时间：
2021
影响因子：
1
通讯作者：
Sudakov, Benny
中科院分区：
文献类型：
--
作者：
Alon, Noga;Bucić, Matija;Sudakov, Benny
我们研究了 Erdős 和 Hajnal 在 90 年代初提出的以下问题。在全顶点图上，任何顶点同时包含团和独立大小集的最小可能值是多少？我们构建的示例表明，与来自自然猜测（随机图）的上限相比，最多获得两倍的次多项式改进。我们的（概率）构造产生了拉姆齐图的新示例，虽然没有非常大的同质子集，但在任何小的顶点子集中都包含派系和独立的大小集。在随机图中，这与事实相去甚远。我们的证明基于字典产品和使用随机性之间的相互作用。参考
We study the following question raised by Erdős and Hajnal in the early 90’s. Over all-vertex graphswhat is the smallest possible value offor which anyvertices ofcontain both a clique and an independent set of size? We construct examples showing thatis at mostobtaining a twofold sub-polynomial improvement over the upper bound of aboutcoming from the natural guess, the random graph. Our (probabilistic) construction gives rise to new examples of Ramsey graphs, which while having no very large homogenous subsets contain both cliques and independent sets of sizein any small subset of vertices. This is very far from being true in random graphs. Our proofs are based on an interplay between taking lexicographic products and using randomness. References
登录
查看更多内容
Darstellbarkeit von Zahlen durchquadratische Formen in einem beliebigen algebraischen Zahlkörper。
DOI：
10.1515/crll.1924.153.113
发表时间：
2017
期刊：
Journal für die reine und angewandte Mathematik (Crelles Journal)
影响因子：
--
作者：
H. Hasse
通讯作者：
H. Hasse
Ramsey 图的导出子图猜想的证明
影响因子：
1.3
作者：
Matthew Kwan;B. Sudakov
通讯作者：
B. Sudakov
用于多对数熵和改进拉姆齐图的双源分散器
DOI：
10.1145/2897518.2897530
发表时间：
2015
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Gil Cohen
通讯作者：
Gil Cohen
关于拉姆齐型定理
影响因子：
0.8
作者：
P. Erdos;A. Szemerédi
通讯作者：
A. Szemerédi
考虑局部因素的大型独立集
影响因子：
1.1
作者：
M. Buci'c;B. Sudakov
通讯作者：
B. Sudakov