8th Cracow Conference on Graph Theory

How do two people share a cake? As everyone knows, one cuts and the other chooses. This does not assume that the two people value the cake in the same ways: maybe one loves cherries, and the other hates icing.

In more mathematical terms, each person has a measure on the cake; without loss, the total measure is 1. The procedure satisfies two fairness conditions:

  • Proportionality: each person gets at least half of the cake, according to her valuation.
  • Envy-freeness: neither person prefers the other’s piece of cake to her own.

It is fairly well known that there is an extension which allows n people to share a cake fairly (satisfying the above criteria).

Why am I discussing this in the account of a graph theory conference? Because my choice of the most interesting talk at the conference was Zbigniew Lonc’s talk on this topic.

There are many real-life situations which don’t look like cake-cutting. For example, in a divorce case, maybe a house and a car have to be shared, and half a house or a third of a car are not much use. So it is reasonable to consider a discrete version of the problem, where there are m indivisible goods to be shared among n agents, each of whom has a valuation on each of the goods. This turns the problem into discrete mathematics.

In this case, easy examples show that we cannot satisfy the fairness criteria above. How can they be relaxed? One way is the maximin condition. Each agent considers all partitions of the set of goods into n parts and notes the value of the least valuable part. The maximum of this over all partitions is the best that this agent could expect to get in a “fair division”. An allocation of goods to agents is said to be a maximin share if each agent gets at least this maximin value. A maximin share may not exist (though failures seem to be fairly rare), but it is not even known that the existence of a maximin share is in NP.

But now let us add a further complication, which brings the problem into the realm of graph theory. Suppose that the set of goods is the vertex set of a graph, and we require that the share of each agent should be connected. (Suppose that the agents are farmers and the goods are plots of land; each farmer should get a contiguous set of plots.) We can easily extend the maximin share principle to this case (consider only partitions into connected parts). But can it be done? This question has only been answered for rather special graphs and small numbers of agents.

I wanted to ask a question, but couldn’t formulate it quickly enough. Suppose that, instead of insisting on connected parts, we imagine that each agent puts a value on connectedness (perhaps a decreasing function of the number of parts, or an increasing function on the degree of connectedness). How does the problem change? In a divorce case, the parties would not be happy with a division which gave the television to one and the remote to the other, but they could probably live with it.

The conference was in Rytro, a village more than two hours from Krakow in the mountains, with swimming pool, etc., and a ski lift next door. Brief comments on some of the other talks follow.

There were several talks on the distinguishing index of a graph, the least number of colours required to colour the edges so as to kill all automorphisms. I hope it wasn’t the case that they invited me on the strength of my survey paper with Robert Bailey on similar things (I didn’t realise that I should worry about this until too late, since my talk was the first of the conference.) This number is very small, even if you allow the automorphisms the possibility of permuting the colour classes rather than fixing them.

There were also a number of talks on “facial total colourings” of graphs embedded in surfaces, like the more usual colourings except that edges are only required to have different colours if they are consecutive in a face. There are variants where edges at most k steps apart must get different colours, or where you colour incidences rather than vertices and edges.

Sandi Klavžar talked about the “strong geodetic number” of a graph, a new topic where you ask for a set of vertices and a choice of shortest paths between all pairs in the set so that every vertex of the graph is covered. All published papers on this are 2018 or later. I asked at the end what happens if you want to bound the load on any vertex (the number of paths passing through it), which seems a reasonable condition for a network. He said that is the next thing they are going to look at.

Nikolay Abrosimov gave a talk which was not graph theory, but which I enjoyed. He was talking about the volume of a polyhedron in hyperbolic space, in terms of its side lengths. Once a popular topic (both Lobachevsky and Thurston considered it), but perhaps a bit unfashionable now. Anyway, he had completely solved the problem for symmetric antiprisms.

Akira Sato gave a most enjoyable talk. He was considering two famous results about existence of Hamiltonian cycles, by Ore and by Moon and Moser for bipartite graphs. Can you deduce Ore from Moon and Moser? No, there is a gap of one in the required inequalities. But perhaps you can find all examples attaining the Moon–Moser bound, and find a workaround for these. This can be done, and a lot of interesting arguments have to be deployed to do it.

Marthe Bonamy, the last plenary speaker, gave a thought-provoking talk. It was a pity that many people had already left. It was a graph colouring problem in which the traditionally easiest graphs are the hardest, while a lot of traditionally hard graphs are very easy.

She imagines that each node has unlimited computing power but can only communicate with its neighbours, so has a very local view of the graph. Clearly a path of length n is going to take at least n steps to agree a colouring. But given any graph, if you add a vertex joined to every other vertex, this vertex will see the whole graph in a small finite number of time steps, and can then use its unlimited computing power to find a proper colouring, and then order the others to use it. One of the difficulties (clear even in the path case) is conflict resolution; she talked about this but I am not sure I followed it.

The conference excursion was to the top of Przehyba, an 1175-metre mountain which involved a hike of more than 20 kilometres. With a party of 27 walkers and a guide, of course we didn’t go very fast, and there was plenty of time to view the many different kinds of fungi that grew near the park. By contrast, apart from flies and wasps, there was very little wildlife to be seen: two butterflies, a small passerine bird I couldn’t identify, and a pigeon, and on the way down a pair of crows and a dead mole. From the lunch stop at the restaurant on top of the mountain (a feature we don’t have in Scotland!), we could see the much higher Tatra Mountains in the distance.



About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.