Search

In [Trans. Am. Math. Soc. 375 (2022), no. 1, 627–668], Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let r⩾3$$ r\geqslant 3 $$ and let n$$ n $$ be divisible by r$$ r $$. Then, in the random r$$ r $$‐uniform hypergraph process on n$$ n $$ vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we prove the analogue of this result for clique factors in the random graph process: at the time that the last vertex joins a copy of the complete graph Kr$$ {K}_r $$, the random graph process contains a Kr$$ {K}_r $$‐factor. Our proof draws on a novel sequence of couplings which embeds the random hypergraph process into the cliques of the random graph process. An analogous result is proved for clique factors in the s$$ s $$‐uniform hypergraph process (s⩾3$$ s\geqslant 3 $$). [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 determine the distribution of the sandpile group (also known as the Jacobian) of the Erdős–Rényi random graph G(n,q) along with its canonical duality pairing as n tends to infinity, fully resolving a conjecture due to Clancy, Leake, and Payne [Exp. Math. 24 (2015), pp. 1–7] and generalizing the result by Wood [J. Amer. Math. Soc. 30 (2017), pp. 915–958] on the groups. In particular, we show that a finite abelian p-group G equipped with a perfect symmetric pairing \delta appears as the Sylow p-part of the sandpile group and its pairing with frequency inversely proportional to |G| |\operatorname {Aut}(G,\delta)|, where \operatorname {Aut}(G,\delta) is the set of automorphisms of G preserving the pairing \delta. While this distribution is related to the Cohen–Lenstra distribution, the two distributions are not the same on account of the additional algebraic data of the pairing. The proof utilizes the moment method: we first compute a complete set of moments for our random variable (the average number of epimorphisms from our random object to a fixed object in the category of interest) and then show the moments determine the distribution. To obtain the moments, we prove a universality result for the moments of cokernels of random symmetric integral matrices whose dual groups are equipped with symmetric pairings that is strong enough to handle both the dependence in the diagonal entries and the additional data of the pairing. We then apply results due to Sawin and Wood [ The moment problem for random objects in a category , preprint] to show that these moments determine a unique distribution. [ABSTRACT FROM AUTHOR]

We consider two general classes of multiplicative degree-based topological indices (MTIs), denoted by $ X_{\Pi, F_V}(G) = \prod_{u \in V(G)} F_V(d_u) $ and $ X_{\Pi, F_E}(G) = \prod_{uv \in E(G)} F_E(d_u, d_v) $, where $ uv $ indicates the edge of $ G $ connecting the vertices $ u $ and $ v $, $ d_u $ is the degree of the vertex $ u $, and $ F_V(x) $ and $ F_E(x, y) $ are functions of the vertex degrees. This work has three objectives: First, we follow an analytical approach to deal with a classical topic in the study of topological indices: to find inequalities that relate two MTIs between them, but also to their additive versions $ X_\Sigma(G) $. Second, we propose some statistical analysis of MTIs as a generic tool for studying average properties of random networks, extending these techniques for the first time to the context of MTIs. Finally, we perform an innovative scaling analysis of MTIs which allows us to state a scaling law that relates different random graph models.

We consider the two-opinion voter model on a regular random graph with n vertices and degree d = 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 (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. [ABSTRACT FROM AUTHOR]

Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove n edges from G to make it H-minor-free (for some small constant > 0). We give an n1/2+o(1)-time randomized procedure that, with high probability, finds an H-minor in such a graph. As an application, suppose one must remove n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K3,3- or K5-minor in G. No prior sublinear time bound was known for this problem. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to no(1) factors, this resolves a conjecture of Benjamini, Schramm, and Shapira [Adv. Math., 223 (2010), pp. 2200--2218] on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal by a n) lower bound of Czumaj et al. [Random Structures Algorithms, 45 (2014), pp. 139--184]. Prior to this work, the only graphs H for which nontrivial one-sided property testers were known for H-minor-freeness were the following: H being a forest or a cycle [Czumaj et al., Random Structures Algorithms, 45 (2014), pp. 139--184], K2,k, (k2)-grid, and the k-circus [Fichtenberger et al., preprint, arXiv:1707.06126v1, 2017]. [ABSTRACT FROM AUTHOR]

We consider the Norros-Reittu random graph NRn(w), where edges are present independently but edge probabilities are moderated by vertex weights, and use probabilistic arguments based on martingales to study component sizes in this model when considered at criticality. In particular, we obtain stronger bounds (with respect to those available in the literature) for the probability of observing an unusually large maximal cluster and simplify the arguments needed to derive (polynomial) bounds for the probability of observing an unusually small largest component. [ABSTRACT FROM AUTHOR]

We determine the asymptotic distribution of the p-rank of the sandpile groups of random bipartite graphs. We see that this depends on the ratio between the number of vertices on each side, with a threshold when the ratio between the sides is equal to 1 p . We follow the approach of Wood (J Am Math Soc 30(4):915–958, 2017) and consider random graphs as a special case of random matrices, and rely on a variant the definition of min-entropy given by Maples (Cokernels of random matrices satisfy the Cohen–Lenstra heuristics, 2013) to obtain useful results about these random matrices. Our results show that unlike the sandpile groups of Erdős–Rényi random graphs, the distribution of the sandpile groups of random bipartite graphs depends on the properties of the graph, rather than coming from some more general random group model. [ABSTRACT FROM AUTHOR]

In this note we study inhomogeneous random bipartite graphs in random environment. These graphs can be thought of as an extension of the classical Erd\H os-R\'enyi random bipartite graphs in a random environment. We show that the expected number of perfect matchings obeys a precise asymptotic.

The aim of this work is to obtain new inequalities for the variable symmetric division deg index $ SDD_\alpha(G) = \sum_{uv \in E(G)} (d_u^\alpha/d_v^\alpha+d_v^\alpha/d_u^\alpha) $, and to characterize graphs extremal with respect to them. Here, by $ uv $ we mean the edge of a graph $ G $ joining the vertices $ u $ and $ v $, and $ d_u $ denotes the degree of $ u $, and $ \alpha \in \mathbb{R} $. Some of these inequalities generalize and improve previous results for the symmetric division deg index. In addition, we computationally apply the $ SDD_\alpha(G) $ index on random graphs and we demonstrate that the ratio $ \langle SDD_\alpha(G) \rangle/n $ ($ n $ is the order of the graph) depends only on the average degree $ \langle d \rangle $.

The concentration of the sizes of largest induced paths and cycles (holes) is studied in Erdős-Rényi random graphs. A 2-point concentration is proved for the size of the largest induced path and cycle for all p=p(n) satisfying p≥n-1/2(lnn)2 and p≤1-ε, where ε>0 is any constant. No such tight concentration (within two consecutive values) was previously known for induced paths and cycles. As a corollary, a significant additive improvement is obtained over a 40-year-old result of Erdős and Palka [Discrete Math., 46 (1983), pp. 145-150] concerning the size of the largest induced tree in a dense random graph. Further, the induced path decomposition number and induced tree decomposition number, i.e., the smallest number of parts into which the vertex set of a graph can be partitioned such that every part induces a (i) path or (ii) tree, respectively, are studied for G(n,p). The arguments involve the second moment method together with an adaptation of a martingale-based technique of Krivelevich et al. [Random Structures Algorithms, 22 (2003), pp. 1-14] for monotone high-degree polynomial random variables to the nonmonotone setting. A lower bound is proved showing the tightness of the application of the inequality up to logarithmic factors in the exponent. The modified inequality is then stated and proved in a general setting, which may be of independent interest. [ABSTRACT FROM AUTHOR]

Our object of study is the asymptotic growth of heaviest paths in a charged (weighted with signed weights) complete directed acyclic graph. Edge charges are i.i.d. random variables with common distribution F supported on [-∞; 1] with essential supremum equal to 1 (a charge of -∞ is understood as the absence of an edge). The asymptotic growth rate is a constant that we denote by C(F). Even in the simplest case where F = pδ1 + (1 - p)δ-∞, corresponding to the longest path in the Barak-Erdos random graph, there is no closed-form expression for this function, but good bounds do exist. In this paper we construct a Markovian particle system that we call "Max Growth System" (MGS), and show how it is related to the charged random graph. The MGS is a generalization of the Infinite Bin Model that has been the object of study of a number of papers. We then identify a random functional of the process that admits a stationary version and whose expectation equals the unknown constant C(F). Furthermore, we construct an effective perfect simulation algorithm for this functional which produces samples from the random functional. [ABSTRACT FROM AUTHOR]

A singular graph G, defined when its adjacency matrix is singular, has important applications in mathematics, natural sciences and engineering. The chemical importance of singular graphs lies in the fact that if the molecular graph is singular, the nullity (the number of the zero eigenvalue) is greater than 0, then the corresponding chemical compound is highly reactive or unstable. By this reasoning, chemists have a great interest in this problem. Thus, the problem of characterization singular graphs was proposed and raised extensive studies on this challenging problem thereafter. The graph obtained by conglutinating the starting vertices of three paths P s 1 , P s 2 , P s 3 into a vertex, and three end vertices into a vertex on the cycle C a 1 , C a 2 , C a 3 , respectively, is denoted as γ (a 1 , a 2 , a 3 , s 1 , s 2 , s 3) . Note that δ (a 1 , a 2 , a 3 , s 1 , s 2) = γ (a 1 , a 2 , a 3 , s 1 , 1 , s 2) , ζ (a 1 , a 2 , a 3 , s) = γ (a 1 , a 2 , a 3 , 1 , 1 , s) , φ (a 1 , a 2 , a 3) = γ (a 1 , a 2 , a 3 , 1 , 1 , 1) . In this paper, we give the necessity and sufficiency that the γ − graph, δ − graph, ζ − graph and φ − graph are singular and prove that the probability that a randomly given γ − graph, δ − graph, ζ − graph or φ − graph being singular is equal to 325 512 , 165 256 , 43 64 , 21 32 , respectively. From our main results, we can conclude that such a γ − graph( δ − graph, ζ − graph, φ − graph) is singular if at least one cycle is a multiple of 4 in length, and surprisingly, the theoretical probability of these graphs being singular is more than half. This result promotes the understanding of a singular graph and may be promising to propel the solutions to relevant application problems. [ABSTRACT FROM AUTHOR]

Kim, Kühn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655–4742) greatly extended the well-known blow-up lemma of Komlós, Sárközy and Szemerédi by proving a 'blow-up lemma for approximate decompositions' which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, Kühn and Osthus to prove the tree packing conjecture due to Gyárfás and Lehel from 1976 and Ringel's conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, Kühn and Osthus. Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties which is useful for potential applications. [ABSTRACT FROM AUTHOR]

