组合数学
数学
离散数学
集团
学位(音乐)
对数
拉姆齐定理
图形
集团总额
元组
弦图
1-平面图
声学
物理
数学分析
作者
Anurag Bishnoi,Simona Boyadzhiyska,Dennis Clemens,Pranshu Gupta,Thomas Lesgourgues,Anita Liebenau
摘要
A graph is said to be -Ramsey for a -tuple of graphs , denoted by , if every -edge-coloring of contains a monochromatic copy of in color for some . Let denote the smallest minimum degree of over all graphs that are minimal -Ramsey for (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erdős, and Lovász, who determined its value precisely for a pair of cliques. Over the past two decades the parameter has been studied by several groups of authors, their main focus being on the symmetric case, where for all . The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles, and trees. We determine when is a pair of one clique and one tree, a pair of one clique and one cycle, and a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on in terms of the size of the cliques , the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed.
科研通智能强力驱动
Strongly Powered by AbleSci AI