Search

We consider the voter model with binary opinions on a random regular graph with $n$ vertices of degree $d \geq 3$, subject to a rewiring dynamics in which pairs of edges are rewired, i.e., broken into four half-edges and subsequently reconnected at random. A parameter $\nu \in (0,\infty)$ regulates the frequency at which the rewirings take place, in such a way that any given edge is rewired exponentially at a rate $\nu$ in the limit as $n\to\infty$. We show that, under the joint law of the random rewiring dynamics and the random opinion dynamics, the fraction of vertices with either one of the two opinions converges on time scale $n$ to the Fisher-Wright diffusion with an explicit diffusion constant $\vartheta_{d,\nu}$ in the limit as $n\to\infty$. In particular, we identify $\vartheta_{d,\nu}$ in terms of a continued-fraction expansion and analyse its dependence on $d$ and $\nu$. A key role in our analysis is played by the set of discordant edges, which constitutes the boundary between the sets of vertices carrying the two opinions., Comment: 53 pages

In this paper, we advance the network theory of aging and mortality by developing a causal mathematical model for the mortality rate. First, we show that in large networks, where health deficits accumulate at nodes representing health indicators, the modeling of network evolution with Poisson processes is universal and can be derived from fundamental principles. Second, with the help of two simplifying approximations, which we refer to as mean-field assumption and homogeneity assumption, we provide an analytical derivation of Gompertz law under generic and biologically relevant conditions. We identify the parameters in Gompertz law as a function of the parameters driving the evolution of the network, and illustrate our computations with simulations and analytic approximations., Comment: 28 pages, 10 figure

The present paper is a brief overview of random opinion dynamics on random graphs based on the Ising Lecture given by the author at the World Congress in Probability and Statistics, 12--16 August 2024, Bochum, Germany. The content is a snapshot of an interesting area of research that is developing rapidly., Comment: 13 pages, 11 figures

The present overview of interacting particle systems on random graphs collects the notes of a mini-course given by the authors at the Brazilian School of Probability, 5--9 August 2024, in Salvador, Bahia, Brazil. The content is a personal snapshot of an interesting area of research at the interface between probability theory, combinatorics, statistical physics and network science that is developing rapidly., Comment: 44 pages, 13 figures

We consider two-opinion voter models on dense dynamic random graphs. Our goal is to understand and describe the occurrence of consensus versus polarisation over long periods of time. The former means that all vertices have the same opinion, the latter means that the vertices split into two communities with different opinions and few disagreeing edges. We consider three models for the joint dynamics of opinions and graphs: one with a one-way feedback and two which are co-evolutionary, i.e., with a two-way feedback. In the first model only coexistence is attainable, meaning that both opinions survive, but with the presence of many disagreeing edges. In the second model only consensus prevails, while in the third model polarisation is possible. Our main results are functional laws of large numbers for the densities of the two opinions, functional laws of large numbers for the dynamic random graphs in the space of graphons, and a characterisation of the limiting densities in terms of Beta-distributions. Our results are supported by simulations. To prove our results we develop a novel method that involves coupling the co-evolutionary process to a mimicking process with one-way feedback. We expect that this method can be extended to other dense co-evolutionary models., Comment: 39 pages

Learning performance data describe correct and incorrect answers or problem-solving attempts in adaptive learning, such as in intelligent tutoring systems (ITSs). Learning performance data tend to be highly sparse (80\%\(\sim\)90\% missing observations) in most real-world applications due to adaptive item selection. This data sparsity presents challenges to using learner models to effectively predict future performance explore new hypotheses about learning. This article proposes a systematic framework for augmenting learner data to address data sparsity in learning performance data. First, learning performance is represented as a three-dimensional tensor of learners' questions, answers, and attempts, capturing longitudinal knowledge states during learning. Second, a tensor factorization method is used to impute missing values in sparse tensors of collected learner data, thereby grounding the imputation on knowledge tracing tasks that predict missing performance values based on real observations. Third, a module for generating patterns of learning is used. This study contrasts two forms of generative Artificial Intelligence (AI), including Generative Adversarial Networks (GANs) and Generate Pre-Trained Transformers (GPT) to generate data associated with different clusters of learner data. We tested this approach on an adult literacy dataset from AutoTutor lessons developed for Adult Reading Comprehension (ARC). We found that: (1) tensor factorization improved the performance in tracing and predicting knowledge mastery compared with other knowledge tracing techniques without data augmentation, showing higher relative fidelity for this imputation method, and (2) the GAN-based simulation showed greater overall stability and less statistical bias based on a divergence evaluation with varying simulation sample sizes compared to GPT.

In many data-driven applications, higher-order relationships among multiple objects are essential in capturing complex interactions. Hypergraphs, which generalize graphs by allowing edges to connect any number of nodes, provide a flexible and powerful framework for modeling such higher-order relationships. In this work, we introduce hypergraph diffusion wavelets and describe their favorable spectral and spatial properties. We demonstrate their utility for biomedical discovery in spatially resolved transcriptomics by applying the method to represent disease-relevant cellular niches for Alzheimer's disease.

We consider a discrete-time binary branching random walk with independent standard normal increments subject to a penalty $\b$ for every pair of particles that get within distance $\e$ of each other at any time. We give a precise description of the most likely configurations of the particles under this law for $N$ large and $\b,\e$ fixed. Particles spread out over a distance $2^{2N/3}$, essentially in finite time, and subsequently arrange themselves so that at time $2N/3$ they cover a grid of width $\e$ with one particle per site. After time $2N/3$, the bulk of the particles and their descendants do not move anymore, while the particles in a boundary layer of width $2^{N/3}$ form a ``staircase" to the particles in the bulk. At time $N$, each site in the boundary layer is occupied by $2^{N/3}$ particles., Comment: 20 pages, 4 figures