Kim and Vu made the following conjecture (Advances in Mathematics, 2004): if d ≫ log n , then the random d-regular graph G (n , d) can asymptotically almost surely be "sandwiched" between G (n , p 1) and G (n , p 2) where p 1 and p 2 are both (1 + o (1)) d / n . They proved this conjecture for log n ≪ d ⩾ n 1 / 3 - o (1) , with a defect in the sandwiching: G (n , d) contains G (n , p 1) perfectly, but is not completely contained in G (n , p 2) . The embedding G (n , p 1) ⊆ G (n , d) was improved by Dudek, Frieze, Ruciński and Šileikis to d = o (n) . In this paper, we prove Kim–Vu's sandwich conjecture, with perfect containment on both sides, for all d where min { d , n - d } ≫ n / log n . The sandwich theorem allows translation of many results from G (n , p) to G (n , d) such as Hamiltonicity, the chromatic number, the diameter, etc. It also allows translation of threshold functions of phase transitions from G (n , p) to bond percolation of G (n , d) . In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability of small subgraph appearances in a random factor of a pseudorandom graph, which is of independent interest. [ABSTRACT FROM AUTHOR]

Given k⩾2$k\geqslant 2$ and two k$k$‐graphs (k$k$‐uniform hypergraphs) F$F$ and H$H$, an F$F$‐factor in H$H$ is a set of vertex‐disjoint copies of F$F$ that together cover the vertex set of H$H$. Lenz and Mubayi [J. Combin. Theory Ser. B, 2016] studied the F$F$‐factor problem in quasi‐random k$k$‐graphs with minimum degree Ω(nk−1)$\Omega (n^{k-1})$. They posed the problem of characterizing the k$k$‐graphs F$F$ such that every sufficiently large quasi‐random k$k$‐graph with constant edge density and minimum degree Ω(nk−1)$\Omega (n^{k-1})$ contains an F$F$‐factor, and, in particular, they showed that all linear k$k$‐graphs satisfy this property. In this paper we prove a general theorem on F$F$‐factors which reduces the F$F$‐factor problem of Lenz and Mubayi to a natural sub‐problem, that is, the F$F$‐cover problem. By using this result, we answer the question of Lenz and Mubayi for those F$F$ which are k$k$‐partite k$k$‐graphs, and for all 3‐graphs F$F$, separately. Our characterization result on 3‐graphs is motivated by the recent work of Reiher, Rödl, and Schacht [J. Lond. Math. Soc., 2018] that classifies the 3‐graphs with vanishing Turán density in quasi‐random k$k$‐graphs. [ABSTRACT FROM AUTHOR]

