Breadcrumb

 
 

Independent sets in graph products via harmonic analysis

Title:

Independent sets in graph products via harmonic analysis

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

[img]
Preview
PDF - Accepted Version
1634Kb

Abstract

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.
Program:Mathematics and Statistics
Date:2005
Thesis Supervisor(s):Larose, Benoit
ID Code:8540
Deposited By:Concordia University Libraries
Deposited On:18 Aug 2011 14:28
Last Modified:18 Aug 2011 14:28
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

Document Downloads

More statistics for this item...

Concordia University - Footer