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



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

  

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

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

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

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

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

下证结论对 的情形成立.

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

所以

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

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

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

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


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




  

相关话题

  这道排列组合该如何思考? 
  已知映射f:N→N(其中N是正整数集),问以下三条是否可以相容? 
  母函数都是用幂级数吗?三角级数可以构造母函数吗? 
  博弈论+图论,博士有哪些方向可以选择? 
  如何证明以下的这个组合恒等式? 
  在一个球内任取n个点,则这n个点落在同一个半球内的概率是多少? 
  如何解决这个图的特征值问题? 
  博弈论+图论,博士有哪些方向可以选择? 
  【组合数学】这个魔术有什么策略吗? 
  如何证明这个与树有关的递推式? 

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





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