We consider a class of sparse random matrices which includes the adjacency matrix of the Erdős–Rényi graph G (N , p) . We show that if N ε ⩽ N p ⩽ N 1 / 3 - ε then all nontrivial eigenvalues away from 0 have asymptotically Gaussian fluctuations. These fluctuations are governed by a single random variable, which has the interpretation of the total degree of the graph. This extends the result (Huang et al. in Ann Prob 48:916–962, 2020) on the fluctuations of the extreme eigenvalues from N p ⩾ N 2 / 9 + ε down to the optimal scale N p ⩾ N ε . The main technical achievement of our proof is a rigidity bound of accuracy N - 1 / 2 - ε (N p) - 1 / 2 for the extreme eigenvalues, which avoids the (N p) - 1 -expansions from Erdős et al. (Ann Prob 41:2279–2375, 2013), Huang et al. (2020) and Lee and Schnelli (Prob Theor Rel Fields 171:543–616, 2018). Our result is the last missing piece, added to Erdős et al. (Commun Math Phys 314:587–640, 2012), He (Bulk eigenvalue fluctuations of sparse random matrices. arXiv:1904.07140), Huang et al. (2020) and Lee and Schnelli (2018), of a complete description of the eigenvalue fluctuations of sparse random matrices for N p ⩾ N ε . [ABSTRACT FROM AUTHOR]

