Search

The limit theorem for the estimator G 59 for the regularized solution of the Kolmogorov–Wiener filter is proved. [ABSTRACT FROM AUTHOR]

Given a finite group G acting freely on a compact metric space M, and ε > 0 , we define the G-Borsuk graph on M by drawing edges x ∼ y whenever there is a non-identity g ∈ G such that d x , g y ≤ ε . We show that when ε is small, its chromatic number is determined by the topology of M via its G-covering number, which is the minimum k such that there is a closed cover M = F 1 ∪ ⋯ ∪ F k with F i ∩ g (F i) = ∅ for all g ∈ G \ { 1 } . We are interested in bounding this number. We give lower bounds using G-actions on Hom-complexes, and upper bounds using a recursive formula on the dimension of M. We conjecture that the true chromatic number coincides with the lower bound, and give computational evidence. We also study random G-Borsuk graphs, which are random induced subgraphs. For these, we compute thresholds for ε that guarantee that the chromatic number is still that of the whole G-Borsuk graph. Our results are tight (up to a constant) when the G-index and dimension of M coincide. [ABSTRACT FROM AUTHOR]

We suggest a new random model for links based on meander diagrams and graphs. We then prove that trivial links appear with vanishing probability in this model, no link L is obtained with probability 1, and there is a lower bound for the number of non-isotopic knots obtained for a fixed number of crossings. A random meander diagram is obtained through matching pairs of parentheses, a well-studied problem in combinatorics. Hence tools from combinatorics can be used to investigate properties of random links in this model, and, moreover, of the respective 3-manifolds that are link complements in 3-sphere. We use this for exploring geometric properties of a link complement. Specifically, we give expected twist number of a link diagram and use it to bound expected hyperbolic and simplicial volume of random links. The tools from combinatorics that we use include Catalan and Narayana numbers, and Zeilberger's algorithm. [ABSTRACT FROM AUTHOR]

For all integers n ≥ k > d ≥ 1 , let m d (k , n) be the minimum integer D ≥ 0 such that every k-uniform n-vertex hypergraph H with minimum d-degree δ d (H) at least D has an optimal matching. For every fixed integer k ≥ 3 , we show that for n ∈ k N and p = Ω (n - k + 1 log n) , if H is an n-vertex k-uniform hypergraph with δ k - 1 (H) ≥ m k - 1 (k , n) , then a.a.s. its p-random subhypergraph H p contains a perfect matching. Moreover, for every fixed integer d < k and γ > 0 , we show that the same conclusion holds if H is an n-vertex k-uniform hypergraph with δ d (H) ≥ m d (k , n) + γ n - d k - d . Both of these results strengthen Johansson, Kahn, and Vu's seminal solution to Shamir's problem and can be viewed as "robust" versions of hypergraph Dirac-type results. In addition, we also show that in both cases above, H has at least exp ((1 - 1 / k) n log n - Θ (n)) many perfect matchings, which is best possible up to an exp (Θ (n)) factor. [ABSTRACT FROM AUTHOR]

We propose an algorithm for the closed-form recursive computation of joint moments and cumulants of all orders of k-hop counts in the 1D unit disk random graph model with Poisson distributed vertices. Our approach uses decompositions of k-hop counts into multiple Poisson stochastic integrals. As a consequence, using the Stein and cumulant methods we derive Berry-Esseen bounds for the asymptotic convergence of renormalized k-hop path counts to the normal distribution as the density of Poisson vertices tends to infinity. Computer codes for the recursive symbolic computation of moments and cumulants of any orders are provided as an online resource. [ABSTRACT FROM AUTHOR]

We study the disassortative stochastic block model with three communities, a well-studied model of graph partitioning and Bayesian inference for which detailed predictions based on the cavity method exist (Decelle et al. in Phys Rev E 84:066106, 2011). We provide strong evidence that for a part of the phase where efficient algorithms exist that approximately reconstruct the communities, inference based on maximum a posteriori (MAP) fails. In other words, we show that there exist modes of the posterior distribution that have a vanishing agreement with the ground truth. The proof is based on the analysis of a graph colouring algorithm from Achlioptas and Moore (J Comput Syst Sci 67:441–471, 2003). [ABSTRACT FROM AUTHOR]

