Orthogonal Polarity Graphs and Sidon Sets

Determining the maximum number of edges in an n‐vertex C₄‐free graph is a well‐studied problem that dates back to a paper of Erd?s from 1938. One of the most important families of C₄‐free graphs are the Erd?s‐Rényi orthogonal polarity graphs. We show that the Cayley sum graph constructed using a Bose‐Chowla Sidon set is isomorphic to a large induced subgraph of the Erd?s‐Rényi orthogonal polarity graph. Using this isomorphism, we prove that the Petersen graph is a subgraph of every sufficiently large Erd?s‐Rényi orthogonal polarity graph.     

Almost all graphs are rigid—revisited

It is shown that almost all graphs are unretractive, i.e. have no endomorphisms other than their automorphisms. A more general result has already been published in [V. Koubek, V. Rödl, On the minimum order of graphs with given semigroup, J. Combin. Theory Ser. B 36 (1984) 135–155]. In the paper at hand, a different proof is presented, following an approach of P. Erdős and A. Rényi that was used in their proof [P. Erdős, A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963) 295–315] that almost all graphs are asymmetric (have a trivial automorphism group). The approach is modified using an algebraically motivated reduction to idempotent endomorphisms. These take the role of the automorphisms in the proof of Erdős and Rényi. A bound of is provided for the ratio of retractive graphs among all graphs with n vertices, confirming an earlier statement by Babai [L. Babai, Automorphism groups, isomorphism, reconstruction, in: R.L. Graham, M. Grötschel, L. Lovász (Eds.), in: Handbook of Combinatorics, vol. 2, Elsevier, Amsterdam, 1995, pp. 1447–1540]. The fact that almost all graphs are unretractive and asymmetric can be summarized in the statement that almost all graphs are rigid (have a trivial endomorphism monoid), and the same bound can be obtained for corresponding ratios of nonrigid graphs.     

On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph

The Erd?s‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that in many cases, this upper bound is sharp in the order of magnitude. Our result for the Erd?s‐Rényi graph has the following reformulation: the maximum size of a family of mutually non‐orthogonal lines in a vector space of dimension three over the finite field of order q is of order q^3/2. We also prove that every subset of vertices of size greater than q^2/2 + q^3/2 + O(q) in the Erd?s‐Rényi graph contains a triangle. This shows that an old construction of Parsons is asymptotically sharp. Several related results and open problems are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 113–127, 2007     

The birth of the giant component

Limiting distributions are derived for the sparse connected components that are present when a random graph on n vertices has approximately 1/2n edges. In particular, we show that such a graph consists entirely of trees, unicyclic components, and bicyclic components with probability approaching √2/3 cosh √5/18 ≈ 0.9325 as n→∞. The limiting probability that it is consists of trees, unicyclic components, and at most one another component is approximately 0.9957; the limiting probability that it is planar lies between 0.987 and 0.9998. When a random graph evolves and the number of edges passes 1/2n, its components grow in cyclic complexity according to an interesting Markov process whose asymptotic structure is derived. The probability that there never is more than a single component with more edges than vertices, throughout the veolution, approaches 5 π/18 ≈ 0.8727. A “uniform” model of random graphs, which allows self-loops and multiple edges, is shown to lead to formulas that are substanitially simpler than the analogous formulas for the classical random graphs of Erdõs and Rényi. The notions of “excess” and “deficiency,” which are significant characteristics of the generating function as well as of the graphs themselves, lead to a mathematically attractive structural theory for the uniform model. A general approach to the study of stopping configurations makes it possible to sharpen previously obtained estimates in a uniform manner and often to obtain closed forms for the constants of interest. Empirical results are presented to complement the analysis, indicating the typical behavior when n is near 2oooO. © 1993 John Wiley & Sons, Inc.     

On limit points of spectra of the random graph first-order properties

New bounds on the minimum and maximum limit points of spectra of first-order properties of the Erdös–Rényi random graph are obtained. These results are used to improve bounds on the minimal quantifier depths of first-order formulas with infinite spectra. Moreover, we prove that there are no limit points of the spectra in the interval (1–2^1–k , 1).     

Asymmetry and structural information in preferential attachment graphs