Consider an infinite planar graph with uniform polynomial growth of degree d > 2 . Many examples of such graphs exhibit similar geometric and spectral properties, and it has been conjectured that this is necessary. We present a family of counterexamples. In particular, we show that for every rational d > 2 , there is a planar graph with uniform polynomial growth of degree d on which the random walk is transient, disproving a conjecture of Benjamini (Coarse Geometry and Randomness, Volume 2100 of Lecture Notes in Mathematics. Springer, Cham, 2011). By a well-known theorem of Benjamini and Schramm, such a graph cannot be a unimodular random graph. We also give examples of unimodular random planar graphs of uniform polynomial growth with unexpected properties. For instance, graphs of (almost sure) uniform polynomial growth of every rational degree d > 2 for which the speed exponent of the walk is larger than 1/d, and in which the complements of all balls are connected. This resolves negatively two questions of Benjamini and Papasoglou (Proc Am Math Soc 139(11):4105–4111, 2011). [ABSTRACT FROM AUTHOR]

Here we present the entropic dynamics formalism for networks. That is, a framework for the dynamics of graphs meant to represent a network derived from the principle of maximum entropy and the rate of transition is obtained taking into account the natural information geometry of probability distributions. We apply this framework to the Gibbs distribution of random graphs obtained with constraints on the node connectivity. The information geometry for this graph ensemble is calculated and the dynamical process is obtained as a diffusion equation. We compare the steady state of this dynamics to degree distributions found on real-world networks.

This paper examines bounds on upper tails for cycle counts in Gn,p. For a fixed graph H define ξH =ξn,p H to be the number of copies of H in Gn,p. It is a much studied and surprisingly difficult problem to understand the upper tail of the distribution of ξH, for example, to estimate P(ξH > 2EξH). The best known result for general H and p is due to Janson, Oleszkiewicz, and Ruciński [Israel J. Math., 142 (2004), pp. 61--92], who proved that exp[ OH,η (MH(n, p) ln(1/p))] < P(ξH > (1 + η )EξH) < exp[-Ω H,η (MH(n, p))]. Thus they determined the upper tail up to a factor of ln(1/p) in the exponent. There has since been substantial work to improve these bounds for particular H and p. We close the ln(1/p) gap for cycles, up to a constant in the exponent. Here the lower bound stated above is accurate for l-cycles when p > ln¹/(l-2)n/n. [ABSTRACT FROM AUTHOR]

We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst-case approximation ratio of this heuristic is 2. We have the following results: (a) In the one-dimension-al case, with uniform [0, 1]-distributed distances, the expected approximation ratio is bounded above by $2 - 2/(\myp+2)$, where $\myp$ denotes the distance power gradient. (b) For the complete graph, with uniform [0, 1] distributed edge weights, the expected approximation ratio is bounded above by 2 − 1 / 2ζ(3), where ζ denotes the Riemann zeta function.

