Hypercube graph

Let Q_n be the hypercube graph.

  • Q_1 = K_2 (the complete graph with two vertices),
  • Q_2 = C_4 (the square), and
  • Q_n is constructed taking two copies of Q_{n-1} and adding an edge that connects each vertex of the first copy with the corresponding vertex of the second copy.

Easy: Find \chi(Q_n) (chromatic number) for every n.

Harder: Find every n such that Q_n is planar.

 

Advertisements
Hypercube graph

A generalization of Schur’s lemma

(Dixmier) Let A be a \Bbb{C}-algebra (in fact, any uncountable algebraically closed field will do) and V be a simple A-module having a countable basis as a \Bbb{C}-vector space. Then D=\mathrm{End}_A(V)\simeq \Bbb{C}.

Brief outline:

  1. By Schur’s lemma, D is a division algebra. Moreover, it has a countable basis.
  2. Suppose \varphi\in D does not act as a scalar. Then \varphi is trascendental over \Bbb{C}.
  3. This is absurd since it would imply \Bbb{C}(\varphi)\subseteq D has uncountable dimension.
A generalization of Schur’s lemma

One too many

Consider a permutation \sigma of mn+1 letters written in one line notation, say \sigma = a_1\ldots a_{mn+1}. An increasing subsequence of \sigma is a choice of integers i_1 <\cdots < i_k such that a_{i_1}< \cdots < a_{i_k}, a decreasing subsequence is defined analogously. Show that any permutation in mn+1 letters has either an increasing subsequence of length n+1 or a decreasing subsequence of length m+1. Is the bound optimal?

One too many