Graph symmetries intervene in diverse applications, from enumeration, to graph structure compression, to the discovery of graph dynamics (e.g., node arrival order inference). Whereas Erd?s‐Rényi graphs are typically asymmetric, real networks are highly symmetric. So a natural question is whether preferential attachment graphs, where in each step a new node with m edges is added, exhibit any symmetry. In recent work it was proved that preferential attachment graphs are symmetric for m = 1, and there is some nonnegligible probability of symmetry for m = 2. It was conjectured that these graphs are asymmetric when m ≥ 3. We settle this conjecture in the affirmative, then use it to estimate the structural entropy of the model. To do this, we also give bounds on the number of ways that the given graph structure could have arisen by preferential attachment. These results have further implications for information theoretic problems of interest on preferential attachment graphs.     

Moderate Deviations via Cumulants

The purpose of the present paper is to establish moderate deviation principles for a rather general class of random variables fulfilling certain bounds of the cumulants. We apply a celebrated lemma of the theory of large deviations probabilities due to Rudzkis, Saulis, and Statulevi?ius. The examples of random objects we treat include dependency graphs, subgraph-counting statistics in Erdös–Rényi random graphs and U-statistics. Moreover, we prove moderate deviation principles for certain statistics appearing in random matrix theory, namely characteristic polynomials of random unitary matrices and the number of particles in a growing box of random determinantal point processes such as the number of eigenvalues in the GUE or the number of points in Airy, Bessel, and sine random point fields.     

Graphs in which each m-tuple of vertices is adjacent to the same number n of other vertices

Let G be a finite graph in which each m-tuple of mutually distinct vertices is adjacent to exactly n other vertices. If m ≥3 then G is isomorphic to the complete m+n graph. For completeness we state the friendship theorem of Erdös, Rényi, and Sós and a theorem of Bose and Shrikhande, both of which deal with the case m=2.     

Matrix Tree Theorems

A simple proof of a directed graph generalization of the Matrix Tree Theorem, sometimes called Maxwell's rule or Kirchhoff's rule, is given. It is based on the idea A. Rényi used to prove Cayley's tree counting formula. The theorem counts rooted arborescences (analogs of forests) in a directed graph with the determinant of a submatrix in a special adjacency matrix. In the proof we show two n-k degree homogeneous polynomials in n variables are equal by applying induction to those terms lacking one variable. An application to a well-known identity and related theorems are given.     

Cooperation in changing environments: Irreversibility in the transition to cooperation in complex networks

In the framework of the evolutionary dynamics of the Prisoner’s Dilemma game on complex networks, we investigate the possibility that the average level of cooperation shows hysteresis under quasi-static variations of a model parameter (the “temptation to defect”). Under the “discrete replicator” strategy updating rule, for both Erdös–Rényi and Barabási–Albert graphs we observe cooperation hysteresis cycles provided one reaches tipping point values of the parameter; otherwise, perfect reversibility is obtained. The selective fixation of cooperation at certain nodes and its organization in cooperator clusters, that are surrounded by fluctuating strategists, allows the rationalization of the “lagging behind” behavior observed.     

The Bohman‐Frieze process near criticality

The Erd?s‐Rényi process begins with an empty graph on n vertices, with edges added randomly one at a time to the graph. A classical result of Erd?s and Rényi states that the Erd?s‐Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 (we say at time 1) and a giant component emerges. Since this seminal work of Erd?s and Rényi, various random graph models have been introduced and studied. In this paper we study the Bohman‐Frieze process, a simple modification of the Erd?s‐Rényi process. The Bohman‐Frieze process also begins with an empty graph on n vertices. At each step two random edges are presented, and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We present several new results on the phase transition of the Bohman‐Frieze process. We show that it has a qualitatively similar phase transition to the Erd?s‐Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at time t_c ? ? (that is, when the number of edges are (t_c ? ?)n/2) are trees or unicyclic components and that the largest component is of size Ω(?^‐2log n). Further, at t_c + ?, all components apart from the giant component are trees or unicyclic and the size of the second‐largest component is Θ(?^‐2log n). Each of these results corresponds to an analogous well‐known result for the Erd?s‐Rényi process. Our proof techniques include combinatorial arguments, the differential equation method for random processes, and the singularity analysis of the moment generating function for the susceptibility, which satisfies a quasi‐linear partial differential equation. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