Many real systems can be described by a set of interacting entities forming a complex network. To some surprise, these have been shown to share a number of structural properties regardless of their type or origin. It is thus of vital importance to design simple and intuitive models that can explain their intrinsic structure and dynamics. These can, for instance, be used to study networks analytically or to construct networks not observed in real life. Most models proposed in the literature are of two types. A model can be either static, where edges are added between a fixed set of nodes according to some predefined rule, or evolving, where the number of nodes or edges increases over time. However, some real networks do not grow but rather shrink, meaning that the number of nodes or edges decreases over time. We here propose a simple model of shrinking networks called the war pact model. We show that networks generated in such a way exhibit common structural properties of real networks. Furthermore, compared to classical models, these resemble international trade, correlates of war, Bitcoin transactions and other networks more closely. Network shrinking may therefore represent a reasonable explanation of the evolution of some networks and greater emphasis should be put on such models in the future. [ABSTRACT FROM AUTHOR]

We study pairs of graphs (H1;H2) such that every graph with the densities of H1 and H2 close to the densities of H1 and H2 in a random graph is quasirandom; such pairs (H1;H2) are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, Hán, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40 (2012), no. 1, 1{38]: they showed that (Kt; F) is forcing where F is the graph that arises from Kt by iteratively doubling its vertices and edges in a prescribed way t times. Reiher and Schacht [Forcing quasirandomness with triangles, Forum of Mathematics, Sigma. Vol. 7, 2019] strengthened this result for t = 3 by proving that two doublings suffice and asked for the minimum number of doublings needed for t > 3. We show that d(t + 1)=2e doublings always suffice. [ABSTRACT FROM AUTHOR]

In life sciences, accompanied by the rapid growth of sequencing technology and the advancement of research, vast amounts of data are being generated. It is known that as the size of Resource Description Framework (RDF) datasets increases, the more efficient loading to triple stores is crucial. For example, UniProt’s RDF version contains 44 billion triples as of December 2018. PubChem also has an RDF dataset with 137 billion triples. As data sizes become extremely large, loading them to a triple store consumes time. To improve the efficiency of this task, parallel loading has been recommended for several stores. However, with parallel loading, dataset consistency must be considered if the dataset contains blank nodes. By definition, blank nodes do not have global identifiers; thus, pairs of identical blank nodes in the original dataset are recognized as different if they reside in separate files after the dataset is split for parallel loading. To address this issue, we propose the Split4Blank tool, which splits a dataset into multiple files under the condition that identical blank nodes are not separated. The proposed tool uses connected component and multiprocessor scheduling algorithms and satisfies the above condition. Furthermore, to confirm the effectiveness of the proposed approach, we applied Split4Blank to two life sciences RDF datasets. In addition, we generated synthetic RDF datasets to evaluate scalability based on the properties of various graphs, such as a scale-free and random graph. [ABSTRACT FROM AUTHOR]

