百科问答小站 logo
百科问答小站 font logo



如何估计Ramsey数的上界? 第1页

  

user avatar   RealFiddie 网友的相关建议: 
      
命题:

证明:根据Ramsey数的定义,只需要证明:

阶完全图用 种颜色染完之后,总存在同色三角形.

用数学归纳法进行证明. 当 时, 结论成立.

假设结论对 的情形成立,即

下证结论对 的情形成立.

设 为 阶完全图, 用 种颜色对 的边染色, 连接顶点 的边的条数是

所以

由抽屉原理, 有至少 条由 连出的边同色, 比如叫红色.

由红边连接 的那些点导出的完全子图记为 , 则 .

如果 中不含红边, 由归纳假设, 中必有同色三角形.

如果 中含红边 , 则可以得到红色三角形 . 因此 必有同色三角形.


很久没看组合数学了,不保证上面证明过程正确.




  

相关话题

  等比数列的任意连续三项的中间一项都是另外两项的等比中项吗? 
  包含所有各项不大于n的n元正整数列且长度最小的序列有多少个? 
  如何证明子集族上界? 
  竞赛组合题的成绩可以通过训练得到显著提高吗? 
  如何证明子集族上界? 
  n 座桥,连通 n+1 个岛,有多少种连法? 
  如何证明以下式子? 
  不用计算机程序,如何求1,2,…,n中所有与n互素的数的平方和? 
  如何用组合数学证明 (n²)! 能被 (n!)^(n+1) 整除? 
  能否求出n次对称群中置换的最大阶? 

前一个讨论
如何评价2021年第37届全国中学生数学竞赛决赛(CMO)?
下一个讨论
如何求解这个偏序集的问题?





© 2025-06-06 - tinynew.org. All Rights Reserved.
© 2025-06-06 - tinynew.org. 保留所有权利