Paley graph - Revision history

Vipul: /* Other numerical invariants */

2012-05-29T21:49:53Z

Other numerical invariants

← Older revision		Revision as of 21:49, 29 May 2012
Line 43:		Line 43:
	\| [[independence number]] \|\| same as clique number \|\| The two numbers are equal because the Paley graph is a [[self-complementary graph]] and [[independence number equals clique number of complement]]		\| [[independence number]] \|\| same as clique number \|\| The two numbers are equal because the Paley graph is a [[self-complementary graph]] and [[independence number equals clique number of complement]]
	\|-		\|-
	\| [[chromatic number]] \|\| {{fillin}} \|\| {~~{fillin}~~}		\| [[chromatic number]] \|\| {{fillin}} \|\| Precise formula unclear, but the fact that [[self-complementary graph implies chromatic number is at least equal to square root of size of vertex set]] puts a lower bound, namely the smallest integer greater than or equal to <math>\sqrt{q}</math>.
	\|-		\|-
	\| {{arithmetic function value\|radius of a graph\|2}} \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.		\| {{arithmetic function value\|radius of a graph\|2}} \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.

Vipul: /* Definition */

2012-05-29T21:48:07Z

Definition

← Older revision		Revision as of 21:48, 29 May 2012
Line 1:		Line 1:
	==Definition==		==Definition==

	Suppose <math>q</math> is a [[prime power]] such that <math>q \equiv 1 \pmod 4</math>. The '''Paley graph''' on <math>q</math> vertices is defined as follows:		Suppose <math>q</math> is a [[prime power]] such that <math>q \equiv 1 \pmod 4</math>. The '''Paley graph''' on <math>q</math> vertices, denoted <math>P_q</math> or <math>QR(q)</math>, is defined as follows:

	# The vertex set is identified with the elements of the field <math>\mathbb{F}_q</math> of <math>q</matH> elements. This field is unique up to field isomorphism.		# The vertex set is identified with the elements of the field <math>\mathbb{F}_q</math> of <math>q</matH> elements. This field is unique up to field isomorphism.

Vipul: /* Other numerical invariants */

2012-05-28T18:30:39Z

Other numerical invariants

← Older revision		Revision as of 18:30, 28 May 2012
Line 51:		Line 51:
	\| {{arithmetic function value\|girth of a graph\|3}} (except the case of <math>P_5</math>) \|\| The girth of <math>P_5</math> is 5. Note that for ''all'' higher <math>q</math>, the girth of the graph is 3, due to the fact that there are <math>(q - 5)/4</math> pairs of nonzero quadratic residues that differ by 1, and this number is positive whenever <matH>q > 5</math>.		\| {{arithmetic function value\|girth of a graph\|3}} (except the case of <math>P_5</math>) \|\| The girth of <math>P_5</math> is 5. Note that for ''all'' higher <math>q</math>, the girth of the graph is 3, due to the fact that there are <math>(q - 5)/4</math> pairs of nonzero quadratic residues that differ by 1, and this number is positive whenever <matH>q > 5</math>.
	\|-		\|-
	\| [[circuit rank]] \|\| <math>q(q -5)/4 + 1</math> \|\| The circuit rank is number of edges - number of vertices + number of connected components. This becomes <matH>q(q-1)/4 - q + 1</math> which simplifies to <matH>q(q - 5)/4 + 1</math>.		\| [[circuit rank]] \|\| <math>q(q -5)/4 + 1</math> <math>= (q - 1)(q -4)/4</math> \|\| The circuit rank is number of edges - number of vertices + number of connected components. This becomes <matH>q(q-1)/4 - q + 1</math> which simplifies to <matH>q(q - 5)/4 + 1</math>.
	\|}		\|}

Vipul at 18:30, 28 May 2012

2012-05-28T18:30:11Z

