Welcome to Workshop on Applied Mathematics and Graph Theory
The Workshop on Applied Mathematics and Graph Theory brings together researchers, academics, and practitioners to discuss recent advances in applied mathematics, graph theory, combinatorics, network science, and related fields. Held annually in Ohrid during August.
Call for Papers
Find information about paper submission guidelines, important dates, and topics of interest for the workshop. This section provides everything you need to know to submit your research for presentation.
Classical Result in Graph Theory
Ramsey's Theorem
Ramsey’s Theorem
Finite Version (Ramsey’s Theorem for Graphs)
For any integers $r, s \ge 2$, there exists an integer $R(r, s)$ such that any graph on at least $R(r, s)$ vertices contains either a clique of size $r$ or an independent set of size $s$.
Example
$R(3, 3) = 6$: In any party of six people, there are either three mutual acquaintances or three mutual strangers.
Infinite Version
Let $X$ be an infinite set. For any coloring of the $k$-element subsets of $X$ with finitely many colors, there exists an infinite subset $Y \subseteq X$ all of whose $k$-element subsets have the same color.
Known Ramsey Numbers
- $R(3, 3) = 6$
- $R(3, 4) = 9$
- $R(3, 5) = 14$
- $R(4, 4) = 18$
- $R(5, 5)$ is unknown (between 43 and 48)
Proof Ideas
The finite version is proved by induction on $r + s$, using the inequality
$$R(r, s) \le R(r-1, s) + R(r, s-1)$$Applications
- Combinatorics and extremal graph theory
- Logic and model theory
- Computer science (lower bounds)
- Number theory (Van der Waerden’s theorem)
Philosophical Interpretation
“Complete disorder is impossible” – any sufficiently large system contains ordered substructures.