Asymmetric polygons with maximum area

We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given n diameters of a circle and a positive integer k < n, this paper addresses the problem of computing a maximum area asymmetric k-gon having as vertices k < n endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.

Approximation limits of linear programs (beyond hierarchies)

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^1/2-ε)-approximations for CLIQUE require LPs of size 2^nΩ(ε). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.

Les derniers écueils vers la parité aux élections régionales en Belgique

La Belgique impose depuis les années 2000 la parité femmes-hommes sur les listes de candidats pour les élections aux différents niveaux de pouvoir (local, régional, fédéral et européen). Cette obligation a accru la féminisation des assemblées pour atteindre entre un quart et un tiers d’élues. Le progrès est donc réel mais la stricte parité reste éloignée. Cet article s’interroge sur les raisons de ce « plafond de verre ». Elles sont à chercher dans la réticence des partis à accorder les premières places sur les listes à des candidates, et encore plus à placer une femme en première position. Dans un scrutin proportionnel de listes semi-ouvertes, la part d’élues s’en trouve automatiquement réduite, surtout lorsque la magnitude des circonscriptions est faible. Parmi les motivations de ces réticences à la parité l’une des plus importantes est la conviction que les candidates seraient de moins bonnes « locomotives électorales » que leurs homologues masculins. Pourtant, et cet article le démontre, ces craintes ne résistent pas à l’épreuve des faits. Une analyse détaillée des résultats électoraux en Belgique montre bien que les femmes ne réalisent pas de moins bonnes performances électorales que les hommes lorsqu’elles sont placées en tête de liste.