Dear all,

next Monday's Lecture and Colloquium will take place on July 11 at
14:15 & 16:00 at TU Berlin.

**You all are cordially invited. **

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, July 11 - 14:15**

__Lecture__: Bill Zwicker (Union College, USA)

__Title__: Higher-order Condorcet cycles

In an ordinary Condorcet cycle one can identify, for each candidate, a second candidate preferred, by a majority of voters, to the first. In a

William S. Zwicker^{a} (joint work with Davide P.
Cervone^{b})

keywords: Condorcet cycle of order 2, Condorcet winning set, tournament

[1] Elkind, E., Lang, J., and Saffidine, A., Condorcet
Winning Sets, *Soc Choice Welf *44, 493-517 (2015)

[2] Erdös, P., On a problem of graph theory, *Math Gaz*
47, 220-223 (1963)

[3] Graham, R.L. and Spencer, J.H., A constructive solution
to a tournament problem, *Can Math Bul* 14, 45-48
(1971)

[4] Szekeres, E. and Szekeres,G., On a problem of Schütte and
Erdös, *Math Gaz* 49, 290-293 (1965)

^{a}William D Williams Professor of Mathematics
Emeritus, Union College, New York; and Murat Sertel Center for
Advanced Economic Studies, Istanbul Bilgi University

^{b}Mathematics Department, Union College, New York

__Colloquium__: Warut Suksompong (National University of
Singapore)

__Title__: The Price of Connectivity in Fair Division

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems. Joint work with Xiaohui Bei, Ayumi Igarashi, and Xinhang Lu.

--------------E9189D12200AC3D0AE8DDCAE-- From itabrunke@zedat.fu-berlin.de Thu Jul 14 00:26:14 2022 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

Dear all,

our next and last Monday's Lecture and Colloquium will take place
on July 18 at 14:15 & 16:00 at FU Berlin.

**You are all cordially invited. **

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, July 18 - 14:15**

__Lecture__: Herman Haverkort (Universität Bonn)

__Title__: Space-filling curves: properties, applications
and challenges

A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in d-dimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how space-filling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal space-filling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a space-filling curve.

__Colloquium__: Andrea Jiménez (Universidad de Varparaíso,
Chile)

__Title__: Groundstates of the Ising Model on
antiferromagnetic triangulations

We discuss a dual version of a problem about perfect matchings in cubic graphs posed by Lovasz and Plummer. The dual version is formulated as follows "Every triangulation of an orientable surface has exponentially many groundstates'', where groundstates are the states at the lowest energy in the antiferromagnetic Ising Model.

According to physicists, this dual formulation holds. In this talk, I show a counterexample to the dual formulation, a method to count groundstates which gives a better bound (for the original problem) on the class of Klee-graphs, the complexity of the related problems and, if time allows, some open problems.

This is joint work with Marcos Kiwi and Martin Loebl.

Dear all,

there may be a change of program for the colloquium.

Our next and last Monday's Lecture and Colloquium will take
place on July 18 at 14:15 & 16:00 at FU Berlin.

**You are all cordially invited. **

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, July 18 - 14:15**

__Lecture__: Herman Haverkort (Universität Bonn)

__Title__: Space-filling curves: properties, applications
and challenges

A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in d-dimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how space-filling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal space-filling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a space-filling curve.

__Colloquium__: Andrea Jiménez (Universidad de
Varparaíso, Chile)

__Title__: Grid subdivisions, wall minors
and treewidth in planar graphs

Minors, subdivisions and treewidth are classical notions that appear for example in the seminal characterization of planar graphs by Kuratowski and in the celebrated Graph Minor Theorem by Robertson and Seymour. The importance of grid/wall minors comes from one of the results of Robertson and Seymour, which roughly claims that a graph of large treewidth necessarily contains a large grid/wall minor. The concept of treewidth is fundamental in algorithmic graph theory since many problems which are hard to solve in general, can be efficiently solved when restricted to classes of graphs with bounded treewidth.

In this talk, we discuss the computational complexity of the
Minor Problem, the Subdivision Problem and the
Treewidth Problem with input: grids/walls and planar graphs.
Surprisingly, some of these problems are still open. We describe
two reductions which prove that the respective GridSubdivision
Problem and the WallMinor Problem are NP-complete problems.

Dear Colleagues,

in 2022 Martin Aigner has turned 80. On the afternoon
(14:00-18:00) of the 7th of November we will celebrate this
occasion with a Festkolloquium. Invited speakers include Mathias
Schacht (Hamburg), Emo Welzl (Zurich), and Günther Ziegler
(Berlin). There is no registration fee, however, if you are
interested in attending, please indicate this **by the end of
September:**

** **https://docs.google.com/forms/d/e/1FAIpQLSfEsxz0FD9RDZQT2PosE86UD-HFHjgGFDBQTE8hvD4ETsb-dg/viewform

so we can estimate the number of participants.

Best regards,

Tibor Szabó