We estimate the minimum number of distance queries that is sufficient to reconstruct the binomial random graph G(n,p) with constant diameter with high probability. We get a tight (up to a constant factor) answer for all p > n^{-1+o(1)} outside "threshold windows" around n^{-k/(k+1)+o(1)}, k ∈ ℤ_{> 0}: with high probability the query complexity equals Θ(n^{4-d}p^{2-d}), where d is the diameter of the random graph. This demonstrates the following non-monotone behaviour: the query complexity jumps down at moments when the diameter gets larger; yet, between these moments the query complexity grows. We also show that there exists a non-adaptive algorithm that reconstructs the random graph with O(n^{4-d}p^{2-d}ln n) distance queries with high probability, and this is best possible.

We show that for every ε > 0 there exists a sufficiently large d₀ ∈ ℕ such that for every d ≥ d₀, whp the random d-regular graph G(n,d) contains a T-factor for every tree T on at most (1-ε)d/log d vertices. This is best possible since, for large enough integer d, whp G(n,d) does not contain a ((1+ε)d)/(log d)-star-factor. Our method gives a randomised algorithm which whp finds said T-factor and whose expected running time is O(n^{1+o(1)}), as well as an efficient deterministic counterpart.

We show that if p = O(1/n), then the Erdős-Rényi random graph G(n,p) with high probability admits a canonical labeling computable in time O(nlog n). Combined with the previous results on the canonization of random graphs, this implies that G(n,p) with high probability admits a polynomial-time canonical labeling whatever the edge probability function p. Our algorithm combines the standard color refinement routine with simple post-processing based on the classical linear-time tree canonization. Noteworthy, our analysis of how well color refinement performs in this setting allows us to complete the description of the automorphism group of the 2-core of G(n,p).

We prove that the density of any covering singleinsertion codeC⊆Xrover then-symbol alphabet X cannot be smaller than 1/r+ δrfor some positive real δrnot depending onn. This improves the volume lower bound of 1=(r+ 1). On the other hand, we observe that, for all sufficiently larger, ifntends to infinity then the asymptotic upper bound of 7=(r+ 1) due to Lenz et al. (2021) can be improved to 4.911=(r+ 1). Both the lower and the upper bounds are achieved by relating the code density to the Turán density from extremal combinatorics. For the last task, we use the analytic framework of measurable subsets of the real cube [0; 1]r.

A class of graphs admits an adjacency labeling scheme of size $b(n)$, if the vertices in each of its $n$-vertex graphs can be assigned binary strings (called labels) of length $b(n)$ so that the adjacency of two vertices can be determined solely from their labels. We give tight bounds on the size of adjacency labels for every family of monotone (i.e., subgraph-closed) classes with a well-behaved growth function between $2^{O(n \log n)}$ and $2^{O(n^{2-δ})}$ for any $δ> 0$. Specifically, we show that for any function $f: \mathbb N \to \mathbb R$ satisfying $\log n \leqslant f(n) \leqslant n^{1-δ}$ for any fixed $δ> 0$, and some~sub-multiplicativity condition, there are monotone graph classes with growth $2^{O(nf(n))}$ that do not admit adjacency labels of size at most $f(n) \log n$. On the other hand, any such class does admit adjacency labels of size $O(f(n)\log n)$. Surprisingly this tight bound is a $Θ(\log n)$ factor away from the information-theoretic bound of $Ω(f(n))$. The special case when $f = \log$ implies that the recently-refuted Implicit Graph Conjecture [Hatami and Hatami, FOCS 2022] also fails within monotone classes. We further show that the Implicit Graph Conjecture holds for all monotone \emph{small} classes. In other words, any monotone class with growth rate at most $n!\,c^n$ for some constant $c>0$, admits adjacency labels of information-theoretic order optimal size. In fact, we show a more general result that is of independent interest: any monotone small class of graphs has bounded degeneracy.We conjecture that the Implicit Graph Conjecture holds for all hereditary small classes.