This paper investigates the significance of employing random subgraphs and analyzing the expected values of Zagreb ndices within chemical graphs. By examining smaller, representative subsets, we uncover valuable insights into the properties and characteristics of complex networks. The expected values of Zagreb indices serve as critical mathematical measures for quantifying the structural complexity of chemical graphs, providing essential information about connectivity and branching patterns within molecules. Our primary contribution includes deriving theoretical expressions for these indices and validating them through extensive computational experiments on fullerene graphs C 20 and C 60 . The results demonstrate that our theoretical predictions closely align with experimental findings, affirming the robustness of Zagreb indices in characterizing molecular structures. Additionally, our analysis of specific cases, such as complete graphs and complete bipartite graphs, is consistent with previous studies, further reinforcing our methodology. This research emphasizes the relevance of random subgraphs and expected values of Zagreb indices in advancing our understanding of molecular behavior and stability, with important implications for materials science and drug design. [ABSTRACT FROM AUTHOR]

In analyzing collected network data, measurement error is a common concern. One of the current research interests is to study robustness of network properties to measurement error. In this work, we analytically study the impact of measurement error on the global clustering coefficient and the average clustering coefficient of a network. Two types of common measurement errors are considered: (I) each node is randomly removed with probability β and (II) each edge is randomly removed with probability γ. We analytically derive the limits of the clustering coefficients of an inhomogeneous Erdös-Rényi random graph or a power-law random graph with the above two measurement errors. The limits can be used to quantify robustness of the coefficients: if the limits do not depend on β or γ, the coefficients can be considered as robust. Based on our results, the global clustering coefficient and the average clustering coefficient are robust to random removal of nodes but vulnerable to random removal of edges. Extensive experiments validate our theoretical results. [ABSTRACT FROM AUTHOR]

In this manuscript, we delve into the exploration of the first and second Zagreb connection indices of both polyomino chains and random polyomino chains. Our methodology relies on the utilization of Markov chain theory. Within this framework, the article thoroughly examines precise formulas and investigates extreme values. Leveraging the derived formulas, we further explore and elucidate the long-term behavior exhibited by random polyomino chains.

We offer an alternative proof, using the Stein-Chen method, of Bollobás' theorem concerning the distribution of the extreme degrees of a random graph. Our proof also provides a rate of convergence of the extreme degree to its asymptotic distribution. The same method also applies in a more general setting where the probability of every pair of vertices being connected by edges depends on the number of vertices. [ABSTRACT FROM AUTHOR]

In this paper a continuous-time evolving random graph model is defined and examined. The main units of the model are complete graphs on N vertices, where $ N \geq ~3 $ N ≥ 3 is a fixed integer. At each birth event a new vertex and random number of edges are added to the graph. The asymptotic behaviour of the number of vertices and the asymptotic behaviour of the number of m-cliques ( $ 2\leq m\leq N $ 2 ≤ m ≤ N) are studied. The proofs are based on general results of the theory of branching processes. [ABSTRACT FROM AUTHOR]

A tournament is an orientation of a graph. Each edge is a match, directed towards the winner. The score sequence lists the number of wins by each team. In this article, by interpreting score sequences geometrically, we generalize and extend classical theorems of Landau (Bull. Math. Biophys. 15, 143–148 (1953)) and Moon (Pac. J. Math. 13, 1343–1345 (1963)), via the theory of zonotopal tilings. [ABSTRACT FROM AUTHOR]

Co-evolving network models, wherein dynamics such as random walks on the network influence the evolution of the network structure, which in turn influences the dynamics, are of interest in a range of domains. While much of the literature in this area is currently supported by numerics, providing evidence for fascinating conjectures and phase transitions, proving rigorous results has been quite challenging. We propose a general class of co-evolving tree network models driven by local exploration, started from a single vertex called the root. New vertices attach to the current network via randomly sampling a vertex and then exploring the graph for a random number of steps in the direction of the root, connecting to the terminal vertex. Specific choices of the exploration step distribution lead to the well-studied affine preferential attachment and uniform attachment models, as well as less well understood dynamic network models with global attachment functionals such as PageRank scores (Chebolu and Melsted, in: SODA, 2008). We obtain local weak limits for such networks and use them to derive asymptotics for the limiting empirical degree and PageRank distribution. We also quantify asymptotics for the degree and PageRank of fixed vertices, including the root, and the height of the network. Two distinct regimes are seen to emerge, based on the expected exploration distance of incoming vertices, which we call the 'fringe' and 'non-fringe' regimes. These regimes are shown to exhibit different qualitative and quantitative properties. In particular, networks in the non-fringe regime undergo 'condensation' where the root degree grows at the same rate as the network size. Networks in the fringe regime do not exhibit condensation. Further, non-trivial phase transition phenomena are shown to arise for: (a) height asymptotics in the non-fringe regime, driven by the subtle competition between the condensation at the root and network growth; (b) PageRank distribution in the fringe regime, connecting to the well known power-law hypothesis. In the process, we develop a general set of techniques involving local limits, infinite-dimensional urn models, related multitype branching processes and corresponding Perron–Frobenius theory, branching random walks, and in particular relating tail exponents of various functionals to the scaling exponents of quasi-stationary distributions of associated random walks. These techniques are expected to shed light on a variety of other co-evolving network models. [ABSTRACT FROM AUTHOR]