In this paper, we obtain a precise estimate of the probability that the sparse binomial random graph contains a large number of vertices in a triangle. The estimate of log of this probability is correct up to second order, and enables us to propose an exponential random graph model based on the number of vertices in a triangle. Specifically, by tuning a single parameter, we can with high probability induce any given fraction of vertices in a triangle. Moreover, in the proposed exponential random graph model we derive the large deviation principle for the number of edges. As a byproduct, we propose a consistent estimator of the tuning parameter., Comment: Follow up of arXiv:2112.06526v2. Revised version

This is the third in a series of three papers in which we study a lattice gas subject to Kawasaki dynamics at inverse temperature $\beta>0$ in a large finite box $\Lambda_\beta \subset \mathbb{Z}^2$ whose volume depends on $\beta$. Each pair of neighbouring particles has a negative binding energy $-U<0$, while each particle has a positive activation energy $\Delta>0$. The initial configuration is drawn from the grand-canonical ensemble restricted to the set of configurations where all the droplets are subcritical. Our goal is to describe, in the metastable regime $\Delta \in (U,2U)$ and in the limit as $\beta\to\infty$, how and when the system nucleates, i.e., creates a critical droplet somewhere in $\Lambda_\beta$ that subsequently grows by absorbing particles from the surrounding gas. In the first paper we showed that subcritical droplets behave as quasi-random walks. In the second paper we used the results in the first paper to analyse how subcritical droplets form and dissolve on multiple space-time scales when the volume is moderately large, namely, $|\Lambda_\beta| = \mathrm{e}^{\theta\beta}$ with $\Delta < \theta < 2\Delta-U$. In the present paper we consider the setting where the volume is very large, namely, $|\Lambda_\beta| = \mathrm{e}^{\Theta\beta}$ with $\Delta < \Theta < \Gamma-(2\Delta-U)$, where $\Gamma$ is the energy of the critical droplet in the local model with fixed volume, and use the results in the first two papers to identify the nucleation time and the tube of typical trajectories towards nucleation. We will see that in a very large volume critical droplets appear more or less independently in boxes of moderate volume, a phenomenon referred to as homogeneous nucleation. One of the key ingredients in the proof is an estimate showing that no information can travel between these boxes on relevant time scales., Comment: 21 pages, 5 figures. arXiv admin note: text overlap with arXiv:2304.14099

Collecting and annotating real-world data for the development of object detection models is a time-consuming and expensive process. In the military domain in particular, data collection can also be dangerous or infeasible. Training models on synthetic data may provide a solution for cases where access to real-world training data is restricted. However, bridging the reality gap between synthetic and real data remains a challenge. Existing methods usually build on top of baseline Convolutional Neural Network (CNN) models that have been shown to perform well when trained on real data, but have limited ability to perform well when trained on synthetic data. For example, some architectures allow for fine-tuning with the expectation of large quantities of training data and are prone to overfitting on synthetic data. Related work usually ignores various best practices from object detection on real data, e.g. by training on synthetic data from a single environment with relatively little variation. In this paper we propose a methodology for improving the performance of a pre-trained object detector when training on synthetic data. Our approach focuses on extracting the salient information from synthetic data without forgetting useful features learned from pre-training on real images. Based on the state of the art, we incorporate data augmentation methods and a Transformer backbone. Besides reaching relatively strong performance without any specialized synthetic data transfer methods, we show that our methods improve the state of the art on synthetic data trained object detection for the RarePlanes and DGTA-VisDrone datasets, and reach near-perfect performance on an in-house vehicle detection dataset., Comment: Submitted to and presented at SPIE Defense + Commercial Sensing 2024, 13 pages, 4 figures, 3 tables

Recent studies have investigated new approaches for communicating an autonomous vehicle's (AV) intent and awareness to pedestrians. This paper adds to this body of work by presenting the design and evaluation of in-situ projections on the road. Our design combines common traffic light patterns with aesthetic visual elements. We describe the iterative design process and the prototyping methods used in each stage. The final design concept was represented as a virtual reality simulation and evaluated with 18 participants in four different street crossing scenarios, which included three scenarios that simulated various degrees of system errors. We found that different design elements were able to support participants' confidence in their decision even when the AV failed to correctly detect their presence. We also identified elements in our design that needed to be more clearly communicated. Based on these findings, the paper presents a series of design recommendations for projection-based communication between AVs and pedestrians.

Intelligent Tutoring Systems (ITSs) have significantly enhanced adult literacy training, a key factor for societal participation, employment opportunities, and lifelong learning. Our study investigates the application of advanced AI models, including Large Language Models (LLMs) like GPT-4, for predicting learning performance in adult literacy programs in ITSs. This research is motivated by the potential of LLMs to predict learning performance based on its inherent reasoning and computational capabilities. By using reading comprehension datasets from the ITS, AutoTutor, we evaluate the predictive capabilities of GPT-4 versus traditional machine learning methods in predicting learning performance through five-fold cross-validation techniques. Our findings show that the GPT-4 presents the competitive predictive abilities with traditional machine learning methods such as Bayesian Knowledge Tracing, Performance Factor Analysis, Sparse Factor Analysis Lite (SPARFA-Lite), tensor factorization and eXtreme Gradient Boosting (XGBoost). While XGBoost (trained on local machine) outperforms GPT-4 in predictive accuracy, GPT-4-selected XGBoost and its subsequent tuning on the GPT-4 platform demonstrates superior performance compared to local machine execution. Moreover, our investigation into hyper-parameter tuning by GPT-4 versus grid-search suggests comparable performance, albeit with less stability in the automated approach, using XGBoost as the case study. Our study contributes to the field by highlighting the potential of integrating LLMs with traditional machine learning models to enhance predictive accuracy and personalize adult literacy education, setting a foundation for future research in applying LLMs within ITSs., Comment: 26TH International Conference on Human-Computer Interaction

