Fourier Analysis on Finite Groups and the Lovász ϑ-Number of Cayley Graphs

Abstract

We apply Fourier analysis on finite groups to obtain simplified formulations for the Lovász ϑ-number of a Cayley graph. We put these formulations to use by checking a few cases of a conjecture of Ellis, Friedgut, and Pilpel made in a recent article proving a version of the Erdös–Ko–Rado theorem for k-intersecting families of permutations. We also introduce a q-analogue of the notion of k-intersecting families of permutations, and we verify a few cases of the corresponding Erdös–Ko–Rado assertion by computer.

2000 AMS Subject Classification::

• 05C50
• 20C30
• 43A35
• 90C22

Keywords:

• Lovász theta number
• Cayley graphs of finite groups
• independent sets
• Erdös–Ko–Rado theorems
• intersecting families of permutations (and their q-analogue)
• finite Fourier analysis

Notes

¹Available at http://cgm.cs.mcgill.ca/avis/C/lrs.html.

²The Magma program that generates the linear programs can be downloaded from the third author’s website http://www.mi.uni- koeln.de/opt/frank-vallentin/programs/.

³Available at http://www.gurobi.com.

⁴M. Dutour Sikirić, private communication, 2013.