We investigate the number of maximal independent set queries required to reconstruct the edges of a hidden graph. We show that randomised adaptive algorithms need at least Ω ( Δ 2 log ⁡ ( n / Δ ) / log ⁡ Δ ) queries to reconstruct n -vertex graphs of maximum degree Δ with success probability at least 1/2, and we further improve this lower bound to Ω ( Δ 2 log ⁡ ( n / Δ ) ) for randomised non-adaptive algorithms. We also prove that deterministic non-adaptive algorithms require at least Ω ( Δ 3 log ⁡ n / log ⁡ Δ ) queries. This improves bounds of Konrad, O'Sullivan, and Traistaru, and answers one of their questions. The proof of the lower bound for deterministic non-adaptive algorithms relies on a connection to cover-free families, for which we also improve known bounds.

Abstract. For an oriented graph [Formula: see text] and a set [Formula: see text], the inversion of [Formula: see text] in [Formula: see text] is the digraph obtained by reversing the orientations of the edges of [Formula: see text] with both endpoints in [Formula: see text]. The inversion number of [Formula: see text], [Formula: see text], is the minimum number of inversions which can be applied in turn to [Formula: see text] to produce an acyclic digraph. Answering a recent question of Bang-Jensen, da Silva, and Havet we show that, for each [Formula: see text] and tournament [Formula: see text], the problem of deciding whether [Formula: see text] is solvable in time [Formula: see text], which is tight for all [Formula: see text]. In particular, the problem is fixed-parameter tractable when parameterized by [Formula: see text]. On the other hand, we build on their work to prove their conjecture that for [Formula: see text] the problem of deciding whether a general oriented graph [Formula: see text] has [Formula: see text] is NP-complete. We also construct oriented graphs with inversion number equal to twice their cycle transversal number, confirming another conjecture of Bang-Jensen, da Silva, and Havet, and we provide a counterexample to their conjecture concerning the inversion number of so-called dijoin digraphs while proving that it holds in certain cases. Finally, we asymptotically solve the natural extremal question in this setting, improving on previous bounds of Belkhechine, Bouaziz, Boudabbous, and Pouzet to show that the maximum inversion number of an [Formula: see text]-vertex tournament is [Formula: see text].

Abstract. Let [Formula: see text] be a set of [Formula: see text] points on the real line. Suppose that each pairwise distance is known independently with probability [Formula: see text]. How much of [Formula: see text] can be reconstructed up to isometry? We prove that [Formula: see text] is a sharp threshold for reconstructing all of [Formula: see text], which improves a result of Benjamini and Tzalik. This follows from a hitting time result for the random process where the pairwise distances are revealed one by one uniformly at random. We also show that [Formula: see text] is a weak threshold for reconstructing a linear proportion of [Formula: see text].

Abstract. Fix [Formula: see text], and let [Formula: see text] be a graph, with vertex set partitioned into [Formula: see text] subsets (“blocks”) of approximately equal size. An induced subgraph of [Formula: see text] is “transversal” (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly [Formula: see text] vertices). A “pure pair” in [Formula: see text] is a pair [Formula: see text] of disjoint subsets of [Formula: see text] such that either all edges between [Formula: see text] are present or none are; and in the present context we are interested in pure pairs [Formula: see text] where each of [Formula: see text] is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded.

Abstract. Two permutations [Formula: see text] and [Formula: see text] are [Formula: see text]-similar if they can be decomposed into subpermutations [Formula: see text] and [Formula: see text] such that [Formula: see text] is order-isomorphic to [Formula: see text] for all [Formula: see text]. Recently, Dudek, Grytczuk, and Ruciński Variations on twins in permutations, Electron. J. Combin., 28 (2021), P3.19. posed the problem of determining the minimum [Formula: see text] for which two permutations chosen independently and uniformly at random are [Formula: see text]-similar. We show that two such permutations are [Formula: see text]-similar with high probability, which is tight up to a polylogarithmic factor. Our result also generalizes to simultaneous decompositions of multiple permutations.

Let $\mathcal F$ be an antichain of finite subsets of $\mathbb N$. How quickly can the quantities $|\mathcal{F}\cap 2^{[n]}|$ grow as $n\to\infty$? We show that for any sequence $(f_n)_{n\ge n_0}$ of positive integers satisfying $\sum_{n=n_0}^\infty f_n/2^n \le 1/4$ and $f_n\le f_{n+1}\le 2f_n$, there exists an infinite antichain $\mathcal{F}$ of finite subsets of $\mathbb{N}$ such that $|\F\cap 2^{[n]}| \geq f_n$ for all $n\ge n_0$. It follows that for any $\varepsilon>0$ there exists an antichain $\mathcal{F}\subseteq 2^{\mathbb{N}}$ such that $\liminf_{n \to \infty} |\mathcal{F}\cap 2^{[n]}| \cdot \big(\frac{2^n}{n\log^{1+\varepsilon} n}\big)^{-1} > 0.$ This resolves a problem of Sudakov, Tomon, and Wagner in a strong form and is essentially tight.

A pure pair in a graph $G$ is a pair $(Z_1,Z_2)$ of disjoint sets of vertices such that either every vertex in $Z_1$ is adjacent to every vertex in $Z_2$, or there are no edges between $Z_1$ and $Z_2$. With Maria Chudnovsky, we recently proved that, for every forest $F$, every graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair $(Z_1,Z_2)$ with $|Z_1|,|Z_2|$ linear in $|G|$. Here we investigate what we can say about pure pairs in an ordered graph $G$, when we exclude an ordered forest $F$ and its complement as induced subgraphs. Fox showed that there need not be a linear pure pair; but Pach and Tomon showed that if $F$ is a monotone path, then there is a pure pair of size $c|G|/\log |G|$. We generalize this to all ordered forests, at the cost of a slightly worse bound: we prove that, for every ordered forest $F$, every ordered graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair of size $|G|^{1-o(1)}$.