In this paper, we study the online nearest neighbor random tree in dimension d ∈ N (called d-NN tree for short) defined as follows. We fix the torus T n d of dimension d and area n and equip it with the metric inherited from the Euclidean metric in R d . Then, embed consecutively n vertices in T n d uniformly at random and independently, and let each vertex but the first one connect to its (already embedded) nearest neighbor. Call the resulting graph G n . We show multiple results concerning the degree sequence of G n . First, we prove that typically the number of vertices of degree at least k ∈ N in the d-NN tree decreases exponentially with k and is tightly concentrated by a new Lipschitz-type concentration inequality that may be of independent interest. Second, we obtain that the maximum degree of G n is of logarithmic order. Third, we give explicit bounds for the number of leaves that are independent of the dimension and also give estimates for the number of paths of length two. Moreover, we show that typically the height of a uniformly chosen vertex in G n is (1 + o (1)) log n and the diameter of T n d is (2 e + o (1)) log n , independently of the dimension. Finally, we define a natural infinite analog G ∞ of G n and show that it corresponds to the local limit of the sequence of finite graphs (G n) n ≥ 1 . Furthermore, we prove almost surely that G ∞ is locally finite, that the simple random walk on G ∞ is recurrent, and that G ∞ is connected. [ABSTRACT FROM AUTHOR]

A variety of graphical invariants have been described and tested, offering lots of applications in the fields of nanochemistry, computational networks, and different scientific research areas. One commonly studied group of invariants is the topological index, which allows research on the chemical, biological, and physical properties of a chemical structure. Topological indices are numerical quantities that can be used to describe the properties of the molecular graph. In this article, we draw from the analytically closed formulas of molecular structures of polycyclic aromatic hydrocarbons by calculating temperature-based topological indices. Our results in this paper may be useful to better understand many physical and chemical properties of polycyclic aromatic hydrocarbons. [ABSTRACT FROM AUTHOR]

We consider a Markovian model of an SIR epidemic spreading on a contact graph that is drawn uniformly at random from the set of all graphs with n vertices and given vertex degrees. Janson, Luczak and Windridge (Random Struct Alg 45(4):724–761, 2014) prove that the evolution of such an epidemic is well approximated by the solution to a simple set of differential equations, thus providing probabilistic underpinnings to the works of Miller (J Math Biol 62(3):349–358, 2011) and Volz (J Math Biol 56(3):293–310, 2008). The present paper provides an additional probabilistic interpretation of the limiting deterministic functions in Janson, Luczak and Windridge (Random Struct Alg 45(4):724–761, 2014), thus clarifying further the connection between their results and the results of Miller and Volz. [ABSTRACT FROM AUTHOR]

Wasserstein gradient flows on probability measures have found a host of applications in various optimization problems. They typically arise as the continuum limit of exchangeable particle systems evolving by some mean-field interaction involving a gradient-type potential. However, in many problems, such as in multi-layer neural networks, the so-called particles are edge weights on large graphs whose nodes are exchangeable. Such large graphs are known to converge to continuum limits called graphons as their size grows to infinity. We show that the Euclidean gradient flow of a suitable function of the edge weights converges to a novel continuum limit given by a curve on the space of graphons that can be appropriately described as a gradient flow or, more technically, a curve of maximal slope. Several natural functions on graphons, such as homomorphism functions and the scalar entropy, are covered by our setup, and the examples have been worked out in detail. [ABSTRACT FROM AUTHOR]

For a set M of vertices and an edge e of a graph G, let $ P_G(M, e) $ P G (M , e) be the set of the pair $ (x, y) $ (x , y) with a vertex x of M and a vertex y of $ V(G) $ V (G) such that $ d_G(x, y)\neq d_{G-e}(x, y) $ d G (x , y) ≠ d G − e (x , y). For a vertex x, let $ EM(x) $ EM (x) be the edge set e such that there exists a vertex v in G with $ (x, v) \in P(\{x\}, e) $ (x , v) ∈ P ({ x } , e). A set M of vertices of a graph G is distance-edge-monitoring set if every edge e of G is monitored by some vertex $ v\in M $ v ∈ M , that is, for any $ e \in E(G) $ e ∈ E (G) , we have $ P_G(M, e)\neq \emptyset $ P G (M , e) ≠ ∅. The distance-edge-monitoring number of a graph G, denoted by $ \operatorname {dem}(G) $ dem ⁡ (G) , is defined as the smallest size of distance-edge-monitoring sets of G. In this paper, we study the distance edge monitoring number of pseudo wheel graphs, that is, some variants of wheel graph. [ABSTRACT FROM AUTHOR]

