Archive for the ‘Uncategorized’ Category

Re: Schonhardt polyhedron, IMS-2013/4 program, etc…

28 November, 2013

The program announced at this post is finally happening, here is
the official schedule etc.

Two of my graduate students at NTU, Svetlana Obraztsova and Nick Gravin, received their PhDs in the past 12 months.

And, on a personal note, there is Jacob Victor, a.k.a. Yasha, born in August 2012 🙂


An email from Sendai (Tohoku University)

13 March, 2011

I was very glad today to receive an email from Akihiro Munemasa (from Tohoku university at Sendai), my long-term collaborator and friend. He says he’s OK, but has no electricity/water/gas…

And, as we see, they have internet, at least some kind of service (email went via, a web-mail service run by Apple).

Well, I can only wish a lot of strength to Akihiro, and all the people affected by this disaster!

PS: today (14th March) he also sent me photos of his office:
photo of the office

2010 in review – Happy New Year!

2 January, 2011

While it might be snowing on this page, Edith picked up a mango fallen from a tree outside our block of flats this afternoon…

The stats helper monkeys at mulled over how this blog did in 2010, and here’s a high level summary of its overall blog health:

Healthy blog!

The Blog-Health-o-Meter™ reads Fresher than ever.

Crunchy numbers

Featured image

A helper monkey made this abstract painting, inspired by your stats.

A Boeing 747-400 passenger jet can hold 416 passengers. This blog was viewed about 5,700 times in 2010. That’s about 14 full 747s.

In 2010, there were 6 new posts, growing the total archive of this blog to 33 posts. There were 5 pictures uploaded, taking up a total of 28kb.

The busiest day of the year was May 11th with 79 views. The most popular post that day was Is C++ the worst 1st programming language for maths majors?.

Where did they come from?

The top referring sites in 2010 were,,,, and

Some visitors came searching, mostly for funny pictures, funny, confused cat, total unimodularity, and funny pics.

Attractions in 2010

These are the posts and pages that got the most views in 2010.


Is C++ the worst 1st programming language for maths majors? May 2010


Total unimodularity and networks October 2009
1 comment


Cosets and normal subgroups March 2009


Bipartite matchings via linear programming September 2009
1 comment


Bellman-Ford algorithm for shortest paths and potentials September 2009

a subgeometry of D_3-dual polar space

29 May, 2009

In 1991 I provided to Andries Brouwer more examples of distance-regular graphs that were not known at the time the book “Distance-regular graphs” by Andries, A.M.Cohen, and A.Neumaier, that he included into “Additions and corrections”. Recently I was asked for more details on these. So I started to recall what that was all about (I drifted quite far from that area of research since then, I must say)…

D3-dual polar space is a bipartite graph \Gamma=(V,E) that satisfies the following properties:

  • each 2-path lies in a unique complete bipartite subgraph Q with parts of size \geq 3;
  • for any vertex v\in V the edges (v,u)\in E and the subgraphs Q\ni v form a projective plane \Pi_v, with respect to inclusion.

So from the point of view of Tits’ “local” approach to buildings we talk about a “geometry with diagram” \circ==\circ--\circ, where \circ==\circ stands for a generalised 4-gon (and indeed complete bipartite graph is a trivial example of such a thing), and \circ--\circ stands for a generalised 3-gon, i.e., a projective plane.

To construct a typical example, let us consider the case of the projective planes \Pi_v being of order q=3. Then we have a distance-regular graph of diameter 3, with distribution diagram around a vertex as follows:
So each vertex v has 13 neighbours, 39 vertices at distance 2, and 27 at distance 3; each neighbour of v has 12 neighbours at distance 2 from v, each distance 2 vertex has 4 mutual neighbours with v, and 9 neighbours at distance 3 from v.

Such a graph is unique: this is so for each q a prime power, in fact, there is 1-to-1 correspondence between such graphs and 3-dimensional projective spaces: take as points (resp. planes) of the space parts of the bipartition, with incidence being the adjacency in \Gamma, and subgraphs Q as lines, with adjacency between lines and points (resp. planes) being inclusion.
And k-dimensional finite projective spaces, for k\geq 3, are all coming from the natural construction from the 4-dimensional vector space over a Galois field.