For a sequence of random structures with n-element domains over a relational signature, we define its FO complexity as a certain subset in the Banach space ℓ∞/c0. The well-known FO zero-one law and FO convergence law correspond to FO complexities equal to {0, 1} and a subset of R, respectively. We present a hierarchy of FO complexity classes, introduce a stochastic FO reduction that allows to transfer complexity results between different random structures, and deduce using this tool several new logical limit laws for binomial random structures. Finally, we introduce a conditional distribution on graphs, subject to a FO sentence ϕ, that generalises certain well-known random graph models, show instances of this distribution for every complexity class, and prove that the set of all ϕ validating 0--1 law is not recursively enumerable.

We study the problem of distinguishing between two independent samples [EQUATION], [EQUATION] of a binomial random graph G(n, p) by first order (FO) sentences. Shelah and Spencer proved that, for a constant α ∈ (0, 1), G(n, n−-α) obeys FO zero-one law if and only if α is irrational. Therefore, for irrational α ∈ (0, 1), any fixed FO sentence does not distinguish between [EQUATION] with asymptotical probability 1 (w.h.p.) as n → ∞. We show that the minimum quantifier depth kα of a FO sentence [EQUATION] distinguishing between [EQUATION] depends on how closely α can be approximated by rationals:

We show that for any natural number s, there is a constant γ and a subgraph-closed class having, for any natural n, at most γn graphs on n vertices up to isomorphism, but no adjacency labeling scheme with labels of size at most s log n. In other words, for every s, there is a small -even tiny - monotone class without universal graphs of size ns. Prior to this result, it was not excluded that every small class has an almost linear universal graph, or equivalently a labeling scheme with labels of size (1 + o(1))log n. The existence of such a labeling scheme, a scaled-down version of the recently disproved Implicit Graph Conjecture, was repeatedly raised [Gavoille and Labourel, ESA ‘07; Dujmović et al., JACM ‘21; Bonamy et al., SIDMA ‘22; Bonnet et al., Comb. Theory ‘22]. Furthermore, our small monotone classes have unbounded twin-width, thus simultaneously disprove the already-refuted Small conjecture; but this time with a self-contained proof, not relying on elaborate group-theoretic constructions.

Abstract. We show that for any natural number [Formula: see text], there is a constant [Formula: see text] and a subgraph-closed class having, for any natural [Formula: see text], at most [Formula: see text] graphs on [Formula: see text] vertices up to isomorphism, but no adjacency labeling scheme with labels of size at most [Formula: see text]. In other words, for every [Formula: see text], there is a small—even tiny—monotone class without universal graphs of size [Formula: see text]. Prior to this result, it was not excluded that every small class has an almost linear universal graph, or equivalently a labeling scheme with labels of size [Formula: see text]. The existence of such a labeling scheme, a scaled-down version of the recently disproved Implicit Graph Conjecture, was repeatedly raised [Gavoille and Labourel, Proceedings of the 15 th Annual European Symposium on Algorithms, Lecture Notes in Comput. Sci. 4698, Springer, 2007, pp. 582–593; Dujmović et al., J. ACM, 68 (2021), pp. 1–33; Bonamy, Gavoille, and Pilipczuk, SIAM J. Discrete Math., 36 (2022), pp. 2082–2099; Bonnet et al., Comb. Theory, 2 (2022)]. Furthermore, our small monotone classes have unbounded twin-width and thus simultaneously disprove the already-refuted Small conjecture, but this time with a self-contained proof, not relying on elaborate group-theoretic constructions. As our main ingredient, we show that with high probability an Erdős–Rényi random graph [Formula: see text] with [Formula: see text] has, for every [Formula: see text], at most [Formula: see text] subgraphs on [Formula: see text] vertices, up to isomorphism. As a barrier to our general method of producing even more complex tiny classes, we show that when [Formula: see text], the latter no longer holds. More concretely, we provide an explicit lower bound on the number of unlabeled [Formula: see text]-vertex induced subgraphs of [Formula: see text] when [Formula: see text]. We thereby obtain a threshold for the property of having exponentially many unlabeled induced subgraphs: if [Formula: see text] with [Formula: see text], then with high probability even the number of all unlabeled (not necessarily induced) subgraphs is [Formula: see text], whereas if [Formula: see text] for sufficiently large [Formula: see text], then with high probability the number of unlabeled induced subgraphs is [Formula: see text]. This result supplements the study of counting unlabeled induced subgraphs that was initiated by Erdős and Rényi with a question on the number of unlabeled induced subgraphs of Ramsey graphs, eventually answered by Shelah.

