A graph G is called a $(P_{\geq n},k)$ -factor-critical covered graph if for any $Q\subseteq V(G)$ with $|Q|=k$ and any $e\in E(G-Q)$ , $G-Q$ has a $P_{\geq n}$ -factor covering e. We demonstrate that (i) a $(k+1)$ -connected graph G with at least $k+3$ vertices is a $(P_{\geq 3},k)$ -factor-critical covered graph if its toughness $t(G)>{(2+k)}/{3}$ ; (ii) a $(k+2)$ -connected graph G is a $(P_{\geq 3},k)$ -factor-critical covered graph if its isolated toughness $I(G)>{(5+k)}/{3}$ . Furthermore, we show that the conditions on $t(G)$ and $I(G)$ are sharp.

Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $\Delta $ , then for every integer $k \geq \Delta +1$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $1$ ; such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree $\Delta $ , then for each $k \geq \Delta + 1$ , G has a Borel proper k-colouring in which every two colour classes are related by an element of the Borel full semigroup of G. In particular, such colourings are equitable with respect to every G-invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $\Delta $ -colourings of graphs with small average degree. Namely, we prove that if $\Delta \geq 3$ , G does not contain a clique on $\Delta + 1$ vertices and $\mu $ is an atomless G-invariant probability measure such that the average degree of G with respect to $\mu $ is at most $\Delta /5$ , then G has a $\mu $ -equitable $\Delta $ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit.

We study a natural model of a random $2$-dimensional cubical complex which is a subcomplex of an n-dimensional cube, and where every possible square $2$-face is included independently with probability p. Our main result exhibits a sharp threshold $p=1/2$ for homology vanishing as $n \to \infty $. This is a $2$-dimensional analogue of the Burtin and Erdoős–Spencer theorems characterising the connectivity threshold for random graphs on the $1$-skeleton of the n-dimensional cube.

Our main result can also be seen as a cubical counterpart to the Linial–Meshulam theorem for random $2$-dimensional simplicial complexes. However, the models exhibit strikingly different behaviours. We show that if $p> 1 - \sqrt {1/2} \approx 0.2929$, then with high probability the fundamental group is a free group with one generator for every maximal $1$-dimensional face. As a corollary, homology vanishing and simple connectivity have the same threshold, even in the strong ‘hitting time’ sense. This is in contrast with the simplicial case, where the thresholds are far apart. The proof depends on an iterative algorithm for contracting cycles – we show that with high probability, the algorithm rapidly and dramatically simplifies the fundamental group, converging after only a few steps.

A classical theorem of Frucht states that any finite group appears as the automorphism group of a finite graph. In the quantum setting, the problem is to understand the structure of the compact quantum groups which can appear as quantum automorphism groups of finite graphs. We discuss here this question, notably with a number of negative results.

Random intersection graphs model networks with communities, assuming an underlying bipartite structure of communities and individuals, where these communities may overlap. We generalize the model, allowing for arbitrary community structures within the communities. In our new model, communities may overlap, and they have their own internal structure described by arbitrary finite community graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, show local weak convergence (including convergence of subgraph counts), and derive the asymptotic degree distribution and the local clustering coefficient.

In the localization game on a graph, the goal is to find a fixed but unknown target node $v^\star$ with the least number of distance queries possible. In the jth step of the game, the player queries a single node $v_j$ and receives, as an answer to their query, the distance between the nodes $v_j$ and $v^\star$ . The sequential metric dimension (SMD) is the minimal number of queries that the player needs to guess the target with absolute certainty, no matter where the target is.

The term SMD originates from the related notion of metric dimension (MD), which can be defined the same way as the SMD except that the player’s queries are non-adaptive. In this work we extend the results of Bollobás, Mitsche, and Prałat [4] on the MD of Erdős–Rényi graphs to the SMD. We find that, in connected Erdős–Rényi graphs, the MD and the SMD are a constant factor apart. For the lower bound we present a clean analysis by combining tools developed for the MD and a novel coupling argument. For the upper bound we show that a strategy that greedily minimizes the number of candidate targets in each step uses asymptotically optimal queries in Erdős–Rényi graphs. Connections with source localization, binary search on graphs, and the birthday problem are discussed.

We investigate spatial random graphs defined on the points of a Poisson process in d-dimensional space, which combine scale-free degree distributions and long-range effects. Every Poisson point is assigned an independent weight. Given the weight and position of the points, we form an edge between any pair of points independently with a probability depending on the two weights of the points and their distance. Preference is given to short edges and connections to vertices with large weights. We characterize the parameter regime where there is a non-trivial percolation phase transition and show that it depends not only on the power-law exponent of the degree distribution but also on a geometric model parameter. We apply this result to characterize robustness of age-based spatial preferential attachment networks.