A Generalization of a theorem of chang

Szigeti, Tuza and Révész have developed a method in [6] to obtain polynomial identities for the n×n matrix ring over a commutative ring starting from directed Eulerian graphs. These polynomials are called Euler-ian. In the first part of this paper we show some polynomials that are in the T-ideal generated by a certain set of Eulerian polynomials, hence we get some identities of the n×n matrices. This result is a generalization of a theorem of Chang [l]. After that, using this theorem, we show that any Eulerian identity arising from a graph which lias d-fold multiple edges follows from the standard identity of degree d     

On the probability of the occurrence of a copy of a fixed graph in a random distance graph

The threshold probability of the occurrence of a copy of a balanced graph in a random distance graph is obtained. The technique used by P. Erd?s and A. Rényi for determining the threshold probability for the classical random graph could not be applied in the model under consideration. In this connection, a new method for deriving estimates of the number of copies of a balanced graph in a complete distance graph is developed.     

On the connectivity of randomm-orientable graphs and digraphs

We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex. We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning trees and arborescences. We also examine the relationship between our results and certain results of Erdős and Rényi.     

Distance edge-colourings and matchings

We consider a distance generalisation of the strong chromatic index and the maximum induced matching number. We study graphs of bounded maximum degree and Erd?s–Rényi random graphs. We work in three settings. The first is that of a distance generalisation of an Erd?s–Ne?et?il problem. The second is that of an upper bound on the size of a largest distance matching in a random graph. The third is that of an upper bound on the distance chromatic index for sparse random graphs. One of our results gives a counterexample to a conjecture of Skupień.     

Transformations on density operators and on positive definite operators preserving the quantum Rényi divergence

In a certain sense we generalize the recently introduced and extensively studied notion called quantum Rényi divergence (also called ”sandwiched Rényi relative entropy”) and describe the structures of corresponding symmetries. More precisely, we characterize all transformations on the set of density operators which leave our new general quantity invariant and also determine the structure of all bijective transformations on the cone of positive definite operators which preserve the quantum Rényi divergence.     

Connectivity of a general class of inhomogeneous random digraphs

We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erd?s‐Rényi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish a phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale‐free graphs with arbitrary in‐degree/out‐degree dependence.     

A probabilistic approach to the leader problem in random graphs

We study the fixation time of the identity of the leader, that is, the most massive component, in the general setting of Aldous's multiplicative coalescent, which in an asymptotic sense describes the evolution of the component sizes of a wide array of near‐critical coalescent processes, including the classical Erd?s‐Rényi process. We show tightness of the fixation time in the “Brownian” regime, explicitly determining the median value of the fixation time to within an optimal O(1) window. This generalizes ?uczak's result for the Erd?s‐Rényi random graph using completely different techniques. In the heavy‐tailed case, in which the limit of the component sizes can be encoded using a thinned pure‐jump Lévy process, we prove that only one‐sided tightness holds. This shows a genuine difference in the possible behavior in the two regimes.     

Functional Erdös-Rényi laws for processes indexed by sets

We consider a process X(A) indexed by some sets A∈A, where A is a collection of sets. We prove a functional form of the Erdös-Rényi laws. The result may be specialized to get back and sometimes improve previous versions of the classical Erdös-Rényi laws.     

Strong sufficient conditions for the existence of Hamiltonian circuits in undirected graphs

In this paper, we derive some results giving sufficient conditions for a graph G containing a Hamiltonian path to be Hamiltonian. In particular the Bondy-Chvátal theorem [J. A. Bondy and V. Chvátal, Discrete Math. 15 (1976), 111–135] is derived as a corollary of the main theorem of this paper and hence a more powerful closure operation than the one introduced by Bondy and Chvátal is defined. These results can be viewed as a step towards a unification of the various known results on the existence of Hamiltonian circuits in undirected graphs. Moreover, Theorem 1 of this paper provides a counterpart of the Chvátal-Erdös theorem [V. Chvátal and P. Erdös, Discrete Math. 2 (1972), 111–113] which gives a sufficient condition for a Hamiltonian circuit in terms of global vertex connectivity and independence number.