Abstract. We study vulnerability of a uniformly distributed random graph to an attack by an adversary who aims for a global change of the distribution while being able to make only a local change in the graph. We call a graph property [Formula: see text] antistochastic if the probability that a random graph [Formula: see text] satisfies [Formula: see text] is small but, with high probability, there is a small perturbation transforming [Formula: see text] into a graph satisfying [Formula: see text]. While for labeled graphs such properties are easy to obtain from binary covering codes, the existence of antistochastic properties for unlabeled graphs or, in other words, isomorphism-invariant antistochastic properties, is not so evident. If an admissible perturbation is either the addition or the deletion of one edge, we exhibit an isomorphism-invariant antistochastic property that is satisfied by a random graph of order [Formula: see text] with probability [Formula: see text], which is as small as possible. We also express another antistochastic property in terms of the degree sequence of a graph. This property has probability [Formula: see text], which is optimal up to a factor of 2.

Abstract. It is known that after an appropriate rescaling the maximum degree of the binomial random graph converges in distribution to a Gumbel random variable. The same holds true for the maximum number of common neighbors of a [Formula: see text]-vertex set and for the maximum number of [Formula: see text]-cliques sharing a single vertex. Can these results be generalized to the maximum number of extensions of a [Formula: see text]-vertex set for any given way of extending a [Formula: see text]-vertex set by an [Formula: see text]-vertex set? In this paper, we generalize the abovementioned results to a class of “symmetric extensions” and show that the limit distribution is not necessarily from the Gumbel family.

The k -spectrum is the set of all α > 0 such that G(n,n −α ) does not obey the 0-1 law for FO sentences with quantifier depth at most k . In this article, we prove that the minimum k such that the k -spectrum is infinite equals 5.

Abstract. For a fixed graph [Formula: see text] the minimum number of edges in an edge-maximal [Formula: see text]-free subgraph of [Formula: see text] is called the [Formula: see text]-saturation number. The asymptotics of the [Formula: see text]-saturation number of the binomial random graph [Formula: see text] for constant [Formula: see text] is known for complete graphs [Formula: see text] and stars [Formula: see text]. This paper is devoted to the case when the pattern graph [Formula: see text] is a simple cycle [Formula: see text]. We prove that, for [Formula: see text] with high probability (whp) [Formula: see text]. Also we find [Formula: see text] such that whp [Formula: see text]. In particular, whp [Formula: see text].

In this paper, we disprove EMSO(FO$^2$) convergence law for the binomial random graph $G(n,p)$ for any constant probability $p$. More specifically, we prove that there exists an existential monadic second order sentence with 2 first order variables such that, for every $p\in(0,1)$, the probability that it is true on $G(n,p)$ does not converge.

