Kneser graph - Revision history

Vipul: /* Other numerical invariants */

2012-05-29T22:11:24Z

Other numerical invariants

← Older revision		Revision as of 22:11, 29 May 2012
Line 81:		Line 81:
	\| [[independence number]] \|\| {{fillin}} \|\|		\| [[independence number]] \|\| {{fillin}} \|\|
	\|-		\|-
	\| [[chromatic number]] \|\| ~~{{fillin}}~~ \|\|		\| [[chromatic number]] \|\| <math>n - 2k + 2</math> if <math>k \le n/2</math><br>1 otherwise \|\|
	\|-		\|-
	\| [[radius of a graph]] \|\| <math>1 + \left\lceil\frac{k - 1}{n - 2k}\right\rceil</math> where <math>\lceil \rceil</math> denotes the ceiling function: the smallest integer greater than or equal to a given number \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.		\| [[radius of a graph]] \|\| <math>1 + \left\lceil\frac{k - 1}{n - 2k}\right\rceil</math> where <math>\lceil \rceil</math> denotes the ceiling function: the smallest integer greater than or equal to a given number \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.

Vipul: /* Arithmetic functions */

2012-05-29T22:09:45Z

Arithmetic functions

← Older revision		Revision as of 22:09, 29 May 2012
Line 67:		Line 67:
	\| [[degree of a vertex]] \|\| <math>\binom{n - k}{k}</math> \|\| We need to determine, for a given <math>k</math>-element subset, the number of <math>k</math>-element subsets disjoint from it. This is the same as the number of <math>k</math>-element subsets of its set-theoretic complement, which has size <math>n - k</math>.		\| [[degree of a vertex]] \|\| <math>\binom{n - k}{k}</math> \|\| We need to determine, for a given <math>k</math>-element subset, the number of <math>k</math>-element subsets disjoint from it. This is the same as the number of <math>k</math>-element subsets of its set-theoretic complement, which has size <math>n - k</math>.
	\|-		\|-
	\| [[eccentricity of a vertex]] \|\| <math>1 + \~~operatorname{ceiling}~~\~~left(~~\frac{k - 1}{n - 2k}\right)</math> where ~~ceiling~~ denotes the ceiling function: the smallest integer greater than or equal to a given number \|\|		\| [[eccentricity of a vertex]] \|\| <math>1 + \left\lceil\frac{k - 1}{n - 2k}\right\rceil</math> where <math>\lceil \rceil</math> denotes the ceiling function: the smallest integer greater than or equal to a given number \|\|
	\|}		\|}

Vipul: /* Other numerical invariants */

2012-05-29T22:09:20Z

Other numerical invariants

← Older revision		Revision as of 22:09, 29 May 2012
Line 77:		Line 77:
	! Function !! Value !! Explanation		! Function !! Value !! Explanation
	\|-		\|-
	\| [[clique number]] \|\| <math>\~~operatorname~~{~~floor~~}~~(n/~~k)</math> where ~~floor~~ is the floor function (the greatest integer function) that returns the largest integer less than or equal to the number \|\| For a subset of the vertex set to form a clique, the elements of the subset must be disjoint as subsets of the <math>n</math>-element set. If there are <math>r</math> such subsets, they have a total of <math>kr</math> elements, forcing <math>kr \le n</math>, giving the upper bound. It's also easy to see that this upper bound is achieved.		\| [[clique number]] \|\| <math>\left\lfloor\frac{n}{k}\right\rfloor</math> where <math>\lfloor \rfloor</math> is the floor function (the greatest integer function) that returns the largest integer less than or equal to the number \|\| For a subset of the vertex set to form a clique, the elements of the subset must be disjoint as subsets of the <math>n</math>-element set. If there are <math>r</math> such subsets, they have a total of <math>kr</math> elements, forcing <math>kr \le n</math>, giving the upper bound. It's also easy to see that this upper bound is achieved.
	\|-		\|-
	\| [[independence number]] \|\| {{fillin}} \|\|		\| [[independence number]] \|\| {{fillin}} \|\|
Line 83:		Line 83:
	\| [[chromatic number]] \|\| {{fillin}} \|\|		\| [[chromatic number]] \|\| {{fillin}} \|\|
	\|-		\|-
	\| [[radius of a graph]] \|\| <math>1 + \~~operatorname{ceiling}~~\~~left(~~\frac{k - 1}{n - 2k}\right)</math> where ~~ceiling~~ denotes the ceiling function: the smallest integer greater than or equal to a given number \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.		\| [[radius of a graph]] \|\| <math>1 + \left\lceil\frac{k - 1}{n - 2k}\right\rceil</math> where <math>\lceil \rceil</math> denotes the ceiling function: the smallest integer greater than or equal to a given number \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
	\|-		\|-
	\| [[diameter of a graph]] \|\| <math>1 + \~~operatorname{ceiling}~~\~~left(~~\frac{k - 1}{n - 2k}\right)</math> where ~~ceiling~~ denotes the ceiling function: the smallest integer greater than or equal to a given number \|\| Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.		\| [[diameter of a graph]] \|\| <math>1 + \left\lceil\frac{k - 1}{n - 2k}\right\rceil</math> where <math>\lceil \rceil</math> denotes the ceiling function: the smallest integer greater than or equal to a given number\|\| Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
	\|-		\|-
	\| [[odd girth]] \|\| <math>1 + 2\~~operatorname{ceiling}~~\~~left(~~\frac{k}{n - 2k}\right)</math> where ~~ceiling~~ denotes the ceiling function: the smallest integer greater than or equal to a given number \|\|		\| [[odd girth]] \|\| <math>1 + 2\left\lceil\frac{k}{n - 2k}\right \rceil</math> where <math>\lceil \rceil</math> denotes the ceiling function: the smallest integer greater than or equal to a given number \|\|
	\|-		\|-
	\| [[even girth]] \|\| 6 if <math>n = 2k + 1</math><br>4 if <math>n \ge 2k + 2</math> \|\|		\| [[even girth]] \|\| 6 if <math>n = 2k + 1</math><br>4 if <math>n \ge 2k + 2</math> \|\|
	\|}		\|}