Consider a homogeneous Poisson point process of the Euclidean plane and its Voronoi tessellation. The present note discusses the properties of two stationary point processes associated with the latter and depending on a parameter $\theta$ . The first is the set of points that belong to some one-dimensional facet of the Voronoi tessellation and such that the angle with which they see the two nuclei defining the facet is $\theta$ . The main question of interest on this first point process is its intensity. The second point process is that of the intersections of the said tessellation with a straight line having a random orientation. Its intensity is well known. The intersection points almost surely belong to one-dimensional facets. The main question here concerns the Palm distribution of the angle with which the points of this second point process see the two nuclei associated with the facet. We will give answers to these two questions and briefly discuss their practical motivations. We also discuss natural extensions to three dimensions.

Motivated by applications to a wide range of areas, including assemble-to-order systems, operations scheduling, healthcare systems, and the collaborative economy, we study a stochastic matching model on hypergraphs, extending the model of Mairesse and Moyal (J. Appl. Prob.53, 2016) to the case of hypergraphical (rather than graphical) matching structures. We address a discrete-event system under a random input of single items, simply using the system as an interface to be matched in groups of two or more. We primarily study the stability of this model, for various hypergraph geometries.

We prove concentration inequality results for geometric graph properties of an instance of the Cooper–Frieze [5] preferential attachment model with edge-steps. More precisely, we investigate a random graph model that at each time $t\in \mathbb{N}$ , with probability p adds a new vertex to the graph (a vertex-step occurs) or with probability $1-p$ an edge connecting two existent vertices is added (an edge-step occurs). We prove concentration results for the global clustering coefficient as well as the clique number. More formally, we prove that the global clustering, with high probability, decays as $t^{-\gamma(p)}$ for a positive function $\gamma$ of p, whereas the clique number of these graphs is, up to subpolynomially small factors, of order $t^{(1-p)/(2-p)}$ .

Let R be a commutative ring with identity which is not an integral domain. An ideal I of R is called an annihilating ideal if there exists $r\in R- \{0\}$ such that $Ir=(0)$ . The total graph of nonzero annihilating ideals of R is the graph $\Omega (R)$ whose vertices are the nonzero annihilating ideals of R and two distinct vertices $I,J$ are joined if and only if $I+J$ is also an annihilating ideal of R. We study the strong metric dimension of $\Omega (R)$ and evaluate it in several cases.

Using a variation of the rainbow construction and various pebble and colouring games, we prove that RRA, the class of all representable relation algebras, cannot be axiomatised by any first-order relation algebra theory of bounded quantifier depth. We also prove that the class At(RRA) of atom structures of representable, atomic relation algebras cannot be defined by any set of sentences in the language of RA atom structures that uses only a finite number of variables.

The Bollobás–Riordan (BR) polynomial [(2002), Math. Ann.323 81] is a universal polynomial invariant for ribbon graphs. We find an extension of this polynomial for a particular family of combinatorial objects, called rank 3 weakly coloured stranded graphs. Stranded graphs arise in the study of tensor models for quantum gravity in physics, and generalize graphs and ribbon graphs. We present a seven-variable polynomial invariant of these graphs, which obeys a contraction/deletion recursion relation similar to that of the Tutte and BR polynamials. However, it is defined on a much broader class of objects, and furthermore captures properties that are not encoded by the Tutte or BR polynomials.

We consider groupoids constructed from a finite number of commuting local homeomorphisms acting on a compact metric space and study generalized Ruelle operators and $ C^{\ast } $ -algebras associated to these groupoids. We provide a new characterization of $ 1 $ -cocycles on these groupoids taking values in a locally compact abelian group, given in terms of $ k $ -tuples of continuous functions on the unit space satisfying certain canonical identities. Using this, we develop an extended Ruelle–Perron–Frobenius theory for dynamical systems of several commuting operators ( $ k $ -Ruelle triples and commuting Ruelle operators). Results on KMS states on $ C^{\ast } $ -algebras constructed from these groupoids are derived. When the groupoids being studied come from higher-rank graphs, our results recover existence and uniqueness results for KMS states associated to the graphs.