A family F of graphs on a fixed set of n vertices is called triangle-intersecting if for any G1,G2∈F, the intersection G1∩G2 contains a triangle. More generally, for a fixed graph H, a family F is H-intersecting if the intersection of any two graphs in F contains a sub-graph isomorphic to H. In [D. Ellis, Y. Filmus, and E. Friedgut, Triangle-intersecting families of graphs, J. Eur. Math. Soc. 14 (2012), pp. 841--885], Ellis, Filmus and Friedgut proved a 36-year old conjecture of Simonovits and Sós stating that the maximal size of a triangle-intersecting family is (1/8)2n(n-1)/2. Furthermore, they proved a p-biased generalization, stating that for any p≤1/2, we have μp(F)≤p3, where μp(F) is the probability that the random graph G(n,p) belongs to F. In the same paper, Ellis et al. conjectured that the assertion of their biased theorem holds also for 1/21/2, an H-intersecting family F of graphs such that μp(F)≥1--n2/C, where C depends only on H and p, thus disproving both conjectures. [ABSTRACT FROM AUTHOR]

Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris, and Samotij [J. Amer. Math. Soc., 28 (2015), pp. 669--709], and independently Saxton and Thomason [Invent. Math., 201 (2015), pp. 925--992], developed very general container theorems for independent sets in hypergraphs, both of which have seen numerous applications to a wide range of problems. In this paper we use the container method to give relatively short and elementary proofs of a number of results concerning Ramsey (and Turán) properties of (hyper)graphs and the integers. In particular we do the following: (a) We generalize the random Ramsey theorem of Rödl and Ruciński [Combinatorics, Paul Erdős Is Eighty, Vol. 1, Bolyai Soc. Math. Stud., János Bolyai Mathematical Society, Budapest, 1993, pp. 317--346; Random Structures Algorithms, 5 (1994), pp. 253--270; J. Amer. Math. Soc., 8 (1995), pp. 917--942] by providing a resilience analogue. Our result unifies and generalizes several fundamental results in the area including the random version of Turán's theorem due to Conlon and Gowers [Ann. of Math., 184 (2016), pp. 367--454] and Schacht [Ann. of Math., 184 (2016), pp. 331--363]. (b) The above result also resolves a general subcase of the asymmetric random Ramsey conjecture of Kohayakawa and Kreuter [Random Structures Algorithms, 11 (1997), pp. 245--276]. (c) All of the above results in fact hold for uniform hypergraphs. (d) For a (hyper)graph H, we determine, up to an error term in the exponent, the number of n-vertex (hyper)graphs G that have the Ramsey property with respect to H (that is, whenever G is r-colored, there is a monochromatic copy of H in G). (e) We strengthen the random Rado theorem of Friedgut, Rödl, and Schacht [Random Structures Algorithms, 37 (2010), pp. 407--436] by proving a resilience version of the result. (f) For partition regular matrices A we determine, up to an error term in the exponent, the number of subsets of { 1, . . . , n} for which there exists an r-coloring which contains no monochromatic solutions to Ax = 0. Along the way a number of open problems are posed. [ABSTRACT FROM AUTHOR]

The famous Pósa‐Seymour conjecture, confirmed in 1998 by Komlós, Sárközy, and Szemerédi, states that for any k ≥ 2, every graph on n vertices with minimum degree kn/(k + 1) contains the kth power of a Hamilton cycle. We extend this result to a sparse random setting. We show that for every k ≥ 2 there exists C > 0 such that if p≥C(logn/n)1/k then w.h.p. every subgraph of a random graph Gn,p with minimum degree at least (k/(k + 1) + o(1))np, contains the kth power of a cycle on at least (1 − o(1))n vertices, improving upon the recent results of Noever and Steger for k = 2, as well as Allen, Böttcher, Ehrenmüller, and Taraz for k ≥ 3. Our result is almost best possible in three ways: for p ≪ n−1/k the random graph Gn,p w.h.p. does not contain the kth power of any long cycle; there exist subgraphs of Gn,p with minimum degree (k/(k + 1) + o(1))np and Ω(p−2) vertices not belonging to triangles; there exist subgraphs of Gn,p with minimum degree (k/(k + 1) − o(1))np which do not contain the kth power of a cycle on (1 − o(1))n vertices. [ABSTRACT FROM AUTHOR]

Recently, emergence of signaling conventions, among which language is a prime example, draws a considerable interdisciplinary interest ranging from game theory, to robotics to evolutionary linguistics. Such a wide spectrum of research is based on much different assumptions and methodologies, but complexity of the problem precludes formulation of a unifying and commonly accepted explanation. We examine formation of signaling conventions in a framework of a multi-agent reinforcement learning model. When the network of interactions between agents is a complete graph or a sufficiently dense random graph, a global consensus is typically reached with the emerging language being a nearly unique object-word mapping or containing some synonyms and homonyms. On finite-dimensional lattices, the model gets trapped in disordered configurations with a local consensus only. Such a trapping can be avoided by introducing a population renewal, which in the presence of superlinear reinforcement restores an ordinary surface-tension driven coarsening and considerably enhances formation of efficient signaling. [ABSTRACT FROM AUTHOR]