Vipul: /* Arithmetic functions */

2012-05-29T02:42:28Z

Arithmetic functions

← Older revision		Revision as of 02:42, 29 May 2012
Line 58:		Line 58:
	===Numerical invariants associated with vertices===		===Numerical invariants associated with vertices===

	We restrict attention to the case that <math>1 < k < n/2</math> for the expressions below.		We restrict attention to the case that <math>1 \le k < n/2</math> for the expressions below.

	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:		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:
Line 72:		Line 72:
	===Other numerical invariants===		===Other numerical invariants===

	We restrict attention to the case <math>1 < k < n/2</math> for all the formulas below, though some of the formulas are also more generally valid.		We restrict attention to the case <math>1 \le k < n/2</math> for all the formulas below, though some of the formulas are also more generally valid.

	{\| class="sortable" border="1"		{\| class="sortable" border="1"

Vipul: /* Particular cases */

2012-05-29T02:41:56Z

Particular cases

← Older revision		Revision as of 02:41, 29 May 2012
Line 39:		Line 39:
	\| 6 \|\| 2 \|\| {{fillin}}		\| 6 \|\| 2 \|\| {{fillin}}
	\|}		\|}

			===Odd graph case===

			A particular case of Kneser graphs of interest is where <math>n = 2k + 1</math>. This gives a one-parameter family of graphs called [[odd graph]]s. Specifically, the odd graph <math>O_m</math> is defined as the Kneser graph with <math>n = 2m - 1</math> and <math>k = m - 1</math>.

	==Arithmetic functions==		==Arithmetic functions==

Vipul: /* Numerical invariants associated with vertices */

2012-05-29T02:33:13Z

Numerical invariants associated with vertices

@@ Line 63: / Line 63: @@
 | [[degree of a vertex]] || <math>\binom{n - k}{k}</math> || We need to determine, for a given <math>k</math>-element subset, the number of <math>k</math>-element subsets disjoint from it. This is the same as the number of <math>k</math>-element subsets of its set-theoretic complement, which has size <math>n - k</math>.
 |-
-| [[eccentricity of a vertex]] || If <math>k \le n/3</math>, it is 2<br>In general, it is something like twice the smallest integer greater than or equal to <math>k/(2(n - 2k))</math>. ||
+| [[eccentricity of a vertex]] || <math>1 + \operatorname{ceiling}\left(\frac{k - 1}{n - 2k}\right)</math> where ceiling denotes the ceiling function: the smallest integer greater than or equal to a given number ||
 |}

Vipul: /* Numerical invariants associated with vertices */

2012-05-28T19:08:26Z

Numerical invariants associated with vertices

← Older revision		Revision as of 19:08, 28 May 2012
Line 63:		Line 63:
	\| [[degree of a vertex]] \|\| <math>\binom{n - k}{k}</math> \|\| We need to determine, for a given <math>k</math>-element subset, the number of <math>k</math>-element subsets disjoint from it. This is the same as the number of <math>k</math>-element subsets of its set-theoretic complement, which has size <math>n - k</math>.		\| [[degree of a vertex]] \|\| <math>\binom{n - k}{k}</math> \|\| We need to determine, for a given <math>k</math>-element subset, the number of <math>k</math>-element subsets disjoint from it. This is the same as the number of <math>k</math>-element subsets of its set-theoretic complement, which has size <math>n - k</math>.
	\|-		\|-
	\| [[eccentricity of a vertex]] \|\| If <math>k \le n/3</math>, it is 2<br>In general, it is something like twice the smallest integer greater than or equal to <math>k/(2(n - 2k))</math>.		\| [[eccentricity of a vertex]] \|\| If <math>k \le n/3</math>, it is 2<br>In general, it is something like twice the smallest integer greater than or equal to <math>k/(2(n - 2k))</math>. \|\|
	\|}		\|}

Vipul: /* Other numerical invariants */

2012-05-28T19:08:13Z

Other numerical invariants

@@ Line 64: / Line 64: @@
 |-
 | [[eccentricity of a vertex]] || If <math>k \le n/3</math>, it is 2<br>In general, it is something like twice the smallest integer greater than or equal to <math>k/(2(n - 2k))</math>.
 |}

Vipul at 19:07, 28 May 2012

2012-05-28T19:07:57Z

@@ Line 38: / Line 38: @@
 |-
 | 6 || 2 || {{fillin}}
 |}

Vipul at 18:58, 28 May 2012

2012-05-28T18:58:21Z

@@ Line 7: / Line 7: @@
 ==Particular cases==
 {| class="sortable" border="1"
@@ Line 24: / Line 26: @@
 |-
 | <math>k = 0</math> || [[one-point graph]]
 |}