Search

For an oriented graph $D$ and a set $X\subseteq V(D)$, the inversion of $X$ in $D$ is the graph obtained from $D$ by reversing the orientation of each edge that has both endpoints in $X$. Define the inversion number of $D$, denoted $inv(D)$, to be the minimum number of inversions required to obtain an acyclic oriented graph from $D$. We show that $inv({D_1 \rightarrow D_2}) > inv(D_1)$, for any oriented graphs $D_1$ and $D_2$ such that $inv(D_1) = inv(D_2) \ge 1$. This resolves a question of Aubian, Havet, H\"{o}rsch, Klingelhoefer, Nisse, Rambaud and Vermande. Our proof proceeds via a natural connection between the graph inversion number and the subgraph complementation number., Comment: 10 pages

Given a finite poset $\mathcal P$, we say that a family $\mathcal F$ of subsets of $[n]$ is $\mathcal P$-saturated if $\mathcal F$ does not contain an induced copy of $\mathcal P$, but adding any other set to $\mathcal F$ creates an induced copy of $\mathcal P$. The induced saturation number of $\mathcal P$, denoted by $\text{sat}^*(n,\mathcal P)$, is the size of the smallest $\mathcal P$-saturated family with ground set $[n]$. In this paper we prove that the saturation number for any given poset grows at worst polynomially. More precisely, we show that $\text{sat}^*(n, \mathcal P)=O(n^c)$, where $c\leq|\mathcal{P}|^2/4+1$ is a constant depending on $\mathcal P$ only. We obtain this result by bounding the VC-dimension of our family., Comment: 7 pages, 2 figures

We analyse the typical structure of games in terms of the connectivity properties of their best-response graphs. Our central result shows that almost every game that is 'generic' (without indifferences) and has a pure Nash equilibrium and a 'large' number of players is connected, meaning that every action profile that is not a pure Nash equilibrium can reach every pure Nash equilibrium via best-response paths. This has important implications for dynamics in games. In particular, we show that there are simple, uncoupled, adaptive dynamics for which period-by-period play converges almost surely to a pure Nash equilibrium in almost every large generic game that has one (which contrasts with the known fact that there is no such dynamic that leads almost surely to a pure Nash equilibrium in every generic game that has one). We build on recent results in probabilistic combinatorics for our characterisation of game connectivity., Comment: 39 pages; v3: improved the introduction and added more discussion of our results. Other minor changes

Given an integer $n$, let $G(n)$ be the number of integer sequences $n-1\ge d_1\ge d_2\ge\dotsb\ge d_n\ge 0$ that are the degree sequence of some graph. We show that $G(n)=(c+o(1))4^n/n^{3/4}$ for some constant $c>0$, improving both the previously best upper and lower bounds by a factor of $n^{1/4}$ (up to polylog-factors). Additionally, we answer a question of Royle, extend the values of $n$ for which the exact value of $G(n)$ is known from $n\le290$ to $n\le 1651$ and determine the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge remains non-negative., Comment: 43 pages, 2 figures

In the graph shotgun assembly problem, we are given the balls of radius $r$ around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erd\H{o}s-R\'enyi random graph $\mathcal G(n,p)$ from a wide range of values of $r$. We determine the threshold for reconstructibility for each $r\geq 3$, extending and improving substantially on results of Mossel and Ross for $r=3$. For $r=2$, we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for $r=1$., Comment: 36 pages, 3 figures

Given a graph $H$, we say that an edge-coloured graph $G$ is $H$-rainbow saturated if it does not contain a rainbow copy of $H$, but the addition of any non-edge in any colour creates a rainbow copy of $H$. The rainbow saturation number $\text{rsat}(n,H)$ is the minimum number of edges among all $H$-rainbow saturated edge-coloured graphs on $n$ vertices. We prove that for any non-empty graph $H$, the rainbow saturation number is linear in $n$, thus proving a conjecture of Gir\~{a}o, Lewis, and Popielarz. In addition, we also give an improved upper bound on the rainbow saturation number of the complete graph, disproving a second conjecture of Gir\~{a}o, Lewis, and Popielarz., Comment: 16 pages, 2 figures

A lazy transposition $(a,b,p)$ is the random permutation that equals the identity with probability $1-p$ and the transposition $(a,b)\in S_n$ with probability $p$. How long must a sequence of independent lazy transpositions be if their composition is uniformly distributed? It is known that there are sequences of length $\binom{n}2$, but are there shorter sequences? This was raised by Fitzsimons in 2011, and independently by Angel and Holroyd in 2018. We answer this question negatively by giving a construction of length $\frac23 \binom{n}2+O(n\log n)$, and consider some related questions., Comment: 23 pages, 5 figures, 1 table