← Older revision		Revision as of 18:30, 28 May 2012
Line 9:		Line 9:

	For a prime power <math>q \equiv 3 \pmod 4</math>, we can consider instead the [[Paley digraph]].		For a prime power <math>q \equiv 3 \pmod 4</math>, we can consider instead the [[Paley digraph]].

			==Arithmetic functions==

			===Size measures===

			{\| class="sortable" border="1"
			! Function !! Value !! Explanation
			\|-
			\| [[size of vertex set]] \|\| <math>q</math> \|\| By definition, the vertex set is the underlying set of a field of size <math>q</math>
			\|-
			\| [[size of edge set]] \|\| <math>q(q - 1)/4</math> \|\| The number of quadratic residues is <matH>(q - 1)/2</math>, hence this is the degree of each vertex. We now use the [[handshaking lemma]].
			\|}

			===Numerical invariants associated with vertices===

			Since the graph is a [[vertex-transitive graph]], any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:

			{\| class="sortable" border="1"
			! Function !! Value !! Explanation
			\|-
			\| [[degree of a vertex]] \|\| <matH>(q - 1)/2</math> \|\| This equals the number of quadratic residues in <math>\mathbb{F}_q^\ast</math>, which is the size of the image of the square map <matH>x \mapsto x^2</math>, whose domain has size <math>q - 1</math> and kernel has size 2. The image thus has size <matH>(q - 1)/2</math>. Note that we are using that <matH>q</math> is odd.
			\|-
			\| [[eccentricity of a vertex]] \|\| 2 \|\| Follows from [[groupprops:every element of a finite field is expressible as a sum of two squares\|every element of a finite field is expressible as a sum of two squares]]
			\|}

			===Other numerical invariants===

			{\| class="sortable" border="1"
			! Function !! Value !! Explanation
			\|-
			\| [[clique number]] \|\| no easy formula, but generally grows with <math>q</math> \|\| Note that <matH>q = 5</math> is the only case where the clique number is 2; for <matH>q \ge 9</math>, the clique number is at least 3 because of the presence of adjacent quadratic residues -- the number of adjacent quadratic residues is <matH>(q - 5)/4</math>. <math>q = 17</math> is the largest value for which the clique number is 3. By Ramsey theory, we know that if <matH>q \ge R(m,m)</math>, then the clique number is at least <math>m</math>.
			\|-
			\| [[independence number]] \|\| same as clique number \|\| The two numbers are equal because the Paley graph is a [[self-complementary graph]] and [[independence number equals clique number of complement]]
			\|-
			\| [[chromatic number]] \|\| {{fillin}} \|\| {{fillin}}
			\|-
			\| {{arithmetic function value\|radius of a graph\|2}} \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
			\|-
			\| {{arithmetic function value\|diameter of a graph\|2}} \|\| Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
			\|-
			\| {{arithmetic function value\|girth of a graph\|3}} (except the case of <math>P_5</math>) \|\| The girth of <math>P_5</math> is 5. Note that for ''all'' higher <math>q</math>, the girth of the graph is 3, due to the fact that there are <math>(q - 5)/4</math> pairs of nonzero quadratic residues that differ by 1, and this number is positive whenever <matH>q > 5</math>.
			\|-
			\| [[circuit rank]] \|\| <math>q(q -5)/4 + 1</math> \|\| The circuit rank is number of edges - number of vertices + number of connected components. This becomes <matH>q(q-1)/4 - q + 1</math> which simplifies to <matH>q(q - 5)/4 + 1</math>.
			\|}

Vipul at 03:34, 28 May 2012

2012-05-28T03:34:01Z

← Older revision		Revision as of 03:34, 28 May 2012
Line 7:		Line 7:

	The significance of <math>q \equiv 1\pmod 4</math> is that this forces -1 to be a square, hence <math>a - b</math> is a square if and only if <math>b - a</math> is a square. This is necessary because we want the definition of adjacency to be symmetric in the two vertices.		The significance of <math>q \equiv 1\pmod 4</math> is that this forces -1 to be a square, hence <math>a - b</math> is a square if and only if <math>b - a</math> is a square. This is necessary because we want the definition of adjacency to be symmetric in the two vertices.

			For a prime power <math>q \equiv 3 \pmod 4</math>, we can consider instead the [[Paley digraph]].

Vipul: Created page with "==Definition== Suppose $q$ is a prime power such that $q \equiv 1 \pmod 4$ . The '''Paley graph''' on $q$ vertices is defined as follows: ..."

2012-05-28T03:31:49Z

Created page with "==Definition== Suppose <math>q</math> is a prime power such that <math>q \equiv 1 \pmod 4</math>. The '''Paley graph''' on <math>q</math> vertices is defined as follows: ..."

New page

==Definition==

Suppose <math>q</math> is a [[prime power]] such that <math>q \equiv 1 \pmod 4</math>. The '''Paley graph''' on <math>q</math> vertices is defined as follows:

# The vertex set is identified with the elements of the field <math>\mathbb{F}_q</math> of <math>q</matH> elements. This field is unique up to field isomorphism.
# Given any two distinct vertices <math>a,b \in \mathbb{F}_q</math>, <math>a</matH> and <math>b</math> are defined to be adjacent if and only if <math>a -b</math> is a square in <math>\mathbb{F}_q^*</math>.

The significance of <math>q \equiv 1\pmod 4</math> is that this forces -1 to be a square, hence <math>a - b</math> is a square if and only if <math>b - a</math> is a square. This is necessary because we want the definition of adjacency to be symmetric in the two vertices.

Paley graph - Revision history

Vipul: /* Other numerical invariants */

Vipul: /* Definition */

Vipul: /* Other numerical invariants */

Vipul at 18:30, 28 May 2012

Vipul at 03:34, 28 May 2012

Vipul: Created page with "==Definition== Suppose q is a prime power such that q \equiv 1 \pmod 4. The '''Paley graph''' on q vertices is defined as follows: ..."

Vipul: Created page with "==Definition== Suppose $q$ is a prime power such that $q \equiv 1 \pmod 4$ . The '''Paley graph''' on $q$ vertices is defined as follows: ..."