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).

Abstract We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard basis vectors and their projections onto eigenspaces of the adjacency matrix. We provide a purely combinatorial characterization of this hierarchy in terms of the walk counts. This allows us to give a complete answer to Fürer's question about the strength of his invariants in distinguishing non-isomorphic graphs in comparison with the 2-dimensional Weisfeiler-Leman algorithm, extending the recent work of Rattan and Seppelt (SODA 2023). As another application of the characterization, we prove that almost all graphs are determined up to isomorphism in terms of the spectrum and the angles, which is of interest in view of the long-standing open problem whether almost all graphs are determined by their eigenvalues alone. Finally, we describe the exact relationship between the hierarchy and the Weisfeiler-Leman algorithms for small dimensions, as also some other important spectral characteristics of a graph such as the generalized and the main spectra.

In this note we explore the color refinement procedure — also known as the 1-dimensional Weisfeiler-Leman procedure, well-studied in connection with the Graph Isomorphism problem — in the context of the Graph Reconstruction conjecture of Ulam. A basic fact about the Ulam reconstruction conjecture is that the connectedness of a graph is determined by the deck of its vertex-deleted subgraphs, which are considered up to isomorphism. We strengthen this result by proving that connectedness of a graph can even be determined from the deck of its vertex-deleted subgraphs given only by their stable colorings (i.e., up to equivalence under color refinement). It follows as a consequence that connectedness is recognizable by Reconstruction Graph Neural Networks, which is a recently introduced GNN architecture inspired by the reconstruction conjecture (Cotta, Morris, Ribeiro 2021).

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.

We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard basis vectors and their projections onto eigenspaces of the adjacency matrix. We provide a purely combinatorial characterization of this hierarchy in terms of the walk counts. This allows us to give a complete answer to Fürer's question about the strength of his invariants in distinguishing non-isomorphic graphs in comparison to the 2-dimensional Weisfeiler-Leman algorithm, extending the recent work of Rattan and Seppelt (SODA 2023). As another application of the characterization, we prove that almost all graphs are determined up to isomorphism in terms of the spectrum and the angles, which is of interest in view of the long-standing open problem whether almost all graphs are determined by their eigenvalues alone. Finally, we describe the exact relationship between the hierarchy and the Weisfeiler-Leman algorithms for small dimensions, as also some other important spectral characteristics of a graph such as the generalized and the main spectra.

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.

As is well known, the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical two-dimensional Weisfeiler--Leman algorithm (2-WL). On the other hand, the prominent Cai--Fürer--Immerman construction shows that even the multidimensional version of the algorithm does not suffice for graphs with color multiplicity 4. We give an efficient decision procedure that, given a graph $G$ of color multiplicity 4, recognizes whether or not $G$ is identifiable by 2-WL, that is, whether or not 2-WL distinguishes $G$ from every nonisomorphic graph. In fact, we solve the much more general problem of recognizing whether or not a given coherent configuration of maximum fiber size 4 is separable. This extends our recognition algorithm to graphs of color multiplicity 4 with directed and colored edges. Our decision procedure is based on an explicit description of the class of graphs with color multiplicity 4 that are not identifiable by 2-WL. The Cai--Fürer--Immerman graphs of color multiplicity 4 distinctly appear here as a natural subclass, which demonstrates that the Cai--Fürer--Immerman construction is not ad hoc. Our classification reveals also other types of graphs that are hard for 2-WL. One of them arises from patterns known as $(n_3)$-configurations in incidence geometry.

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.

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.

Given a connected graph G and its vertex x, let U(G,x) denote the universal cover of G obtained by unfolding G into a tree starting from x. Let T=T(n) be the minimum number such that, for graphs G and H with at most n vertices each, the isomorphism of U(G,x) and U(H,y) surely follows from the isomorphism of these rooted trees truncated at depth T. Motivated by applications in theory of distributed computing, Norris [Discrete Appl. Math. 1995] asks if the value of T(n) is bounded by n. We answer this question in the negative by establishing that T(n)=(2-o(1))n. Our solution uses basic tools of finite model theory such as a bisimulation version of the Immerman-Lander 2-pebble counting game. The graphs G and H we construct for each n to prove the lower bound for T(n) also show some other tight lower bounds. Both having n vertices, G and H can be distinguished in 2-variable counting logic only with quantifier depth (1-o(1))n. It follows that color refinement, the classical procedure used in isomorphism testing and other areas for computing the coarsest equitable partition of a graph, needs (1-o(1))n rounds to achieve color stabilization on each of G and H. Somewhat surprisingly, this number of rounds is not enough for color stabilization on the disjoint union of G and H, where (2-o(1))n rounds are needed.

