Discrete mathematics and graph theory · Maths EE idea · Solid

Ramsey numbers: order in any party

A research question to start from

Why does any party of six people contain three mutual friends or three mutual strangers, and what is known about larger Ramsey numbers?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

A proof you can explain completely, then bounds that show why the problem gets hard.

Mathematics you would need

Graph colourings
Pigeonhole principle
Upper bounds by induction
Constructions for lower bounds

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Prove R(3,3) = 6, including a colouring of 5 vertices.
Prove the general upper bound.
Discuss R(4,4) and why exact values are hard.

Scope and difficulty

Solid. Solid.

Pitfalls

Quoting values without proofs.
Too much on unsolved cases.

Where to start reading

Search a library catalogue or a university's open lecture notes for: Ramsey number R(3,3) proof; Ramsey upper bound induction. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.