Open Collections

Ramsey theory, Discrepancy Theory, Zero-Sums and Symmetric Functions

Banff International Research Station for Mathematical Innovation and Discovery

The underlying philosophy of Ramsey Theory is that total disorder is impossible, and the underlying philosophy of Discrepancy Theory is that a totally equal distribution is impossible. In both theories we mainly try to find extremal configurations that satisfy some property or at least their magnitude. It is convenient to express these configurations as colored objects. Both theories can be extended from using colors to the use of vanishing (or almost vanishing) linear sums in several variables. Theorems in Ramsey Theory can be generalized using the ErdÅ s Ginzburg Ziv theorem, by replacing a {0,1}-coloring by a coloring which uses the residues modulo a positive integer assuring a modular zero-sum. In Discrepancy Theory, many combinatorial problems can be expressed by a {-1,1}-coloring and the discrepancy from a uniform distribution is expressed as the deviation from zero. In the lecture we will discuss from a personal perspective, several Ramsey-type theorems and Discrepancy theorems in order to demonstrate the breadth of the subjects. Next we will survey recent developments of the EGZ theorem and other developments relating to integer-coloring. Finally, we will show how these developments relate to Ramsey Theory and Discrepancy Theory. The linear sums mentioned above can be generalized to symmetric polynomials. This suggests new avenues of research and many more problems.

Mathematics; Combinatorics; Number theory; Discrete mathematics

video/mp4

Author affiliation: University of Idaho

2020-05-10

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/74383

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/