Category Archives: Mathematics

Mathematical Illustrations

As a manual of geometry and Postscript, the beginning chapters of this book reminds me a lot of my junior school Logo tutorials. But very soon Bill Casselman starts to draw 3D objects in 2D and projection is where the story gets very interesting. (Think how to draw a polyhedron on a piece of paper.)

The book has an online version and a paper edition.

P.S. One tidbit I learned from this book is that doughnut, oh I mean, torus means cushion in Latin. Hehe.

An Annoying Combinatorial Problem

Here is an “innocent” combinatorial problem, with the best known bounds being very simple (but nobody managed to improve them since 1978). Disclaimer: the problem is very catchy (I struggled with it for quite a while), so do not read any further if, for example, you are writing a PhD thesis :-)

Maker and Breaker alternatively select 1 and q edges of K_n (the complete graph on n vertices) until all edges have been claimed. Maker wins if his graph has a triangle. What is the smallest q=q(n) such that Breaker has a winning strategy?

The best known strategy for Maker is to claim edges incident to some vertex x (and never miss a one-step win). If Breaker managed to block x completely, say after m rounds, then Breaker made n-1-m + {m\choose 2}\le m q(n) moves. This implies that q(n) is approximately at least \sqrt{2n}.

On the other hand, Breaker can win if q> 2\sqrt{n}: for each edge xy claimed by Maker, Breaker selects \sqrt{n} edges at x and \sqrt{n} edges at y. Thus Maker’s graph has maximum degree at most (n-1)/\sqrt{n}+1 and Breaker can always block all immediate threats.

Reference: V.Chvatal and P.Erdos, Biased positional games, Ann. Discrete Math. 2 (1978), 221-229.

I would bet on the \sqrt{2n} bound :-)

Oleg