The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

On the noise sensitivity of monotone functions

It is known that for all monotone functions f : {0, 1}ⁿ → {0, 1}, if x ∈ {0, 1}ⁿ is chosen uniformly at random and y is obtained from x by flipping each of the bits of x independently with probability ? = n^?α, then P[f(x) ≠ f(y)] < cn^?α+1/2, for some c > 0. Previously, the best construction of monotone functions satisfying P[f_n(x) ≠ f_n(y)] ≥ δ, where 0 < δ < 1/2, required ? ≥ c(δ)n^?α, where α = 1 ? ln 2/ln 3 = 0.36907 …, and c(δ) > 0. We improve this result by achieving for every 0 < δ < 1/2, P[f_n(x) ≠ f_n(y)] ≥ δ, with:

• ? = c(δ)n^?α for any α < 1/2, using the recursive majority function with arity k = k(α);
• ? = c(δ)n^?1/2log^tn for t = log₂ = .3257 …, using an explicit recursive majority function with increasing arities; and
• ? = c(δ)n^?1/2, nonconstructively, following a probabilistic CNF construction due to Talagrand.

We also study the problem of achieving the best dependence on δ in the case that the noise rate ? is at least a small constant; the results we obtain are tight to within logarithmic factors. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 333–350, 2003     

Maximal triangle-free graphs with restrictions on the degrees

We investigate the problem that at least how many edges must a maximal triangle-free graph on n vertices have if the maximal valency is ≤D. Denote this minimum value by F(n, D). For large enough n, we determine the exact value of F(n, D) if D ≥ (n ? 2)/2 and we prove that lim F(n, cn)/n = K(c) exists for all 0 < c with the possible exception of a sequence c_k → 0. The determination of K(c) is a finite problem on all intervals [γ, ∞). For D = cn^?, 1/2 < ? < 1, we give upper and lower bounds for F(n, D) differing only in a constant factor. (Clearly, D < (n - 1)^1/2 is impossible in a maximal triangle-free graph.)     

Extremal problems for triple systems

In this article Turán-type problems for several triple systems arising from (k, k ? 2)-configurations [i.e. (k ? 2) triples on k vertices] are considered. It will be shown that every Steiner triple system contains a (k, k ? 2)-configuration for some k < c log n/ log log n. Moreover, the Turán numbers of (k, k ? 2)-trees are determined asymptotically to be ((k ? 3)/3).(ⁿ₂) (1?o(1)). Finally, anti-Pasch hypergraphs avoiding (5, 3) -and (6, 4)-Configurations are considered. © 1993 John Wiley & Sons, Inc.     

Laplacian coefficients of trees with given number of leaves or vertices of degree two

Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix . It is well known that for trees the Laplacian coefficient c_n-2 is equal to the Wiener index of G, while c_n-3 is equal to the modified hyper-Wiener index of graph. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize the trees with k leaves (pendent vertices) which simultaneously minimize all Laplacian coefficients. In particular, this extremal balanced starlike tree S(n,k) minimizes the Wiener index, the modified hyper-Wiener index and recently introduced Laplacian-like energy. We prove that graph S(n,n-1-p) has minimal Laplacian coefficients among n-vertex trees with p vertices of degree two. In conclusion, we illustrate on examples of these spectrum-based invariants that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution, and pose a conjecture on extremal unicyclic graphs with k leaves.     

On Strong Versions of the Central Limit Theorem

Let S_n be the sum of n i.i.d.r.v. and let 1_(-∞,x)(·) be the indicator function of the interval (-∞, x). Then the sequence 1_{(-∞, x)}(S_n/√n) does not converge for any x. Likewise the arithmetic means of this sequence converge only with probability zero. But the logarithmic means converge with probability one to the standard normal distribution Ø(x). Then for any bounded and a.e. continuous function a(y) the logarithmic means of a(S_n/√n) converge a.s. to a = ∫a(y)dØ(y). The arithmetic means of a(S_nk/√n) converge to the same limit a for all subsequences n_k = [c^k], c > 1.     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

Oscillation and Nonoscillation of Second Order Neutral Delay Difference Equations

Some new oscillation and nonoscillation criteria for the second order neutral delay difference equation

The cover time of the giant component of a random graph

We study the cover time of a random walk on the largest component of the random graph G_n,p. We determine its value up to a factor 1 + o(1) whenever np = c > 1, c = O(lnn). In particular, we show that the cover time is not monotone for c = Θ(lnn). We also determine the cover time of the k‐cores, k ≥ 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

How quadratic are the natural numbers?

Abstract. For natural numbers n we inspect all factorizations n = ab of n with a ￡ ba \le b in \Bbb N\Bbb N and denote by n=a_n b_nn=a_n b_n the most quadratic one, i.e. such that b_n - a_nb_n - a_n is minimal. Then the quotient k(n) : = a_n/b_n\kappa (n) := a_n/b_n is a measure for the quadraticity of n. The best general estimate for k(n)\kappa (n) is of course very poor: 1/n ￡ k(n) ￡ 11/n \le \kappa (n)\le 1. But a Theorem of Hall and Tenenbaum [1, p. 29], implies(logn)^-d-e ￡ k(n) ￡ (logn)^-d(\log n)^{-\delta -\varepsilon } \le \kappa (n) \le (\log n)^{-\delta } on average, with d = 1 - (1+log₂  2)/log2=0,08607 ?\delta = 1 - (1+\log _2 \,2)/\log 2=0,08607 \ldots and for every e > 0\varepsilon >0. Hence the natural numbers are fairly quadratic.¶k(n)\kappa (n) characterizes a specific optimal factorization of n. A quadraticity measure, which is more global with respect to the prime factorization of n, is k^*(n): = ?_{1 ￡ a ￡ b, ab=n} a/b\kappa ^*(n):= \textstyle\sum\limits \limits _{1\le a \le b, ab=n} a/b. We show k^*(n) ~ \frac 12\kappa ^*(n) \sim \frac {1}{2} on average, and k^*(n)=W(2^{\frac 12(1-e) log n/log ₂n})\kappa ^*(n)=\Omega (2^{\frac {1}{2}(1-\varepsilon ) {\log}\, n/{\log} _2n})for every e > 0\varepsilon>0.     