Networks (graphs) permeate scientific fields such as biology, social science, economics, etc. Empirical studies have shown that real-world networks are often heterogeneous, that is, the degrees of nodes do not concentrate on a number. Recently, the Rényi index was tentatively used to measure network heterogeneity. However, the validity of the Rényi index in network settings is not theoretically justified. In this paper, we study this problem. We derive the limit of the Rényi index of a heterogeneous Erdös–Rényi random graph and a power-law random graph, as well as the convergence rates. Our results show that the Erdös–Rényi random graph has asymptotic Rényi index zero and the power-law random graph (highly heterogeneous) has asymptotic Rényi index one. In addition, the limit of the Rényi index increases as the graph gets more heterogeneous. These results theoretically justify the Rényi index is a reasonable statistical measure of network heterogeneity. We also evaluate the finite-sample performance of the Rényi index by simulation. [ABSTRACT FROM AUTHOR]

A well-known open problem on the behavior of optimal paths in random graphs in the strong disorder regime, formulated by statistical physicists, and supported by a large amount of numerical evidence over the last decade (Braunstein et al. in Phys Rev Lett 91(16):168701, 2003; Braunstein et al. in Int J Bifurc Chaos 17(07):2215–2255, 2007; Chen et al. in Phys Rev Lett 96(6):068702, 2006; Wu et al. in Phys Rev Lett 96(14):148702, 2006) is as follows: for a large class of random graph models with degree exponent τ ∈ (3 , 4) , distances in the minimal spanning tree (MST) on the giant component in the supercritical regime scale like n (τ - 3) / (τ - 1) . The aim of this paper is to make progress towards a proof of this conjecture. We consider a supercritical inhomogeneous random graph model with degree exponent τ ∈ (3 , 4) that is closely related to Aldous's multiplicative coalescent, and show that the MST constructed by assigning i.i.d. continuous weights to the edges in its giant component, endowed with the tree distance scaled by n - (τ - 3) / (τ - 1) , converges in distribution with respect to the Gromov–Hausdorff topology to a random compact real tree. Further, almost surely, every point in this limiting space either has degree one (leaf), or two, or infinity (hub), both the set of leaves and the set of hubs are dense in this space, and the Minkowski dimension of this space equals (τ - 1) / (τ - 3) . The multiplicative coalescent, in an asymptotic sense, describes the evolution of the component sizes of various near-critical random graph processes. We expect the limiting spaces in this paper to be the candidates for the scaling limit of the MST constructed for a wide array of other heavy-tailed random graph models. [ABSTRACT FROM AUTHOR]

Many real-world networks exhibit the phenomenon of edge clustering,which is typically measured by the average clustering coefficient. Recently,an alternative measure, the average closure coefficient, is proposed to quantify local clustering. It is shown that the average closure coefficient possesses a number of useful properties and can capture complementary information missed by the classical average clustering coefficient. In this paper, we study the asymptotic distribution of the average closure coefficient of a heterogeneous Erdős–Rényi random graph. We prove that the standardized average closure coefficient converges in distribution to the standard normal distribution. In the Erdős–Rényi random graph,the variance of the average closure coefficient exhibits the same phase transition phenomenon as the average clustering coefficient. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set $ V(G) $ V (G) and edge set $ E(G) $ E (G). For any $ e \in E(G) $ e ∈ E (G) and $ u,v\in V(G) $ u , v ∈ V (G) , the edge e is monitored by two vertices u and v in graph G if $ d_G(u, v) \neq d_{G-e}(u, v) $ d G (u , v) ≠ d G − e (u , v). A set M of vertices of G is a monitoring-edge-geodetic set of G if for any edge $ e \in E(G) $ e ∈ E (G) there exists a pair $ u, v\in M $ u , v ∈ M such that e is monitored by u, v. The monitoring-edge-geodetic number $ \operatorname {meg}(G) $ meg ⁡ (G) is the cardinality of the minimum MEG-set in G. In this paper, we obtain the exact values or bounds for the MEG numbers of graph products, including join, corona, cluster, lexicographic products and direct products. [ABSTRACT FROM AUTHOR]