We investigate a generalisation of permutation networks. We say a sequence $T=(T_1,\dots,T_\ell)$ of transpositions in $S_n$ forms a $t$-reachability network if for every choice of $t$ distinct points $x_1, \dots, x_t\in \{1,\dots,n\}$, there is a subsequence of $T$ whose composition maps $j$ to $x_j$ for every $1\leq j\leq t$. When $t=n$, any permutation in $S_n$ can be created and $T$ is a permutation network. Waksman [JACM, 1968] showed that the shortest permutation networks have length about $n \log_2n$. In this paper, we investigate the shortest $t$-reachability networks. Our main result settles the case of $t=2$: the shortest $2$-reachability network has length $\lceil 3n/2\rceil-2 $. For fixed $t$, we give a simple randomised construction which shows there exist $t$-reachability networks using $(2+o_t(n))n$ transpositions. We also study the case where all transpositions are of the form $(1, \cdot)$, separating 2-reachability from the related probabilistic variant of 2-uniformity. Many interesting questions are left open., Comment: 13 pages, 1 figure

For given positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1,\dots,n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$, but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use sat$^*(n, k)$ to denote the smallest size of such a family. For all $k$ and sufficiently large $n$, we determine the exact value of sat$^*(n, k)$. Our result implies that sat$^*(n, k)=n(k-1)-\Theta(k\log k)$, which confirms several conjectures on antichain saturation. Previously, exact values for sat$^*(n,k)$ were only known for $k$ up to $6$. We also prove a generalisation of a result of Lehman-Ron which may be of independent interest. We show that given $m$ disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one)., Comment: 31 pages, 3 figures

A 1-independent bond percolation model on a graph $G$ is a probability distribution on the spanning subgraphs of $G$ in which, for all vertex-disjoint sets of edges $S_1$ and $S_2$, the states of the edges in $S_1$ are independent of the states of the edges in $S_2$. Such a model is said to percolate if the random subgraph has an infinite component with positive probability. In 2012 the first author and Bollob\'as defined $p_{\max}(G)$ to be the supremum of those $p$ for which there exists a 1-independent bond percolation model on $G$ in which each edge is present in the random subgraph with probability at least $p$ but which does not percolate. A fundamental and challenging problem in this area is to determine the value of $p_{\max}(G)$ when $G$ is the lattice graph $\mathbb{Z}^2$. Since $p_{\max}(\mathbb{Z}^n)\leq p_{\max}(\mathbb{Z}^{n-1})$, it is also of interest to establish the value of $\lim_{n\to\infty} p_{\max}(\mathbb{Z}^n)$. In this paper we significantly improve the best known upper bound on this limit and obtain better upper and lower bounds on $p_{\max}(\mathbb{Z}^2)$. In proving these results, we also give an upper bound on the critical probability for a 1-independent model on the hypercube graph to contain a giant component asymptotically almost surely., Comment: 31 pages, 3 figures

Two permutations $s$ and $t$ are $k$-similar if they can be decomposed into subpermutations $s^1, \ldots, s^k$ and $t^1, \ldots, t^k$ such that $s^i$ is order-isomorphic to $t^i$ for all $i$. Recently, Dudek, Grytczuk and Ruci\'nski posed the problem of determining the minimum $k$ for which two permutations chosen independently and uniformly at random are $k$-similar. We show that two such permutations are $O(n^{1/3}\log^{11/6}(n))$-similar with high probability, which is tight up to a polylogarithmic factor. Our result also generalises to simultaneous decompositions of multiple permutations., Comment: 11 pages, 2 figures

A square is a factor $S = (S_1; S_2)$ where $S_1$ and $S_2$ have the same pattern, and a permutation is said to be square-free if it contains no non-trivial squares. The permutation is further said to be bicrucial if every extension to the left or right contains a square. We completely classify for which $n$ there exists a bicrucial square-free permutation of length $n$., Comment: 24 pages, 4 figures

The $\ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $\ell$ vertices. We say that a graph is reconstructible from its $\ell$-deck if no other graph has the same $\ell$-deck. In 1957, Kelly showed that every tree with $n\ge3$ vertices can be reconstructed from its $(n-1)$-deck, and Giles strengthened this in 1976, proving that trees on at least 6 vertices can be reconstructed from their $(n-2)$-decks. Our main theorem states that trees are reconstructible from their $(n-r)$-decks for all $r\le n/{9}+o(n)$, making substantial progress towards a conjecture of N\'ydl from 1990. In addition, we can recognise the connectedness of a graph from its $\ell$-deck when $\ell\ge 9n/10$, and reconstruct the degree sequence when $\ell\ge\sqrt{2n\log(2n)}$. All of these results are significant improvements on previous bounds., Comment: 29 pages, improvements to exposition and proof clarity

The deck of a graph $G$ is the multiset of cards $\{G-v:v\in V(G)\}$. Myrvold (1992) showed that the degree sequence of a graph on $n\geq7$ vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree $d$ can reconstructed from any deck missing $O(n/d^3)$ cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing., Comment: 10 pages