Another natural construction of \Gamma comes from a non-degenerate 6-variate quadratic form, over \mathbb{F}_q, of maximal Witt index (i.e. a form that cannot be rewritten as a form with lesser number of variables using a nondeg. linear transformation, and such that there are totally isotropic subspaces of dimension 3, the maximal possible in fact). Recall that a subspace U is called totally isotropic w.r.t. to a form \langle , \rangle if \langle s , t \rangle=0 for all s,t\in U.
Then the vertices of \Gamma are the maximal totally isotropic subspaces, with adjacency being the maximality of the intersection dimension (i.e. two vertices are adjacent iff the corresponding 3-spaces intersect in a 2-dimensional subspace).

Example. For q=3 one can take \langle X,X\rangle=X_1 X_2-X_3^2-X_4^2-X_5^2-X_6^2, and a maximal totally isotropic subspace with a basis
\{(1,0,\dots,0), (0,0,0,1,1,1),  (0,0,1,1,-1,0)\}.
The advantage of this construction is that it allows to describe dual polar graphs D_k for k\geq 4 as well. (Take 2k-variate nondeg. form of maximal Witt index equal to k, etc.)

We are interested in constructing a subgraph \Delta of \Gamma that behaves
like \Gamma when we look at the neighbours of v, with the difference that edges on v and the subgraphs Q on v now form an affine plane, not a projective one. So Q\cap\Delta \cong K_{q,q}, while Q\cong K_{q+1,q+1}. In order to do so, we pick up an edge (s,t)\in E\Gamma, and remove from the latter all the vertices adjacent to either s or t. The resulting graph is exactly \Delta that we want!
In terms of maximal totally isotropic subspaces, the vertices of \Delta are these ones that have 0 intersection with the 2-dimensional subspace corresponding to the intersection of the 3-dimensional subspaces corresponding to s and t. We have a distance-regular graph of diameter 4, with distribution diagram (for q=3) around a vertex as follows:
It is a q-fold antipodal cover of K_{q^2,q^2}, i.e. the vertices are partitioned into sets of size q such that pairwise distances between vertices in each of them are maximal, i.e. 4, and there is a naturally defined structure of complete bipartite graphs on them.

row sums of character tables

16 July, 2008

If you ever worked with finite groups, chances are you stared at group character tables, e.g. ones in Atlas of Finite Groups, or ones produced by a CA system, such as GAP. Each row stores a character \chi of an irreducible representation of a group G, columns correspond to the values \chi(C_i) of \chi on representatives of the conjugacy classes C_1,\dots C_k of G. The following must be known, but so far I haven’t found any references.

Proposition. S_\chi =  \sum_{i=1}^k \chi(C_i) is a nonnegative integer, namely
it is the multiplicity of \chi in the character \theta of G acting on itself by conjugation.

Indeed, note that \theta(C_i)=\frac{|G|}{|C_i|}, as it counts the order of the centraliser in G of an element in C_i. Then using the First Orthogonality Relation of characters on \chi and \theta completes the proof: S_\chi=\frac{1}{|G|}\sum_j |C_j|\chi(C_j)\theta(C_j), as claimed.

Update (21.04.09) It turns out to be well-known: see e.g. Solomon, Louis, “On the sum of the elements in the character table of a finite group”. Proc. AMS 12(1961) 962–963.

The below conjecture was actually made by Richard L. Roth in “On the conjugating representation of a finite group”. Pacific J. Math. 36(1971), 515-521.

And it was disproved by Edward Formanek in “The conjugation representation and fusionless extensions”. Proc. AMS 30(1971), 73–74.

Question. When does S_\chi=0 ? It does happen, e.g. take a nontrivial 1-dimensional representation of an abelian group (as an abelian group acts trivially on itself, only trivial character will occur in \theta).
More generally, if \chi is an irreducible character such that \chi(1_G)\neq \chi(z) for 1_G\neq z\in Z(G), then \chi does not occur in \theta, and so S_\chi=0. Is the latter also only if? (Here Z(G) denotes the centre of G.)

Update (21.04.09) See the 3rd reference above for a negative answer to this.

e-learning week

31 March, 2008

it’s here again. We are supposed to put all the lectures for this online, using a pretty usless tool that allows one to record a very low-resolution video of your face, voice-over, and synchronise with your powerpoint slides (or perhaps some other slide format is supported too, I didn’t investigate). The thing runs on Windows only, and the university pays to the company that developed that oh so wonderful product quite a bit, I gather…

As I can’t skip it this time (I was lucky to schedule midterms precisely for such a week last year :)) I’ll just shoot a video of myself giving lecture at a whiteboard, as I did 2 years ago

PS. And while I was shooting the video using iSight camera and Powerbook G4, the harddisk in the latter just died…