We analyse the mixing profile of a random walk on a dynamic random permutation, focusing on the regime where the walk evolves much faster than the permutation. Two types of dynamics generated by random transpositions are considered: one allows for coagulation of permutation cycles only, the other allows for both coagulation and fragmentation. We show that for both types, after scaling time by the length of the permutation and letting this length tend to infinity, the total variation distance between the current distribution and the uniform distribution converges to a limit process that drops down in a single jump. This jump is similar to a one-sided cut-off, occurs after a random time whose law we identify, and goes from the value 1 to a value that is a strictly decreasing and deterministic function of the time of the jump, related to the size of the largest component in Erd\H{o}s-R\'enyi random graphs. After the jump, the total variation distance follows this function down to 0.

In this paper we consider the two-type Moran model with $N$ individuals. Each individual is assigned a resampling rate, drawn independently from a probability distribution ${\mathbb P}$ on ${\mathbb R}_+$, and a type, either $1$ or $0$. Each individual resamples its type at its assigned rate, by adopting the type of an individual drawn uniformly at random. Let $Y^N(t)$ denote the empirical distribution of the resampling rates of the individuals with type $1$ at time $Nt$. We show that if ${\mathbb P}$ has countable support and satisfies certain tail and moment conditions, then in the limit as $N\to\infty$ the process $(Y^N(t))_{t \geq 0}$ converges in law to the process $(S(t)\,\P)_{t \geq 0}$, in the so-called Meyer-Zheng topology, where $(S(t))_{t \geq 0}$ is the Fisher-Wright diffusion with diffusion constant $D$ given by $1/D = \int_{{\mathbb R}_+} (1/r)\,{\mathbb P}(\mathrm{d} r)$.

Let $G_n$ be an undirected finite graph on $n\in\mathbb{N}$ vertices labelled by $[n] = \{1,\ldots,n\}$. For $i \in [n]$, let $\Delta_{i,n}$ be the friendship bias of vertex $i$, defined as the difference between the average degree of the neighbours of vertex $i$ and the degree of vertex $i$ itself when $i$ is not isolated, and zero when $i$ is isolated. Let $\mu_n$ denote the friendship-bias empirical distribution, i.e., the measure that puts mass $\frac{1}{n}$ at each $\Delta_{i,n}$, $i \in [n]$. The friendship paradox says that $\int_{\mathbb{R}} x\mu_n(\mathrm{d}x) \geq 0$, with equality if and only if in each connected component of $G_n$ all the degrees are the same. We show that if $(G_n)_{n\in\mathbb{N}}$ is a sequence of sparse random graphs that converges to a rooted random tree in the sense of convergence locally in probability, then $\mu_n$ converges weakly to a limiting measure $\mu$ that is expressible in terms of the law of the rooted random tree. We study $\mu$ for four classes of sparse random graphs: the homogeneous Erd\H{o}s-R\'enyi random graph, the inhomogeneous Erd\H{o}s-R\'enyi random graph, the configuration model and the preferential attachment model. In particular, we compute the first two moments of $\mu$, identify the right tail of $\mu$, and argue that $\mu([0,\infty))\geq\tfrac{1}{2}$, a property we refer to as friendship paradox significance., Comment: To appear in Probability Theory and Related Fields

We analyse the largest eigenvalue of the adjacency matrix of the configuration model with large degrees, where the latter are treated as hard constraints. In particular, we compute the expectation of the largest eigenvalue for degrees that diverge as the number of vertices $n$ tends to infinity, uniformly on a scale between $1$ and $\sqrt{n}$, and show that a weak law of large numbers holds. We compare with what was derived in our earlier paper "Central limit theorem for the principal eigenvalue and eigenvector of Chung-Lu random graphs" for the Chung-Lu model, which in the regime considered represents the corresponding configuration model with soft constraints, and show that the expectation is shifted down by $1$ asymptotically. This shift is a signature of breaking of ensemble equivalence between the hard and soft (also known as micro-canonical and canonical) versions of the configuration model. The latter result generalizes a previous finding in "A spectral signature of breaking of ensemble equivalence for constrained random graphs" obtained in the case when all degrees are equal., Comment: 21 pages, 3 figures

We show how to capture both the non-unitary Page curve and replica wormhole-like contributions that restore unitarity in a toy quantum system with random dynamics. The motivation is to find the simplest dynamical model that captures this aspect of gravitational physics. In our model, we evolve with an ensemble of Hamiltonians with GUE statistics within microcanonical windows. The entropy of the averaged state gives the non-unitary curve, the averaged entropy gives the unitary curve, and the difference comes from matrix index contractions in the Haar averaging that connect the density matrices in a replica wormhole-like manner., Comment: 43 pages, 10 figures

In this paper we consider stochastic processes taking values in a set of continuum graphs we call graphemes, defined as equivalence classes of sequences of vertices labelled by N embedded in an uncountable Polish space (with the cardinality of the continuum), together with an N x N connection matrix with entries 0 or 1 specifying the absence or presence of edges between pairs of vertices. In particular, we construct a Markov process on a Polish state space G of graphemes suitable to describe the time-space path of countable graphs. The class of dynamics we propose arises by specifying simple rules for the evolution of finite graphs and passing to the limit of infinite graphs. The evolution of graphemes is characterised by well-posed martingale problems, and leads to strong Markov processes with the Feller property., Comment: 78 pages, 2 figures