Given a matrix $M = (a_{i,j})$ a square is a $2 \times 2$ submatrix with entries $a_{i,j}$, $a_{i, j+s}$, $a_{i+s, j}$, $a_{i+s, j +s}$ for some $s \geq 1$, and a zero-sum square is a square where the entries sum to $0$. Recently, Ar\'evalo, Montejano and Rold\'an-Pensado proved that all large $n \times n$ $\{-1,1\}$-matrices $M$ with discrepancy $|\sum a_{i,j}| \leq n$ contain a zero-sum square unless they are split. We improve this bound by showing that all large $n \times n$ $\{-1,1\}$-matrices $M$ with discrepancy at most $n^2/4$ are either split or contain a zero-sum square. Since zero-sum square free matrices with discrepancy at most $n^2/2$ are already known, this bound is asymptotically optimal., Comment: 19 pages, 7 figures

Alon and F\"{u}redi (1993) showed that the number of hyperplanes required to cover $\{0,1\}^n\setminus \{0\}$ without covering $0$ is $n$. We initiate the study of such exact hyperplane covers of the hypercube for other subsets of the hypercube. In particular, we provide exact solutions for covering $\{0,1\}^n$ while missing up to four points and give asymptotic bounds in the general case. Several interesting questions are left open., Comment: Small fixes and updated code

A subspace of $\mathbb{F}_2^n$ is called cyclically covering if every vector in $\mathbb{F}_2^n$ has a cyclic shift which is inside the subspace. Let $h_2(n)$ denote the largest possible codimension of a cyclically covering subspace of $\mathbb{F}_2^n$. We show that $h_2(p)= 2$ for every prime $p$ such that 2 is a primitive root modulo $p$, which, assuming Artin's conjecture, answers a question of Peter Cameron from 1991. We also prove various bounds on $h_2(ab)$ depending on $h_2(a)$ and $h_2(b)$ and extend some of our results to a more general set-up proposed by Cameron, Ellis and Raynaud., Comment: 36 pages

We answer four questions from a recent paper of Rao and Shinkar on Lipschitz bijections between functions from $\{0,1\}^n$ to $\{0,1\}$. (1) We show that there is no $O(1)$-bi-Lipschitz bijection from $\mathrm{Dictator}$ to $\mathrm{XOR}$ such that each output bit depends on $O(1)$ input bits. (2) We give a construction for a mapping from $\mathrm{XOR}$ to $\mathrm{Majority}$ which has average stretch $O(\sqrt{n})$, matching a previously known lower bound. (3) We give a 3-Lipschitz embedding $\phi : \{0,1\}^n \to \{0,1\}^{2n+1}$ such that $\mathrm{XOR}(x) = \mathrm{Majority}(\phi(x))$ for all $x \in \{0,1\}^n$. (4) We show that with high probability there is a $O(1)$-bi-Lipschitz mapping from $\mathrm{Dictator}$ to a uniformly random balanced function.

We continue the study by Melo and Winter [arXiv:1712.01763, 2017] on the possible intersection sizes of a $k$-dimensional subspace with the vertices of the $n$-dimensional hypercube in Euclidean space. Melo and Winter conjectured that all intersection sizes larger than $2^{k-1}$ (the "large" sizes) are of the form $2^{k-1}+2^i$. We show that this is almost true: the large intersection sizes are either of this form or of the form $35\cdot 2^{k-6}$. We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the "small" values is missing.

If $\mathcal{W}$ is the simple random walk on the square lattice $\mathbb{Z}^2$, then $\mathcal{W}$ induces a random walk $\mathcal{W}_G$ on any spanning subgraph $G\subset \mathbb{Z}^2$ of the lattice as follows: viewing $\mathcal{W}$ as a uniformly random infinite word on the alphabet $\{\mathbf{x}, -\mathbf{x}, \mathbf{y}, -\mathbf{y} \}$, the walk $\mathcal{W}_G$ starts at the origin and follows the directions specified by $\mathcal{W}$, only accepting steps of $\mathcal{W}$ along which the walk $\mathcal{W}_G$ does not exit $G$. For any fixed subgraph $G \subset \mathbb{Z}^2$, the walk $\mathcal{W}_G$ is distributed as the simple random walk on $G$, and hence $\mathcal{W}_G$ is almost surely recurrent in the sense that $\mathcal{W}_G$ visits every site reachable from the origin in $G$ infinitely often. This fact naturally leads us to ask the following: does $\mathcal{W}$ almost surely have the property that $\mathcal{W}_G$ is recurrent for \emph{every} subgraph $G \subset \mathbb{Z}^2$? We answer this question negatively, demonstrating that exceptional subgraphs exist almost surely. In fact, we show more to be true: exceptional subgraphs continue to exist almost surely for a countable collection of independent simple random walks, but on the other hand, there are almost surely no exceptional subgraphs for a branching random walk., Comment: 19 pages, submitted