In this work we analyse bucket increasing tree families. We introduce two simple stochastic growth processes, generating random bucket increasing trees of size n, complementing the earlier result of Mahmoud and Smythe (1995, Theoret. Comput. Sci.144 221–249.) for bucket recursive trees. On the combinatorial side, we define multilabelled generalisations of the tree families d-ary increasing trees and generalised plane-oriented recursive trees. Additionally, we introduce a clustering process for ordinary increasing trees and relate it to bucket increasing trees. We discuss in detail the bucket size two and present a bijection between such bucket increasing tree families and certain families of graphs called increasing diamonds, providing an explanation for phenomena observed by Bodini et al. (2016, Lect. Notes Comput. Sci.9644 207–219.). Concerning structural properties of bucket increasing trees, we analyse the tree parameter $K_n$ . It counts the initial bucket size of the node containing label n in a tree of size n and is closely related to the distribution of node types. Additionally, we analyse the parameters descendants of label j and degree of the bucket containing label j, providing distributional decompositions, complementing and extending earlier results (Kuba and Panholzer (2010), Theoret. Comput. Sci.411(34–36) 3255–3273.).

We consider the component structure of the random digraph D(n,p) inside the critical window $p = n^{-1} + \lambda n^{-4/3}$ . We show that the largest component $\mathcal{C}_1$ has size of order $n^{1/3}$ in this range. In particular we give explicit bounds on the tail probabilities of $|\mathcal{C}_1|n^{-1/3}$ .

We define a new ribbon group action on ribbon graphs that uses a semidirect product of a permutation group and the original ribbon group of Ellis-Monaghan and Moffatt to take (partial) twists and duals, or twuals, of ribbon graphs. A ribbon graph is a fixed point of this new ribbon group action if and only if it is isomorphic to one of its (partial) twuals. This extends the original ribbon group action, which only used the canonical identification of edges, to the more natural setting of self-twuality up to isomorphism. We then show that every ribbon graph has in its orbit an orientable embedded bouquet and prove that the (partial) twuality properties of these bouquets propagate through their orbits. Thus, we can determine (partial) twualities via these one vertex graphs, for which checking isomorphism reduces simply to checking dihedral group symmetries. Finally, we apply the new ribbon group action to generate all self-trial ribbon graphs on up to seven edges, in contrast with the few, large, very high-genus, self-trial regular maps found by Wilson, and by Jones and Poultin. We also show how the automorphism group of a ribbon graph yields self-dual, -petrial or –trial graphs in its orbit, and produce an infinite family of self-trial graphs that do not arise as covers or parallel connections of regular maps, thus answering a question of Jones and Poulton.

Motivated by analogous questions in the setting of Steiner triple systems and Latin squares, Nenadov, Sudakov and Wagner [Completion and deficiency problems, Journal of Combinatorial Theory Series B, 2020] recently introduced the notion of graph deficiency. Given a global spanning property $\mathcal P$ and a graph $G$ , the deficiency $\text{def}(G)$ of the graph $G$ with respect to the property $\mathcal P$ is the smallest non-negative integer t such that the join $G*K_t$ has property $\mathcal P$ . In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an n-vertex graph $G$ needs to ensure $G*K_t$ contains a $K_r$ -factor (for any fixed $r\geq 3$ ). In this paper, we resolve their problem fully. We also give an analogous result that forces $G*K_t$ to contain any fixed bipartite $(n+t)$ -vertex graph of bounded degree and small bandwidth.

Kostochka and Thomason independently showed that any graph with average degree $\Omega(r\sqrt{\log r})$ contains a $K_r$ minor. In particular, any graph with chromatic number $\Omega(r\sqrt{\log r})$ contains a $K_r$ minor, a partial result towards Hadwiger’s famous conjecture. In this paper, we investigate analogues of these results in the directed setting. There are several ways to define a minor in a digraph. One natural way is as follows. A strong $\overrightarrow{K}_{\!\!r}$ minor is a digraph whose vertex set is partitioned into r parts such that each part induces a strongly connected subdigraph, and there is at least one edge in each direction between any two distinct parts. We investigate bounds on the dichromatic number and minimum out-degree of a digraph that force the existence of strong $\overrightarrow{K}_{\!\!r}$ minors as subdigraphs. In particular, we show that any tournament with dichromatic number at least 2r contains a strong $\overrightarrow{K}_{\!\!r}$ minor, and any tournament with minimum out-degree $\Omega(r\sqrt{\log r})$ also contains a strong $\overrightarrow{K}_{\!\!r}$ minor. The latter result is tight up to the implied constant and may be viewed as a strong-minor analogue to the classical result of Kostochka and Thomason. Lastly, we show that there is no function $f\;:\;\mathbb{N} \rightarrow \mathbb{N}$ such that any digraph with minimum out-degree at least f(r) contains a strong $\overrightarrow{K}_{\!\!r}$ minor, but such a function exists when considering dichromatic number.