The evolutionary dynamics of a finite population where resident individuals are replaced by mutant ones depends on its spatial structure. Usually, the population adopts the form of an undirected graph where the place occupied by each individual is represented by a vertex and it is bidirectionally linked to the places that can be occupied by its offspring. There are undirected graph structures that act as amplifiers of selection increasing the probability that the offspring of an advantageous mutant spreads through the graph reaching any vertex. But there also are undirected graph structures acting as suppressors of selection where this probability is less than that of the same individual placed in a homogeneous population. Here, firstly, we present the distribution of these evolutionary regimes for all undirected graphs with N ≤ 10 vertices. Some of them exhibit transitions between different regimes when the mutant fitness increases. In particular, as it has been already observed for small-order random graphs, we show that most graphs of order N ≤ 10 are amplifiers of selection. Secondly, we describe examples of amplifiers of order 7 that become suppressors from some critical value. In fact, for graphs of order N ≤ 7, we apply computer-aided techniques to symbolically compute their fixation probability and then their evolutionary regime, as well as the critical values for which they change their regime. Thirdly, the same technique is applied to some families of highly symmetrical graphs as a mean to explore methods of suppressing selection. The existence of suppression mechanisms that reverse an amplification regime when fitness increases could have a great interest in biology and network science. Finally, the analysis of all graphs from order 8 to order 10 reveals a complex and rich evolutionary dynamics, with multiple transitions between different regimes, which have not been examined in detail until now. [ABSTRACT FROM AUTHOR]

Preferential attachment networks with power law exponent τ>3 are known to exhibit a phase transition. There is a value ρc>0 such that, for small edge densities ρ≤ρc every component of the graph comprises an asymptotically vanishing proportion of vertices, while for large edge densities ρ>ρc there is a unique giant component comprising an asymptotically positive proportion of vertices. In this paper we study the decay in the size of the giant component as the critical edge density is approached from above. We show that the size decays very rapidly, like exp(-c/ρ-ρc) for an explicit constant c>0 depending on the model implementation. This result is in contrast to the behaviour of the class of rank-one models of scale-free networks, including the configuration model, where the decay is polynomial. Our proofs rely on the local neighbourhood approximations of Dereich and Mörters (Ann Probab 41(1):329-384, 2013) and recent progress in the theory of branching random walks (Gantert et al. in Ann Inst Henri Poincaré Probab Stat 47(1):111-129, 2011). [ABSTRACT FROM AUTHOR]

A notorious problem in mathematics and physics is to create a solvable model for random sequential adsorption of non-overlapping congruent spheres in the d-dimensional Euclidean space with d≥2. Spheres arrive sequentially at uniformly chosen locations in space and are accepted only when there is no overlap with previously deposited spheres. Due to spatial correlations, characterizing the fraction of accepted spheres remains largely intractable. We study this fraction by taking a novel approach that compares random sequential adsorption in Euclidean space to the nearest-neighbor blocking on a sequence of clustered random graphs. This random network model can be thought of as a corrected mean-field model for the interaction graph between the attempted spheres. Using functional limit theorems, we characterize the fraction of accepted spheres and its fluctuations. [ABSTRACT FROM AUTHOR]

Even though power-law or close-to-power-law degree distributions are ubiquitously observed in a great variety of large real networks, the mathematically satisfactory treatment of random power-law graphs satisfying basic statistical requirements of realism is still lacking. These requirements are: sparsity, exchangeability, projectivity, and unbiasedness. The last requirement states that entropy of the graph ensemble must be maximized under the degree distribution constraints. Here we prove that the hypersoft configuration model, belonging to the class of random graphs with latent hyperparameters, also known as inhomogeneous random graphs or W-random graphs, is an ensemble of random power-law graphs that are sparse, unbiased, and either exchangeable or projective. The proof of their unbiasedness relies on generalized graphons, and on mapping the problem of maximization of the normalized Gibbs entropy of a random graph ensemble, to the graphon entropy maximization problem, showing that the two entropies converge to each other in the large-graph limit. [ABSTRACT FROM AUTHOR]

Natural disasters like hurricanes, floods or earthquakes can damage power grid devices and create cascading blackouts and islands. The nature of failure propagation and extent of damage, among other factors, is dependent on the structural features of the grid, that are distinct from that of random networks. This paper analyzes the structural vulnerability of real power grids to impending disasters and presents intuitive graphical metrics to quantify the extent of topological damage. We develop two improved graph eigen-value based bounds on the grid vulnerability. Further we study adversarial attacks aimed at weakening the grid’s structural robustness and present three combinatorial algorithms to determine the optimal topological attack. Simulations on power grid networks and comparison with existing work show the improvements of the proposed measures and attack schemes. [ABSTRACT FROM AUTHOR]

