Last week I was at the second Emléktábla workshop in Hungary. It was a great event and a chance to meet lots of other young mathematicians, and learn a lot. One problem which I woked on with János Barát, Filip Morić, and Zoltán Nagy, is the following. (The problem is due to Péter Maga.)
Characterize all graphs which have an embedding in the plane, such that three points are collinear in the embedding iff all three edges between them exist in the graph (i.e., iff they induce a triangle).
After a little while we had one observation: such an embedding is impossible if there is an induced “diamond”/K4–. (In other words, if ax, ay, bx, by, xy are edges and ab is not an edge, the problem is that a, x, y need to be collinear, so do b, x, y, forcing all four to be collinear, but this contradicts the lack of edge a, b.)
This led to the following conjecture, which seemed pretty promising:
Conjecture. A graph G has an embedding of the desired form if and only if it has no induced diamond.
Diamond-free graphs have a nice equivalent description in terms of their maximal cliques:
Lemma. Let V be a set of vertices and S a collection of subsets of V, each of size at least 3. Then S is the family of maximal cliques for a diamond-free graph if and only if (1) there is no pair of sets from S intersecting in more than one vertex, and (2) there is no triple of sets such that each two contain a vertex not contained by the third. (I.e., iff there is no hypercycle of length ≤3.)
(Note that it is ok to only care about cliques of size at least 3 for our purposes: the requirements on the embedding are indifferent to any edges not lying in any triangles.)
However, Zoltán knew some design theory, and in particular he suggested that we should look at generalized quadrangles. They are one type of set system S for which the property in the Lemma holds.
The smallest self-dual quadrangle is a set system of 15 triples on 15 points, such that each point is in three triples, and every point-triple pair (P, T) is either incident, or permits a unique pair (P’, T’) such that the pairs (P, T’), (P’, T’), (P’, T) are incident. (More generally, generalized quadrangles are any set system satisfying the last axiom; they have a partial classification theory akin to finite fields.)
Given a generalized quadrangle, we obtain a diamond-free graph by replacing each tuple by a clique. The diagrams are the result of a Maple computation showing that the smallest generalized quadrangle can be realized such that every triple is collinear, and no other collinearities exist. (There is also a trippy video by Burkard Polster showing this.) So it does not contradict the conjecture. However, the next candidate has 40 points in 40 quadruples, and our vague feeling (based on the number of variables and unknowns) is that it is unrealizable, providing a counterexample to the conjecture. Larger self-dual generalized quadrangles are even worse.
Re-conjecture. Let GQ be a self-dual generalized quadrangle on more than 15 points. Then the graph obtained by replacing each set in the GQ by a clique is a counterexample to the original Conjecture above.
Is it possible yet to print animated gifs on a coffee mug or t-shirt?
Update from a concerned citizen: yes, you can get animated gifs on mugs.
Filed under: graphs, maple, math, movies | Leave a Comment