Bounds for Ramsey Numbers in an Extended Scenario

Overview

Typical Ramsey theory refers to that, if all edges of a complete graph with n vertices are colored in red or blue, each edge in either color of the two, when n becomes large enough, we can certainly find a subgraph with k vertices of one color, either red or blue. The least n is called Ramsey number of k, denoted r(k). So far we are unable to find an effective way to solve r(k), we can only to narrow down its range with upper and lower bounds. In this paper I will extend the scenario of typical Ramsey problem: suppose some edges can be both red and blue at the same time, and these two-color edges are not connected to each other. I call it extended Ramsey problem. By similar method of calculation of upper and lower bounds of the typical Ramsey number, including induction and probability, the upper bound of extended Ramsey number r’(k) is 4^(k-2) and lower bound is (3/2)^((k-1)/2). Ramsey theory reveals a characteristic of mathematics, i.e. order comes to the fore from chaos, it is a core subject in the mathematical field of random structure and algorithms. Conclusions in this paper helps to find the optimal solution as how to assign tasks and allocate resources efficiently under certain conditions.

Competition history

• ISEF 2024 Mathematics · Entry MATH019 · Los Angeles, California, United States

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.