Document Type
Lecture
Publication Date
9-13-2023
Abstract
The upper density of a set of natural numbers A is ¯ d(A) := limn→∞ |A∩{1,...,n}| n . A famous theorem of Furstenberg and S´ark¨ ozy says that if ¯ d(A) > 0, then two elements of A differ by a nonzero perfect square. In other words, if ¯ d(A) > 0, then there are a,a′ ∈ A and n ∈ N such that a−a′ = n2. To describe this phenomenon, we say S ⊂ N is density intersective if for all A ⊂ N with ¯ d(A) > 0, there exists a,a′ ∈ A such that a−a′ ∈ S. In this terminology, Furstenberg and S´ark¨ozy’s theorem says that the set of perfect squares is density intersective. Given S ⊂ N, form the Cayley graph Cay(S) with vertex set N and edge set {{n,m} : |n −m| ∈ S}. It is easy to see that if S is density intersective, then Cay(S) has infinite chromatic number, since for every finite coloring of N, one of the color classes must have positive upper density. Bergelson asked if the converse is true, and Igor Kriz gave an elaborate counterexample using Lov´ asz’s computation of the chromatic number of Kneser graphs. Motivated by the problem of determining which sets of natural numbers are density intersective, we will survey the graph theoretic aspects of Kriz’s construction and state several open problems on chromatic number and independence number of Cayley graphs on finite abelian groups.
Relational Format
presentation
Recommended Citation
Griesmer, John, "Chromatic Number and Independence Number of Cayley Graphs on Abelian Groups" (2023). Combinatorics Seminar. 18.
https://egrove.olemiss.edu/math_combinatorics/18
