| | |
| | |
Stat |
Members: 3658 Articles: 2'599'751 Articles rated: 2609
02 November 2024 |
|
| | | |
|
Article overview
| |
|
Clique number of random Cayley graph | Gyan Prakash
; | Date: |
1 Nov 2007 | Abstract: | Let G be a finite abelian group of order n. For any subset B of G with B=-B,
the Cayley graph G_B is a graph on vertex set G in which two elements i and j
of G are connected by an edge if and only if the element i-j belongs to the set
B. It was shown by Ben Green that when G is a vector space over a finite field
Z/pZ, then there is a Cayley graph containing neither a complete subgraph nor
an independent set of size more than $clog nloglog n,$ where $c>0$ is an
absolute constant. In this article we observe that a modification of his
arguments show that for an arbitrary finite abelian group, there is a Cayley
graph containing neither a complete subgraph nor an independent set of size
more than $c(omega^3(n)log omega(n) +loglog n)$, where $c>0$ is an
absolute constant and $omega(n)$ denotes the number of distinct prime divisors
of $n$. | Source: | arXiv, 0711.0081 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|