Graph drawing, or the automatic layout of graphs, is a challenging problem. There are several search based methods for graph drawing which are based on optimizing an objective function which is formed from a weighted sum of multiple criteria. In this paper, we propose a new neighbourhood search method which uses a tabu search coupled with path relinking to optimize such objective functions for general graph layouts with undirected straight lines. To our knowledge, before our work, neither of these methods have been previously used in general multi-criteria graph drawing. Tabu search uses a memory list to speed up searching by avoiding previously tested solutions, while the path relinking method generates new solutions by exploring paths that connect high quality solutions. We use path relinking periodically within the tabu search procedure to speed up the identification of good solutions. We have evaluated our new method against the commonly used neighbourhood search optimization techniques: hill climbing and simulated annealing. Our evaluation examines the quality of the graph layout (objective function’s value) and the speed of layout in terms of the number of evaluated solutions required to draw a graph. We also examine the relative scalability of each method. Our experimental results were applied to both random graphs and a real-world dataset. We show that our method outperforms both hill climbing and simulated annealing by producing a better layout in a lower number of evaluated solutions. In addition, we demonstrate that our method has greater scalability as it can layout larger graphs than the state-of-the-art neighbourhood search methods. Finally, we show that similar results can be produced in a real world setting by testing our method against a standard public graph dataset. [ABSTRACT FROM AUTHOR]

Complex innovations– ideas, practices, and technologies that hold uncertain benefits for potential adopters—often vary in their ability to diffuse in different communities over time. To explain why, I develop a model of innovation adoption in which agents engage in naïve (DeGroot) learning about the value of an innovation within their social networks. Using simulations on Bernoulli random graphs, I examine how adoption varies with network properties and with the distribution of initial opinions and adoption thresholds. The results show that: (i) low-density and high-asymmetry networks produce polarization in influence to adopt an innovation over time, (ii) increasing network density and asymmetry promote adoption under a variety of opinion and threshold distributions, and (iii) the optimal levels of density and asymmetry in networks depend on the distribution of thresholds: networks with high density (>0.25) and high asymmetry (>0.50) are optimal for maximizing diffusion when adoption thresholds are right-skewed (i.e., barriers to adoption are low), but networks with low density (<0.01) and low asymmetry (<0.25) are optimal when thresholds are left-skewed. I draw on data from a diffusion field experiment to predict adoption over time and compare the results to observed outcomes. [ABSTRACT FROM AUTHOR]

The spectrum of a first order sentence is the set of all α such that G ( n , n − α ) does not obey zero–one law with respect to this sentence. In this paper, we prove that the minimal number of quantifier alternations of a first order sentence with infinite spectrum equals 3. We have also proved that the spectrum of a first-order sentence with quantifier depth 4 has no limit points except possibly the points 1 ∕ 2 and 3 ∕ 5 . [ABSTRACT FROM AUTHOR]

Identifying hierarchies and rankings of nodes in directed graphs is fundamental in many applications such as social network analysis, biology, economics, and finance. A recently proposed method identifies the hierarchy by finding the ordered partition of nodes which minimises a score function, termed agony. This function penalises the links violating the hierarchy in a way depending on the strength of the violation. To investigate the resolution of ranking hierarchies we introduce an ensemble of random graphs, the Ranked Stochastic Block Model. We find that agony may fail to identify hierarchies when the structure is not strong enough and the size of the classes is small with respect to the whole network. We analytically characterise the resolution threshold and we show that an iterated version of agony can partly overcome this resolution limit. [ABSTRACT FROM AUTHOR]

Building upon the theory of graph limits and the Aldous–Hoover representation and inspired by Panchenko’s work on asymptotic Gibbs measures [Annals of Probability 2013], we construct continuous embeddings of discrete probability distributions. We show that the theory of graph limits induces a meaningful notion of convergence and derive a corresponding version of the Szemerédi regularity lemma. Moreover, complementing recent work Bapst et al. (2015), we apply these results to Gibbs measures induced by sparse random factor graphs and verify the “replica symmetric solution” predicted in the physics literature under the assumption of non-reconstruction. [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

Though the small-world phenomenon is widespread in many real networks, it is still challenging to replicate a large network at the full scale for further study on its structure and dynamics when sufficient data are not readily available. We propose a method to construct a Watts-Strogatz network using a sample from a small-world network with symmetric degree distribution. Our method yields an estimated degree distribution which fits closely with that of a Watts-Strogatz network and leads into accurate estimates of network metrics such as clustering coefficient and degree of separation. We observe that the accuracy of our method increases as network size increases. [ABSTRACT FROM AUTHOR]