Login | Register

Independent sets in graph products via harmonic analysis


Independent sets in graph products via harmonic analysis

Ghandehari, Mahya (2005) Independent sets in graph products via harmonic analysis. Masters thesis, Concordia University.

Text (application/pdf)
MR10211.pdf - Accepted Version


In this thesis we study the independent sets of Knr , the weak product of n complete graphs on r vertices, which are close to be of maximum size. We review the previously known results. For constant r and arbitrary n, it was known that every such independent set is close to some independent set of maximum size. We prove that this statement holds for arbitrary r and n. The proof involves some techniques from Fourier analysis of Boolean functions on Znr . In fact we show that when most of the 2-norm weight of the Fourier expansion of a Boolean function on Znr is concentrated on the first two levels, then the function can be approximated by a Boolean function that depends only on one coordinate. A stronger analogue of this has been proven by Jean Bourgain for Zn2 . We present an expanded version of his proof in this thesis.

Divisions:Concordia University > Faculty of Arts and Science > Mathematics and Statistics
Item Type:Thesis (Masters)
Authors:Ghandehari, Mahya
Pagination:v, 57 leaves ; 29 cm.
Institution:Concordia University
Degree Name:M. Sc.
Thesis Supervisor(s):Larose, Benoit
ID Code:8540
Deposited By: Concordia University Library
Deposited On:18 Aug 2011 18:28
Last Modified:18 Jan 2018 17:33
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top