For any fixed positive integer k , let α k denote the smallest α ∈ (0,1) such that the random graph sequence { G ( n, n -α )} n does not satisfy the zero-one law for the set ε k of all existential first-order sentences that are of quantifier depth at most k . This article finds upper and lower bounds on α k , showing that as k → ∞, we have α k = ( k - 2 - t ( k )) -1 for some function t ( k ) = Θ ( k -2 ). We also establish the precise value of α k when k = 4.

Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is definable in $k$-variable first-order logic. The recognition problem of $I(F)$, known as Induced Subgraph Isomorphism (for the pattern graph $F$), is solvable in time $O(n^{W[F]})$. Motivated by this fact, we are interested in determining or estimating the value of $W[F]$. Using Olariu's characterization of paw-free graphs, we show that $I(K_3+e)$ is definable by a first-order sentence of quantifier depth 3, where $K_3+e$ denotes the paw graph. This provides an example of a graph $F$ with $W[F]$ strictly less than the number of vertices in $F$. On the other hand, we prove that $W[F]=4$ for all $F$ on 4 vertices except the paw graph and its complement. If $F$ is a graph on $t$ vertices, we prove a general lower bound $W[F]>(1/2-o(1))t$, where the function in the little-o notation approaches 0 as $t$ inreases. This bound holds true even for a related parameter $W^*[F]\le W[F]$, which is defined as the minimum $k$ such that $I(F)$ is definable in the infinitary logic $L^k_{\infty\omega}$. We show that $W^*[F]$ can be strictly less than $W[F]$. Specifically, $W^*[P_4]=3$ for $P_4$ being the path graph on 4 vertices. Using the lower bound for $W[F]$, we also obtain a succintness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate.

Let v ( F ) denote the number of vertices in a fixed connected pattern graph F . We show an infinite family of patterns F such that the existence of a subgraph isomorphic to F is expressible by a first-order sentence of quantifier depth 2/3 v ( F ) + 1, assuming that the host graph is sufficiently large and connected. However, this is impossible for any F using less than 2/3 v ( F ) - 2 first-order variables.

In this paper, we study zero-one laws for the Erdös--Rényi random graph model $G(n,p)$ in the case when $p = n^{-\alpha}$ for $\alpha>0$. For a given class $\mathcal{K}$ of logical sentences about graphs and a given function $p=p(n)$, we say that $G(n,p)$ obeys the zero-one law (w.r.t. the class $\mathcal{K}$) if each sentence $\varphi\in\mathcal{K}$ is either asymptotically almost surely (a.a.s.) true or a.a.s. false for $G(n,p)$. In this paper, we consider first order properties and monadic second order properties of bounded quantifier depth $k$, that is, the length of the longest chain of nested quantifiers in the formula expressing the property. We call zero-one laws for properties of quantifier depth $k$ the zero-one $k$-laws. The main results of this paper concern the zero-one $k$-laws for monadic second order (MSO) properties. We determine all values $\alpha>0$, for which the zero-one $3$-law for MSO properties does not hold. We also show that, in contrast to the case of the $3$-law, there are infinitely many values of $\alpha$ for which the zero-one $4$-law for MSO properties does not hold. To this end, we analyze the evolution of certain properties of $G(n,p)$ that may be of independent interest.

Given a graph F, let I(F) be the class of graphs containing F as an induced subgraph. Let W[F] denote the minimum k such that I(F) is definable in k-variable first-order logic. The recognition problem of I(F), known as Induced Subgraph Isomorphism (for the pattern graph F), is solvable in time O(n^{W[F]}). Motivated by this fact, we are interested in determining or estimating the value of W[F]. Using Olariu's characterization of paw-free graphs, we show that I(K_3+e) is definable by a first-order sentence of quantifier depth 3, where K_3+e denotes the paw graph. This provides an example of a graph F with W[F] strictly less than the number of vertices in F. On the other hand, we prove that W[F]=4 for all F on 4 vertices except the paw graph and its complement. If F is a graph on t vertices, we prove a general lower bound W[F]>(1/2-o(1))t, where the function in the little-o notation approaches 0 as t increases. This bound holds true even for a related parameter W^*[F], which is defined as the minimum k such that I(F) is definable in the k-variable infinitary logic. We show that W^*[F] can be strictly less than W[F]. Specifically, W^*[P_4]=3 for P_4 being the path graph on 4 vertices.

In this paper, we consider a non-convex loss-minimization problem of learning Supervised PageRank models, which can account for features of nodes and edges. We propose gradient-based and random gradient-free methods to solve this problem. Our algorithms are based on the concept of an inexact oracle and unlike the state-of-the-art gradient-based method we manage to provide theoretically the convergence rate guarantees for both of them. Finally, we compare the performance of the proposed optimization methods with the state of the art applied to a ranking task.