Given two structures G and H distinguishable in FO k (first-order logic with k variables), let A k ( G , H ) denote the minimum alternation depth of a FO k formula distinguishing G from H . Let A k ( n ) be the maximum value of A k ( G , H ) over n -element structures. We prove the strictness of the quantifier alternation hierarchy of FO 2 in a strong quantitative form, namely A 2 ( n ) > n /8 − 2, which is tight up to a constant factor. For each k ⩾ 2, it holds that A k ( n ) > log k + 1 n − 2 even over colored trees, which is also tight up to a constant factor if k ⩾ 3. For k ⩾ 3, the last lower bound holds also over uncolored trees, whereas the alternation hierarchy of FO 2 collapses even over all uncolored graphs. We also show examples of colored graphs G and H on n vertices that can be distinguished in FO 2 much more succinctly if the alternation number is increased just by one: Whereas in Σ i it is possible to distinguish G from H with bounded quantifier depth, in Π i this requires quantifier depth Ω( n 2 ). The quadratic lower bound is best possible here because, if G and H can be distinguished in FO k with i quantifier alternations, this can be done with quantifier depth n 2 k − 2 + 1 and the same number of alternations.

Given two structures G and H distinguishable in FO^k (first-order logic with k variables), let A^k(G,H) denote the minimum alternation depth of a FO^k formula distinguishing G from H. Let A^k(n) be the maximum value of A^k(G,H) over n-element structures. We prove the strictness of the quantifier alternation hierarchy of FO^2 in a strong quantitative form, namely A^2(n) >= n/8-2, which is tight up to a constant factor. For each k >= 2, it holds that A^k(n) > log_(k+1) n-2 even over colored trees, which is also tight up to a constant factor if k >= 3. For k >= 3 the last lower bound holds also over uncolored trees, while the alternation hierarchy of FO^2 collapses even over all uncolored graphs. We also show examples of colored graphs G and H on n vertices that can be distinguished in FO^2 much more succinctly if the alternation number is increased just by one: while in Sigma_i it is possible to distinguish G from H with bounded quantifier depth, in Pi_i this requires quantifier depth Omega(n2). The quadratic lower bound is best possible here because, if G and H can be distinguished in FO^k with i quantifier alternations, this can be done with quantifier depth n^(2k-2).

We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where canonical means that isomorphic graphs receive identical models. This implies that the recognition and the isomorphism problems for these graphs are solvable in logspace. For the broader class of concave-round graphs, which still possess (not necessarily proper) circular-arc models, we show that a canonical circular-arc model can also be constructed in logspace. As a building block for these results, we design a logspace algorithm for computing canonical circular-arc models of circular-arc hypergraphs; this important class of hypergraphs corresponds to matrices with the circular ones property. Furthermore, we consider the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We show that this problem is solvable in logarithmic space for the classes of proper circular-arc, concave-round, and co-convex graphs.

We present a logspace algorithm for computing a canonical labeling, in fact, a canonical interval representation, for interval graphs. To achieve this, we compute canonical interval representations of interval hypergraphs. This approach also yields a canonical labeling of convex graphs. As a consequence, the isomorphism and automorphism problems for these graph classes are solvable in logspace. For proper interval graphs we also design logspace algorithms computing their canonical representations by proper and by unit interval systems.

We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is s‐chromatic if it is colorable in s colors and any coloring of it uses at least s colors. The forcing chromatic number $F_{\chi}(G)$ of an s‐chromatic graph G is the smallest number of vertices which must be colored so that, with the restriction that s colors are used, every remaining vertex has its color determined uniquely. We estimate the computational complexity of $\force G$ relating it to the complexity class US introduced by Blass and Gurevich [Inform. Control, 55 (1982), pp. 80–88]. We prove that recognizing whether $F_{\chi}(G)\le2$ is US‐hard with respect to polynomial‐time many‐one reductions. Moreover, this problem is coNP‐hard even under the promises that $F_{\chi}(G)\le3$ and G is 3‐chromatic. On the other hand, recognizing whether $F_{\chi}(G)\le k$, for each constant k, is reducible to a problem in US via a disjunctive truth‐table reduction. Similar results are obtained also for forcing variants of the clique and the domination numbers of a graph.

Abstract We say that a first order formula Φ distinguishes a structure M over a vocabulary L from another structure M′ over the same vocabulary if Φ is true on M but false on M′. A formula Φ defines an L-structure M if Φ distinguishes M from any other non-isomorphic L-structure M′. A formula Φ identifies an n-element L-structure M if Φ distinguishes M from any other non-isomorphic n-element L-structure M′. We prove that every n-element structure M is identifiable by a formula with quantifier rank less than and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification. The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than quantifiers suffice to identify M and. as long as we keep the number of universal quantifiers bounded by a constant, at total quantifiers are necessary.

We show that no fixed number of parallel repetitions suffices in order to reduce the error in two-prover one-round proof systems from one constant to another. Our results imply that the recent bounds proven by Ran Raz (1995), showing that the number of rounds that suffice is inversely proportional to the answer length, are nearly best possible.