Abstract A d-dimensional annulus graph with radii $$R_1$$ R 1 and $$R_2$$ R 2 (here $$R_2\ge R_1\ge 0$$ R 2 ≥ R 1 ≥ 0 ) is a graph embeddable in $$\mathbb R^d$$ R d so that two vertices u and v form an edge if and only if their images in the embedding are at distance in the interval $$[R_1, R_2]$$ [ R 1 , R 2 ] . In this paper we show that the family $$\mathcal A_d(R_1,R_2)$$ A d ( R 1 , R 2 ) of d-dimensional annulus graphs with radii $$R_1$$ R 1 and $$R_2$$ R 2 is uniquely characterised by $$R_2/R_1$$ R 2 / R 1 when this ratio is sufficiently large. Moreover, as a step towards a better understanding of the structure of $$\mathcal A_d(R_1,R_2)$$ A d ( R 1 , R 2 ) , we show that $$\sup _{G\in \mathcal A_d(R_1,R_2)} \chi (G)/\omega (G)$$ sup G ∈ A d ( R 1 , R 2 ) χ ( G ) / ω ( G ) is given by $$\exp (O(d))$$ exp ( O ( d ) ) for all $$R_1,R_2$$ R 1 , R 2 satisfying $$R_2\ge R_1 > 0$$ R 2 ≥ R 1 > 0 and also $$\exp (\Omega (d))$$ exp

Abstract. We show that for every [Formula: see text], the maximal running time of the [Formula: see text]-bootstrap percolation in the complete [Formula: see text]-uniform hypergraph on [Formula: see text] vertices [Formula: see text] is [Formula: see text]. This answers a recent question of Noel and Ranganathan in the affirmative and disproves a conjecture of theirs. Moreover, we show that the prefactor is of the form [Formula: see text] as [Formula: see text].

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost-regular, uniform hypergraph H with small maximum codegree has an almost-perfect matching. We extend this result by obtaining a conflict-free matching, where conflicts are encoded via a collection C of subsets C ⊆ E (H). We say that a matching M ⊆ E (H) is conflict-free if M does not contain an element of C as a subset. Under natural assumptions on C, we prove that H has a conflict-free, almost-perfect matching. This has many applications, one of which yields new asymptotic results for so-called “high-girth” Steiner systems. Our main tool is a polynomial time random greedy algorithm which we call the “conflict-free matching process”. * The full version of the paper can be accessed at https://arxiv.org/abs/2205.05564

In this paper we consider a variant of the well-known Achlioptas process for graphs adapted to monotone Boolean functions. Fix a number of choices $r\in \mathbb N$ and a sequence of increasing functions $(f_n)_{n\ge 1}$ such that, for every $n\ge 1$, $f_n:\{0,1\}^n\mapsto \{0,1\}$. Given $n$ bits which are all initially equal to 0, at each step $r$ 0-bits are sampled uniformly at random and are proposed to an agent. Then, the agent selects one of the proposed bits and turns it from 0 to 1 with the goal to reach $f_n^{-1}(1)$ as quickly as possible. We nearly characterize the conditions on $(f_n)_{n\ge 1}$ under which an acceleration by a factor of $r(1+o(1))$ is possible and underline the wide applicability of our results by giving examples from the fields of Boolean functions and graph theory.