We consider the community detection problem in sparse random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), a general model of random networks with community structure and higher-order interactions. When the random hypergraph has bounded expected degrees, we provide a spectral algorithm that outputs a partition with at least a $\gamma$ fraction of the vertices classified correctly, where $\gamma \in (0.5,1)$ depends on the signal-to-noise ratio (SNR) of the model. When the SNR grows slowly as the number of vertices goes to infinity, our algorithm achieves weak consistency, which improves the previous results in Ghoshdastidar and Dukkipati ((2017) Ann. Stat. 45(1) 289–315.) for non-uniform HSBMs.

Our spectral algorithm consists of three major steps: (1) Hyperedge selection: select hyperedges of certain sizes to provide the maximal signal-to-noise ratio for the induced sub-hypergraph; (2) Spectral partition: construct a regularised adjacency matrix and obtain an approximate partition based on singular vectors; (3) Correction and merging: incorporate the hyperedge information from adjacency tensors to upgrade the error rate guarantee. The theoretical analysis of our algorithm relies on the concentration and regularisation of the adjacency matrix for sparse non-uniform random hypergraphs, which can be of independent interest.

For given positive integers $r\ge 3$, $n$ and $e\le \binom{n}{2}$, the famous Erdős–Rademacher problem asks for the minimum number of $r$-cliques in a graph with $n$ vertices and $e$ edges. A conjecture of Lovász and Simonovits from the 1970s states that, for every $r\ge 3$, if $n$ is sufficiently large then, for every $e\le \binom{n}{2}$, at least one extremal graph can be obtained from a complete partite graph by adding a triangle-free graph into one part.

In this note, we explicitly write the minimum number of $r$-cliques predicted by the above conjecture. Also, we describe what we believe to be the set of extremal graphs for any $r\ge 4$ and all large $n$, amending the previous conjecture of Pikhurko and Razborov.

We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core model, a well-studied discrete spin system. Given an instance of such a point process, our reduction generates a random graph drawn from a natural geometric model. We show that the partition function of a hard-core model on graphs generated by the geometric model concentrates around the partition function of the Gibbs point process. Our reduction allows us to use a broad range of algorithms developed for the hard-core model to sample from the Gibbs point process and approximate its partition function. This is, to the extent of our knowledge, the first approach that deals with pair potentials of unbounded range.

We use Stein’s method to obtain distributional approximations of subgraph counts in the uniform attachment model or random directed acyclic graph; we provide also estimates of rates of convergence. In particular, we give uni- and multi-variate Poisson approximations to the counts of cycles and normal approximations to the counts of unicyclic subgraphs; we also give a partial result for the counts of trees. We further find a class of multicyclic graphs whose subgraph counts are a.s. bounded as $n\to \infty$.

Given an $n\times n$ symmetric matrix $W\in [0,1]^{[n]\times [n]}$, let ${\mathcal G}(n,W)$ be the random graph obtained by independently including each edge $jk\in \binom{[n]}{2}$ with probability $W_{jk}=W_{kj}$. Given a degree sequence $\textbf{d}=(d_1,\ldots, d_n)$, let ${\mathcal G}(n,\textbf{d})$ denote a uniformly random graph with degree sequence $\textbf{d}$. We couple ${\mathcal G}(n,W)$ and ${\mathcal G}(n,\textbf{d})$ together so that asymptotically almost surely ${\mathcal G}(n,W)$ is a subgraph of ${\mathcal G}(n,\textbf{d})$, where $W$ is some function of $\textbf{d}$. Let $\Delta (\textbf{d})$ denote the maximum degree in $\textbf{d}$. Our coupling result is optimal when $\Delta (\textbf{d})^2\ll \|\textbf{d}\|_1$, that is, $W_{ij}$ is asymptotic to ${\mathbb P}(ij\in{\mathcal G}(n,\textbf{d}))$ for every $i,j\in [n]$. We also have coupling results for $\textbf{d}$ that are not constrained by the condition $\Delta (\textbf{d})^2\ll \|\textbf{d}\|_1$. For such $\textbf{d}$ our coupling result is still close to optimal, in the sense that $W_{ij}$ is asymptotic to ${\mathbb P}(ij\in{\mathcal G}(n,\textbf{d}))$ for most pairs $ij\in \binom{[n]}{2}$.

The walk matrix associated to an $n\times n$ integer matrix $\mathbf{X}$ and an integer vector $b$ is defined by ${\mathbf{W}} \,:\!=\, (b,{\mathbf{X}} b,\ldots, {\mathbf{X}}^{n-1}b)$. We study limiting laws for the cokernel of $\mathbf{W}$ in the scenario where $\mathbf{X}$ is a random matrix with independent entries and $b$ is deterministic. Our first main result provides a formula for the distribution of the $p^m$-torsion part of the cokernel, as a group, when $\mathbf{X}$ has independent entries from a specific distribution. The second main result relaxes the distributional assumption and concerns the ${\mathbb{Z}}[x]$-module structure.

The motivation for this work arises from an open problem in spectral graph theory, which asks to show that random graphs are often determined up to isomorphism by their (generalised) spectrum. Sufficient conditions for generalised spectral determinacy can, namely, be stated in terms of the cokernel of a walk matrix. Extensions of our results could potentially be used to determine how often those conditions are satisfied. Some remaining challenges for such extensions are outlined in the paper.

Let $r$ be any positive integer. We prove that for every sufficiently large $k$ there exists a $k$-chromatic vertex-critical graph $G$ such that $\chi (G-R)=k$ for every set $R \subseteq E(G)$ with $|R|\le r$. This partially solves a problem posed by Erdős in 1985, who asked whether the above statement holds for $k \ge 4$.