Graph neural networks (GNNs) have emerged as a powerful tool for tasks such as node classification and graph classification. However, much less work has been done on signal classification, where the data consists of many functions (referred to as signals) defined on the vertices of a single graph. These tasks require networks designed differently from those designed for traditional GNN tasks. Indeed, traditional GNNs rely on localized low-pass filters, and signals of interest may have intricate multi-frequency behavior and exhibit long range interactions. This motivates us to introduce the BLIS-Net (Bi-Lipschitz Scattering Net), a novel GNN that builds on the previously introduced geometric scattering transform. Our network is able to capture both local and global signal structure and is able to capture both low-frequency and high-frequency information. We make several crucial changes to the original geometric scattering architecture which we prove increase the ability of our network to capture information about the input signal and show that BLIS-Net achieves superior performance on both synthetic and real-world data sets based on traffic flow and fMRI data.

Our research explores the use of natural language processing (NLP) methods to automatically classify entities for the purpose of knowledge graph population and integration with food system ontologies. We have created NLP models that can automatically classify organizations with respect to categories associated with environmental issues as well as Standard Industrial Classification (SIC) codes, which are used by the U.S. government to characterize business activities. As input, the NLP models are provided with text snippets retrieved by the Google search engine for each organization, which serves as a textual description of the organization that is used for learning. Our experimental results show that NLP models can achieve reasonably good performance for these two classification tasks, and they rely on a general framework that could be applied to many other classification problems as well. We believe that NLP models represent a promising approach for automatically harvesting information to populate knowledge graphs and aligning the information with existing ontologies through shared categories and concepts., Comment: Presented at IFOW 2023 Integrated Food Ontology Workshop at the Formal Ontology in Information Systems Conference (FOIS) 2023 in Sherbrooke, Quebec, Canada July 17-20th, 2023

In this paper we introduce and study renewal-reward processes in random environments where each renewal involves a reward taking values in a Banach space. We derive quenched large deviation principles and identify the associated rate functions in terms of variational formulas involving correctors. We illustrate the theory with three examples: compound Poisson processes in random environments, pinning of polymers at interfaces with disorder, and returns of Markov chains in dynamic random environments., Comment: Submitted to the special issue of Stochastic Processes and their Applications in honor of Francis Comets

The Brain Imaging Data Structure (BIDS) is a community-driven standard for the organization of data and metadata from a growing range of neuroscience modalities. This paper is meant as a history of how the standard has developed and grown over time. We outline the principles behind the project, the mechanisms by which it has been extended, and some of the challenges being addressed as it evolves. We also discuss the lessons learned through the project, with the aim of enabling researchers in other domains to learn from the success of BIDS.