Gathering training data is a key step of any supervised learning task, and it is both critical and expensive. Critical, because the quantity and quality of the training data has a high impact on the performance of the learned function. Expensive, because most practical cases rely on humans-in-the-loop to label the data. The process of determining the correct labels is much more expensive than comparing two items to see whether they belong to the same class. Thus motivated, we propose a setting for training data gathering where the human experts perform the comparatively cheap task of answering pairwise queries, and the computer groups the items into classes (which can be labeled cheaply at the very end of the process). Given the items, we consider two random models for the classes: one where the set partition they form is drawn uniformly, the other one where each item chooses its class independently following a fixed distribution. In the first model, we characterize the algorithms that minimize the average number of queries required to cluster the items and analyze their complexity. In the second model, we analyze a specific algorithm family, propose as a conjecture that they reach the minimum average number of queries and compare their performance to a random approach. We also propose solutions to handle errors or inconsistencies in the experts' answers.

We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing 2Ω(n2) n-vertex graphs as n→ ∞. This regime contains many classes of interest, for instance perfect graphs or comparability graphs, for which we obtain an adjacency labelling scheme with labels of n/4+o(n) bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of n/4+o(n) bits per vertex and comparability labelling scheme for posets with labels of n/4+o(n) bits per element. All these results are best possible, up to the lower order term.

An odd hole in a graph is an induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time algorithm to test if a graph has an odd hole. We subsequently showed that, for every t , there is a polynomial-time algorithm to test whether a graph contains an odd hole of length at least t . In this article, we give an algorithm that finds a shortest odd hole, if one exists.

We give a polynomial-time algorithm to test whether a graph contains an induced cycle with length more than three and odd.

A $k$-uniform hypergraph is $s$-almost intersecting if every edge is disjoint from exactly $s$ other edges. Gerbner et al. [SIAM J. Discrete Math., 26 (2012), pp. 1657--1669] conjectured that for every $k$, and $s>s_0(k)$, every $k$-uniform $s$-almost intersecting hypergraph has at most $(s+1)\binom{2k-2}{k-1}$ edges. We prove a strengthened version of this conjecture and determine the extremal graphs. We also give some related results and conjectures.

Maximal Independent Set selection is a fundamental problem in distributed computing. A novel probabilistic algorithm for this problem has recently been proposed by Afek et al, inspired by the study of the way that developing cells in the fly become specialised. The algorithm they propose is simple and robust, but not as efficient as previous approaches: the expected time complexity is O(log2 n). Here we first show that the approach of Afek et al cannot achieve better efficiency than this across all networks, no matter how the global probability values are chosen.

A coloring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each color; the polychromatic number is the maximum number of colors in such a coloring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric hypergraphs, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size and degree); our goal here is to broaden the study beyond geometric settings. We obtain algorithms yielding near-tight bounds for three families of hypergraphs: bounded hyperedge size, paths in trees, and bounded Vapnik--Chervonenkis (VC)-dimension. This reveals that discrepancy theory and iterated linear program relaxation are useful for cover-decomposition. Finally, we discuss the generalization of cover-decomposition to sensor cover.

In this short paper we study the game of cops and robbers, which is played on the vertices of some fixed graph [Formula: see text]. Cops and a robber are allowed to move along the edges of [Formula: see text], and the goal of cops is to capture the robber. The cop number [Formula: see text] of [Formula: see text] is the minimum number of cops required to win the game. Meyniel conjectured a long time ago that [Formula: see text] cops are enough for any connected [Formula: see text] on [Formula: see text] vertices. Improving several previous results, we prove that the cop number of an [Formula: see text]-vertex graph is at most [Formula: see text]. A similar result independently and slightly before us was also obtained by Lu and Peng.

We introduce a problem class we call Polynomial Constraint Satisfaction Problems, or PCSP. Where the usual CSPs from computer science and optimization have real-valued score functions, and partition functions from physics have monomials, PCSP has scores that are arbitrary multivariate formal polynomials, or indeed take values in an arbitrary ring. Although PCSP is much more general than CSP, remarkably, all (exact, exponential-time) algorithms we know of for 2-CSP (where each score depends on at most 2 variables) extend to 2-PCSP, at the expense of just a polynomial factor in running time. Specifically, we extend the reduction-based algorithm of Scott and Sorkin [2007]; the specialization of that approach to sparse random instances, where the algorithm runs in polynomial expected time; dynamic-programming algorithms based on tree decompositions; and the split-and-list matrix-multiplication algorithm of Williams [2004]. This gives the first polynomial-space exact algorithm more efficient than exhaustive enumeration for the well-studied problems of finding a maximum bisection of a graph, and calculating the partition function of an Ising model. It also yields the most efficient algorithm known for certain instances of counting and/or weighted Maximum Independent Set. Furthermore, PCSP solves both optimization and counting versions of a wide range of problems, including all CSPs, and thus enables samplers including uniform sampling of optimal solutions and Gibbs sampling of all solutions.

We prove that every finite subset of the plane is reconstructible from the multiset of its subsets of at most 18 points, each given up to rigid motion. We also give some results concerning the reconstructibility of infinite subsets of the plane.