On the Location of the Maximum Stirling Number(s) of the Second Kind

Let S(n, k) denote Stirling numbers of the second kind, and K_n be the integer(s) such that S(n, K_n) ? S(n, k) for all k. We determine the value(s) of K_n to within a maximum error of 1.     

Comonotone approximation of twice differentiable periodic functions

In the case where a 2π-periodic function f is twice continuously differentiable on the real axis ℝ and changes its monotonicity at different fixed points y _i ∈ [− π, π), i = 1,…, 2s, s ∈ ℕ (i.e., on ℝ, there exists a set Y := {y _i } _i∈ℤ of points y _i = y _i+2s + 2π such that the function f does not decrease on [y _i , y _i−1] if i is odd and does not increase if i is even), for any natural k and n, n ≥ N(Y, k) = const, we construct a trigonometric polynomial T _n of order ≤n that changes its monotonicity at the same points y _i ∈ Y as f and is such that

Maximum hitting time for random walks on graphs

For x and y vertices of a connected graph G, let T_G(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which T_G(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2_n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time T_G(x, y) to reach y from x in this graph is approximately 4_n³/27.     

On minimum and maximum spanning trees of linearly moving points

In this paper we investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Here, a transition means a change on the combinatorial structure of the spanning trees. Suppose that we are given a set ofn points ind-dimensional space,S={p ₁,p ₂, ...p _n }, and that all points move along different straight lines at different but fixed speeds, i.e., the position ofp _i is a linear function of a real parametert. We investigate the numbers of transitions of MinST and MaxST whent increases from-∞ to +∞. We assume that the dimensiond is a fixed constant. Since there areO(n ²) distances amongn points, there are naivelyO(n ⁴) transitions of MinST and MaxST. We improve these trivial upper bounds forL ₁ andL _∞ distance metrics. Letk _p (n) (resp. ) be the number of maximum possible transitions of MinST (resp. MaxST) inL _p metric forn linearly moving points. We give the following results in this paper: κ₁(n)=O(n ^5/2 α(n)),κ _∞(n)=O(n ^5/2 α(n)), , and where α(n) is the inverse Ackermann's function. We also investigate two restricted cases, i.e., thec-oriented case in which there are onlyc distinct velocity vectors for movingn points, and the case in which onlyk points move.     

Rank‐width of random graphs

Rank‐width of a graph G, denoted by rw (G), is a width parameter of graphs introduced by Oum and Seymour [J Combin Theory Ser B 96 (2006), 514–528]. We investigate the asymptotic behavior of rank‐width of a random graph G(n, p). We show that, asymptotically almost surely, (i) if p∈(0, 1) is a constant, then rw (G(n, p)) = ?n/3??O(1), (ii) if , then rw (G(n, p)) = ?1/3??o(n), (iii) if p = c/n and c>1, then rw (G(n, p))?rn for some r = r(c), and (iv) if p?c/n and c81, then rw (G(n, p))?2. As a corollary, we deduce that the tree‐width of G(n, p) is linear in n whenever p = c/n for each c>1, answering a question of Gao [2006]. © 2011 Wiley Periodicals, Inc. J Graph Theory.     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

Characterization and Transformation of Invariants

We consider difference equations of order k _n+k ≥ 2 of the form: y_n+k = f(yn,…,yn+k-1), n= 0,1,2,… where f: D ^k → D is a continuous function, and D?R. We develop a necessary and sufficient condition for the existence of a symmetric invariant I(x ₁,…,x_k ) ∈C^∞[D^k,D]. This condition will be used to construct invariants for linear and rational difference equations. Also, we investigate the transformation of invariants under invertible maps. We generalize and extend several results that have been obtained recently.     

Some graphs determined by their (signless) Laplacian spectra

Let W _n = K ₁ ? C _n?1 be the wheel graph on n vertices, and let S(n, c, k) be the graph on n vertices obtained by attaching n-2c-2k-1 pendant edges together with k hanging paths of length two at vertex υ ₀, where υ ₀ is the unique common vertex of c triangles. In this paper we show that S(n, c, k) (c ? 1, k ? 1) and W _n are determined by their signless Laplacian spectra, respectively. Moreover, we also prove that S(n, c, k) and its complement graph are determined by their Laplacian spectra, respectively, for c ? 0 and k ? 1.     

On the genus of a random graph

Let p = p(n) be a function of n with 0<p<1. We consider the random graph model ??(n, p); that is, the probability space of simple graphs with vertex-set {1, 2,…, n}, where two distinct vertices are adjacent with probability p. and for distinct pairs these events are mutually independent. Archdeacon and Grable have shown that if p²(1 ? p²) ?? 8(log n)⁴/n. then the (orientable) genus of a random graph in ??(n, p) is (1 + o(1))pn²/12. We prove that for every integer i ? 1, if n^?i/(i + 1) «p «n^{?(i ? 1)/i}. then the genus of a random graph in ??(n, p) is (1 + o(1))i/4(i + 2) pn². If p = cn^?(i?1)/o, where c is a constant, then the genus of a random graph in ??(n, p) is (1 + o(1))g(i, c, n)pn² for some function g(i, c, n) with 1/12 ? g(i, c, n) ? 1. but for i > 1 we were unable to compute this function.