In [Athreya, den Hollander, R\"ollin; 2021, arXiv:1908.06241] models from population genetics were used to define stochastic dynamics in the space of graphons arising as continuum limits of dense graphs. In the present paper we exhibit an example of a simple neutral population genetics model for which this dynamics is a Markovian diffusion that can be characterised as the solution of a martingale problem. In particular, we consider a Markov chain in the space of finite graphs that resembles a Moran model with resampling and mutation. We encode the finite graphs as graphemes, which can be represented as a triple consisting of a vertex set, an adjacency matrix and a sampling measure. We equip the space of graphons with convergence of sample subgraph densities and show that the grapheme-valued Markov chain converges to a grapheme-valued diffusion as the number of vertices goes to infinity. We show that the grapheme-valued diffusion has a stationary distribution that is linked to the Poisson-Dirichlet distribution. In a companion paper [Greven, den Hollander, Klimovsky, Winter; 2023], we build up a general theory for obtaining grapheme-valued diffusions via genealogies of models in population genetics., Comment: 25 pages

We study the total mass of the solution to the parabolic Anderson model on a regular tree with an i.i.d. random potential whose marginal distribution is double-exponential. In earlier work we identified two terms in the asymptotic expansion for large time of the total mass under the quenched law, i.e., conditional on the realisation of the random potential. In the present paper we do the same for the annealed law, i.e., averaged over the random potential. It turns out that the annealed expansion differs from the quenched expansion. The derivation of the annealed expansion is based on a new approach to control the local times of the random walk appearing in the Feynman-Kac formula for the total mass. In particular, we condition on the backbone to infinity of the random walk, truncate and periodise the infinite tree relative to the backbone to obtain a random walk on a finite subtree with a specific boundary condition, employ the large deviation principle for the empirical distribution of Markov renewal processes on finite graphs, and afterwards let the truncation level tend to infinity to obtain an asymptotically sharp asymptotic expansion.

We consider an inhomogeneous Erd\H{o}s-R\'enyi random graph $G_N$ with vertex set $[N] = \{1,\dots,N\}$ for which the pair of vertices $i,j \in [N]$, $i\neq j$, is connected by an edge with probability $r_N(\tfrac{i}{N},\tfrac{j}{N})$, independently of other pairs of vertices. Here, $r_N\colon\,[0,1]^2 \to (0,1)$ is a symmetric function that plays the role of a reference graphon. Let $\lambda_N$ be the maximal eigenvalue of the Laplacian matrix of $G_N$. We show that if $\lim_{N\to\infty} \|r_N-r\|_\infty = 0$ for some limiting graphon $r\colon\,[0,1]^2 \to (0,1)$, then $\lambda_N/N$ satisfies a downward LDP with rate $\binom{N}{2}$ and an upward LDP with rate $N$. We identify the associated rate functions $\psi_r$ and $\widehat{\psi}_r$, and derive their basic properties., Comment: 25 pages. Assumptions improved and minor corrections incorporated. To appear in Electronic Journal of Probability

This is the second in a series of three papers in which we study a lattice gas subject to Kawasaki conservative dynamics at inverse temperature $\beta>0$ in a large finite box $\Lambda_\beta \subset\mathbb Z^2$ whose volume depends on $\beta$. Each pair of neighbouring particles has a negative binding energy $-U<0$, while each particle has a positive activation energy $\Delta>0$. The initial configuration is drawn from the grand-canonical ensemble restricted to the set of configurations where all the droplets are subcritical. Our goal is to describe, in the metastable regime $\Delta\in(U,2U)$ and in the limit as $\beta\to\infty$, how and when the system nucleates. In the first paper we showed that subcritical droplets behave as quasi-random walks. In the present paper we use the results in the first paper to analyse how subcritical droplets form and dissolve on multiple space-time scales when the volume is moderately large, i.e., $|\Lambda_\beta|=\mathrm e^{\Theta\beta}$ with $\Delta<\Theta<2\Delta-U$. In the third paper we consider the setting where the volume is very large, namely, $|\Lambda_\beta|=\mathrm e^{\Theta\beta}$ with $\Delta<\Theta<\Gamma-(2\Delta-U)$, where $\Gamma$ is the energy of the critical droplet in the local model with fixed volume, and use the results in the first two papers to identify the nucleation time. We will see that in a very large volume critical droplets appear more or less independently in boxes of moderate volume, a phenomenon referred to as homogeneous nucleation. Since Kawasaki dynamics is conservative, i.e., particles are preserved, we need to control non-local effects in the way droplets are formed and dissolved. This is done via a deductive approach: the tube of typical trajectories leading to nucleation is described via a series of events on which the evolution of the gas consists of droplets wandering around on multiple space-time scales., Comment: 46 pages, 11 figures

Twenty-first century literacy includes a mixture of digital and print literacy skills and strategies. AutoTutor for Adult Reading Comprehension is a web-based intelligent tutoring system that is designed to help adult learners develop effective reading comprehension strategies. Lessons span basic reading skills (vocabulary, word parts), comprehension of sentences and texts in different text genres and rhetorical structures, including digital documents and media. The AutoTutor system features an accessible interface, conversational trialogues with helpful and engaging computer agents, and material and scenarios that were developed specifically for adult learners. Studies suggest that this system significantly improves learning outcomes when used in conjunction with classroom instruction. Materials described in this article are free and readily available to adult educators and their students. [This article was published in "COABE Journal: The Resource for Adult Education."]

We consider a system of interacting Fisher-Wright diffusions with seed-bank. Individuals carry type one of two types, live in colonies, and are subject to resampling and migration as long as they are active. Each colony has a structured seed-bank into which individuals can retreat to become dormant, suspending their resampling and migration until they become active again. As geographic space labelling the colonies we consider a countable Abelian group endowed with the discrete topology. In earlier work we showed that the system has a one-parameter family of equilibria controlled by the relative density of the two types. Moreover, these equilibria exhibit a dichotomy of coexistence (= locally multi-type equilibrium) versus clustering (= locally mono-type equilibrium). We identified the parameter regimes for which these two phases occur, and found that these regimes are different when the mean wake-up time of a dormant individual is finite or infinite. The goal of the present paper is to establish the finite-systems scheme, i.e., identify how a finite truncation of the system (both in the geographic space and in the seed-bank) behaves as both the time and the truncation level tend to infinity, properly tuned together. If the wake-up time has finite mean, then there is a single universality class for the scaling limit. On the other hand, if the wake-up time has infinite mean, then there are two universality classes depending on how fast the truncation level of the seed-bank grows compared to the truncation level of the geographic space., Comment: 56 pages, 7 figures

We introduce a general class of mean-field-like spin systems with random couplings that comprises both the Ising model on inhomogeneous dense random graphs and the randomly diluted Hopfield model. We are interested in quantitative estimates of metastability in large volumes at fixed temperatures when these systems evolve according to a Glauber dynamics, i.e.\ where spins flip with Metropolis transition probabilities at inverse temperature $\beta$. We identify conditions ensuring that with high probability the system behaves like the corresponding system where the random couplings are replaced by their averages. More precisely, we prove that the metastability of the former system is implied with high probability by the metastability of the latter. Moreover, we consider relevant metastable hitting times of the two systems and find the asymptotic tail behaviour and the moments of their ratio. This work provides an extension of the results known for the Ising model on the Erd\H{o}s--R{\'e}nyi random graph. The proofs use the potential-theoretic approach to metastability in combination with concentration inequalities., Comment: 30 pages

The prospect of combining human operators and virtual agents (bots) into an effective hybrid system that provides proper customer service to clients is promising yet challenging. The hybrid system decreases the customers' frustration when bots are unable to provide appropriate service and increases their satisfaction when they prefer to interact with human operators. Furthermore, we show that it is possible to decrease the cost and efforts of building and maintaining such virtual agents by enabling the virtual agent to incrementally learn from the human operators. We employ queuing theory to identify the key parameters that govern the behavior and efficiency of such hybrid systems and determine the main parameters that should be optimized in order to improve the service. We formally prove, and demonstrate in extensive simulations and in a user study, that with the proper choice of parameters, such hybrid systems are able to increase the number of served clients while simultaneously decreasing their expected waiting time and increasing satisfaction.

We consider a class of graph-valued stochastic processes in which each vertex has a type that fluctuates randomly over time. Collectively, the paths of the vertex types up to a given time determine the probabilities that the edges are active or inactive at that time. Our focus is on the evolution of the associated empirical graphon in the limit as the number of vertices tends to infinity, in the setting where fluctuations in the graph-valued process are more likely to be caused by fluctuations in the vertex types than by fluctuations in the states of the edges given these types. We derive both sample-path large deviation principles and convergence of stochastic processes. We demonstrate the flexibility of our approach by treating a class of stochastic processes where the edge probabilities depend not only on the fluctuations in the vertex types but also on the state of the graph itself., Comment: 41 pages, 4 figures

We consider the two-opinion voter model on a regular random graph with n vertices and degree $d \geq 3$. It is known that consensus is reached on time scale n and that on this time scale the volume of the set of vertices with one opinion evolves as a Fisher-Wright diffusion. We are interested in the evolution of the number of discordant edges (i.e., edges linking vertices with different opinions), which can be thought as the perimeter of the set of vertices with one opinion, and is the key observable capturing how consensus is reached. We show that if initially the two opinions are drawn independently from a Bernoulli distribution with parameter $u \in (0, 1)$, then on time scale 1 the fraction of discordant edges decreases and stabilises to a value that depends on d and u, and is related to the meeting time of two random walks on an infinite tree of degree d starting from two neighbouring vertices. Moreover, we show that on time scale n the fraction of discordant edges moves away from the constant plateau and converges to zero in an exponential fashion. Our proofs exploit the classical dual system of coalescing random walks and use ideas from Cooper et al. (2010) built on the so-called First Visit Time Lemma. We further introduce a novel technique to derive concentration properties from weak-dependence of coalescing random walks on moderate time scales., Comment: Manuscript matching published version

Symmetric product orbifold theories are valuable due to their universal features at large $N$. Here we will demonstrate that they have features that are not as pervasive: we provide evidence of strange behaviour under deformations within their moduli space. To this end, we consider the symmetric product orbifold of tensor products of $\mathcal{N}=2$ super-Virasoro minimal models, and classify them according to two criteria. The first criterion is the existence of a single-trace twisted exactly marginal operator that triggers the deformation. The second criterion is a sparseness condition on the growth of light states in the elliptic genera. In this context we encounter a strange variety: theories that obey the first criterion but the second criterion falls into a Hagedorn-like growth. We explain why this may be counter-intuitive and discuss how it might be accounted for in conformal perturbation theory. We also find a new infinite class of theories that obey both criteria, which are necessary conditions for each moduli space to contain a supergravity point., Comment: 34 pages, 3 figures, v3: minor changes, version as published in JHEP

Adult literacy learners are characterized by their diversity, both in terms of educational histories and cognitive skill sets. Accounting for the specific strengths and weaknesses of each learner is vital to the assessment of literacy gains and optimization of educational systems. We examined pre- and post-difference scores on a component reading skills assessment battery collected before and after an instructional program that included an adult comprehension- focused intelligent tutoring system. By characterizing learners during instruction, we examined differential gains in foundational reading skills. Most learners made gains in reading skills above the word recognition and decoding level; readers who were classified as "conscientious" (who performed slowly but accurately) tended to make the most substantial gains. We conclude that this hybrid instructional program may be an effective educational environment for adult literacy and describe how characterizing learners via integrating assessments into adaptive instructional practice may improve efficiency and effectiveness. [This is the online version of an article published in "Discourse Processes."]

A Chung-Lu random graph is an inhomogeneous Erd\H{o}s-R\'enyi random graph in which vertices are assigned average degrees, and pairs of vertices are connected by an edge with a probability that is proportional to the product of their average degrees, independently for different edges. We derive a central limit theorem for the principal eigenvalue and the components of the principal eigenvector of the adjacency matrix of a Chung-Lu random graph. Our derivation requires certain assumptions on the average degrees that guarantee connectivity, sparsity and bounded inhomogeneity of the graph.

In this paper we consider the Erd\H{o}s-R\'enyi random graph in the sparse regime in the limit as the number of vertices $n$ tends to infinity. We are interested in what this graph looks like when it contains many triangles, in two settings. First, we derive asymptotically sharp bounds on the probability that the graph contains a large number of triangles. We show that conditionally on this event, with high probability the graph contains an almost complete subgraph, i.e., the triangles form a near-clique, and has the same local limit as the original Erd\H{o}s-R\'enyi random graph. Second, we derive asymptotically sharp bounds on the probability that the graph contains a large number of vertices that are part of a triangle. If order $n$ vertices are in triangles, then the local limit (provided it exists) is different from that of the Erd\H{o}s-R\'enyi random graph. Our results shed light on the challenges that arise in the description of real-world networks, which often are sparse, yet highly clustered, and on exponential random graphs, which often are used to model such networks., Comment: 31 pages, updated references

We consider a system of interacting diffusions labeled by a geographic space that is given by the hierarchical group $\Omega_N$ of order $N\in\mathbb{N}$. Individuals live in colonies and are subject to resampling and migration as long as they are active. Each colony has a seed-bank into which individuals can retreat to become dormant, suspending their resampling and migration until they become active again. The migration kernel has a hierarchical structure: individuals hop between colonies at a rate that depends on the hierarchical distance between the colonies. The seed-bank has a layered structure: when individuals become dormant they acquire a colour that determines the rate at which they become active again. The latter allows us to model seed-banks whose wake-up times have a fat tail. We analyse a system of coupled stochastic differential equations that describes the population in the large-colony-size limit. For fixed $N\in\mathbb{N}$, the system exhibits a dichotomy between coexistence and clustering. We identify the range of parameters controlling the migration and the seed-bank for which clustering prevails. We carry out a multi-scale renormalisation analysis in the hierarchical mean-field limit $N\to\infty$. We show that block averages on hierarchical space-time scale $k \in \mathbb{N}$ perform a diffusion with a renormalised diffusion function that depends on $k$. In the clustering regime, after an appropriate scaling with $k$, this diffusion function converges to the Fisher-Wright diffusion function as $k\to\infty$, irrespective of the diffusion function controlling the resampling. For several subclasses of parameters we identify the speed at which the scaled renormalised diffusion function converges to the Fisher-Wright diffusion as $k\to\infty$. We show that the seed-bank reduces the speed compared to the model without seed-bank., Comment: 167 pages

Kostant's weight $q$-multiplicity formula is an alternating sum over a finite group known as the Weyl group, whose terms involve the $q$-analog of Kostant's partition function. The $q$-analog of the partition function is a polynomial-valued function defined by $\wp_q(\xi)=\sum_{i=0}^k c_i q^i$, where $c_i$ is the number of ways the weight $\xi$ can be written as a sum of exactly $i$ positive roots of a Lie algebra $\mathfrak{g}$. The evaluation of the $q$-multiplicity formula at $q = 1$ recovers the multiplicity of a weight in an irreducible highest weight representation of $\mathfrak{g}$. In this paper, we specialize to the Lie algebra $\mathfrak{sp}_6(\mathbb{C})$ and we provide a closed formula for the $q$-analog of Kostant's partition function, which extends recent results of Shahi, Refaghat, and Marefat. We also describe the supporting sets of the multiplicity formula (known as the Weyl alternation sets of $\mathfrak{sp}_6(\mathbb{C})$), and use these results to provide a closed formula for the $q$-multiplicity for any pair of dominant integral weights of $\mathfrak{sp}_6(\mathbb{C})$. Throughout this work, we provide code to facilitate these computations., Comment: 32 pages, including 6 tables, and 21 pages of appendices with code

We consider a spatial version of the classical Moran model with seed-banks where the constituent populations have finite sizes. Individuals live in colonies labelled by $\mathbb{Z}^d$, $d\geq 1$, playing the role of a geographic space, carry one of the two $types$: $\heartsuit$ or $\spadesuit$, and change type via $resampling$ as long as they are $active$. Each colony contains a seed-bank into which individuals can enter to become $dormant$, suspending their resampling until they exit the seed-bank and become active again. Individuals resample not only from their own colony, but also from other colonies according to a symmetric random walk transition kernel. The latter is referred to as $migration$. The sizes of the populations vary across colonies and remain constant in time. It was shown in Hollander and Nandan (2021) that the system is well-defined, admits a family of equilibria parametrized by the initial density of type $\heartsuit$, and exhibits a dichotomy between $clustering$ (mono-type equilibrium) and $coexistence$ (multi-type equilibrium). This dichotomy is determined by a clustering criterion that is given in terms of a dual of the system, which consists of a system of $interacting$ coalescing random walks. In this paper we provide an alternative clustering criterion, given in terms of an auxiliary dual that is simpler than the original dual, and identify a range of parameters for which the criterion is met, which we refer to as the $clustering$ $regime$. It turns out that if the sizes of the active populations are non-clumping (i.e., do not take arbitrarily large values in finite regions of the geographic space) and the relative strengths of the seed-banks (i.e., the ratio of the sizes of dormant and active population in each colony) are bounded uniformly over the geographic space, then clustering prevails if and only if the (symmetrised) migration kernel is recurrent., Comment: Version 2, added intuitive explainations, remarks etc. The old assumption 2.9 on migration kernel is now weakened to Assumption 2.11

In this paper we consider three classes of interacting particle systems on $\mathbb Z$: independent random walks, the exclusion process, and the inclusion process. We allow particles to switch their jump rate (the rate identifies the type of particle) between $1$ (fast particles) and $\epsilon\in[0,1]$ (slow particles). The switch between the two jump rates happens at rate $\gamma\in(0,\infty)$. In the exclusion process, the interaction is such that each site can be occupied by at most one particle of each type. In the inclusion process, the interaction takes places between particles of the same type at different sites and between particles of different type at the same site. We derive the macroscopic limit equations for the three systems, obtained after scaling space by $N^{-1}$, time by $N^2$, the switching rate by $N^{-2}$, and letting $N\to\infty$. The limit equations for the macroscopic densities associated to the fast and slow particles is the well-studied double diffusivity model. This system of reaction-diffusion equations was introduced to model polycrystal diffusion and dislocation pipe diffusion, with the goal to overcome the limitations imposed by Fick's law. In order to investigate the microscopic out-of-equilibrium properties, we analyse the system on $[N]=\{1,\ldots,N\}$, adding boundary reservoirs at sites $1$ and $N$ of fast and slow particles, respectively. Inside $[N]$ particles move as before, but now particles are injected and absorbed at sites $1$ and $N$ with prescribed rates that depend on the particle type. We compute the steady-state density profile and the steady-state current. It turns out that uphill diffusion is possible, i.e., the total flow can be in the direction of increasing total density. This phenomenon, which cannot occur in a single-type particle system, is a violation of Fick's law made possible by the switching between types.

Consider the complete graph on $n$ vertices. To each vertex assign an Ising spin that can take the values $-1$ or $+1$. Each spin $i \in [n]=\{1,2,\dots, n\}$ interacts with a magnetic field $h \in [0,\infty)$, while each pair of spins $i,j \in [n]$ interact with each other at coupling strength $n^{-1} J(i)J(j)$, where $J=(J(i))_{i \in [n]}$ are i.i.d. non-negative random variables drawn from a probability distribution with finite support. Spins flip according to a Metropolis dynamics at inverse temperature $\beta \in (0,\infty)$. We show that there are critical thresholds $\beta_c$ and $h_c(\beta)$ such that, in the limit as $n\to\infty$, the system exhibits metastable behaviour if and only if $\beta \in (\beta_c, \infty)$ and $h \in [0,h_c(\beta))$. Our main result is a sharp asymptotics, up to a multiplicative error $1+o_n(1)$, of the average crossover time from any metastable state to the set of states with lower free energy. We use standard techniques of the potential-theoretic approach to metastability. The leading order term in the asymptotics does not depend on the realisation of $J$, while the correction terms do. The leading order of the correction term is $\sqrt{n}$ times a centred Gaussian random variable with a complicated variance depending on $\beta,h$, on the law of $J$ and on the metastable state. The critical thresholds $\beta_c$ and $h_c(\beta)$ depend on the law of $J$, and so does the number of metastable states. We derive an explicit formula for $\beta_c$ and identify some properties of $\beta \mapsto h_c(\beta)$. Interestingly, the latter is not necessarily monotone, meaning that the metastable crossover may be re-entrant., Comment: 41 pages, 6 figures

Two ensembles are often used to model random graphs subject to constraints: the microcanonical ensemble (= hard constraint) and the canonical ensemble (= soft constraint). It is said that breaking of ensemble equivalence (BEE) occurs when the specific relative entropy of the two ensembles does not vanish as the size of the graph tends to infinity. The latter means that it matters for the scaling properties of the graph whether the constraint is met for every single realisation of the graph or only holds as an ensemble average. In the literature, it was found that BEE is the rule rather than the exception for two classes: sparse random graphs when the number of constraints is of the order of the number of vertices and dense random graphs when there are two or more constraints that are frustrated. In the present paper we establish BEE for a third class: dense random graphs with a single constraint, namely, on the density of a given finite simple graph. We show that BEE occurs only in a certain range of choices for the density and the number of edges of the simple graph, which we refer to as the BEE-phase. We show that, in part of the BEE-phase, there is a gap between the scaling limits of the averages of the maximal eigenvalue of the adjacency matrix of the random graph under the two ensembles, a property that is referred to as spectral signature of BEE. Proofs are based on an analysis of the variational formula on the space of graphons for the limiting specific relative entropy derived by Den Hollander et al. (2018), in combination with an identification of the minimising graphons and replica symmetry arguments. We show that in the replica symmetric region of the BEE-phase, as the size of the graph tends to infinity, the microcanonical ensemble behaves like an Erd\H{o}s-R\'enyi random graph, while the canonical ensemble behaves like a mixture of two Erd\H{o}s-R\'enyi random graphs., Comment: 21 pages, 3 figures. arXiv admin note: text overlap with arXiv:1807.07750

A dominating set of a graph $G$ is a set of vertices that contains at least one endpoint of every edge on the graph. The domination number of $G$ is the order of a minimum dominating set of $G$. The $(t,r)$ broadcast domination is a generalization of domination in which a set of broadcasting vertices emits signals of strength $t$ that decrease by 1 as they traverse each edge, and we require that every vertex in the graph receives a cumulative signal of at least $r$ from its set of broadcasting neighbors. In this paper, we extend the study of $(t,r)$ broadcast domination to directed graphs. Our main result explores the interval of values obtained by considering the directed $(t,r)$ broadcast domination numbers of all orientations of a graph $G$. In particular, we prove that in the cases $r=1$ and $(t,r) = (2,2)$, for every integer value in this interval, there exists an orientation $\vec{G}$ of $G$ which has directed $(t,r)$ broadcast domination number equal to that value. We also investigate directed $(t,r)$ broadcast domination on the finite grid graph, the star graph, the infinite grid graph, and the infinite triangular lattice graph. We conclude with some directions for future study., Comment: 18 pages, 18 figures

In [1] a detailed analysis was given of the large-time asymptotics of the total mass of the solution to the parabolic Anderson model on a supercritical Galton-Watson random tree with an i.i.d. random potential whose marginal distribution is double-exponential. Under the assumption that the degree distribution has bounded support, two terms in the asymptotic expansion were identified under the quenched law, i.e., conditional on the realisation of the random tree and the random potential. The second term contains a variational formula indicating that the solution concentrates on a subtree with minimal degree according to a computable profile. The present paper extends the analysis to degree distributions with unbounded support. We identify the weakest condition on the tail of the degree distribution under which the arguments in [1] can be pushed through. To do so we need to control the occurrence of large degrees uniformly in large subtrees of the Galton-Watson tree.

We determine all non-edge-to-edge tilings of the sphere by regular spherical polygons of three or more sides.

This paper considers non-backtracking random walks on random graphs generated according to the configuration model. The quantity of interest is the scaling of the mixing time of the random walk as the number of vertices of the random graph tends to infinity. Subject to mild general conditions, we link two mixing times: one for a static version of the random graph, the other for a class of dynamic versions of the random graph in which the edges are randomly rewired but the degrees are preserved. The link is provided by the probability that the random walk has not yet stepped along a previously rewired edge. We use this link to compute the scaling of the mixing time for three specific classes of random rewirings. Depending on the speed and the range of the rewiring relative to the current location of the random walk, the mixing time may exhibit no cut-off, one-sided cut-off or two-sided cut-off, a trichotomy that was also found in earlier work. Interestingly, for a class of dynamics that are `mesoscopic', i.e., non-local and non-global, we find new behaviour with six subregimes. Proofs are built on a new and flexible coupling scheme, in combination with sharp estimates on the degrees encountered by the random walk in the static and the dynamic version of the random graph. Some of these estimates require sharp control on possible short-cuts in the graph between the edges that are traversed by the random walk., Comment: 38 pages, 9 figures