Linear arboricity for graphs with multiple edges

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ(G), the linear arboricity la(G) satisfies ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + 1)/2?. Here it is proved that if G is a loopless graph with maximum degree Δ(G) ≦ k and maximum edge multiplicity μ(G) ≦ k ? 2ⁿ⁺¹ + 1, where k ≧ 2^n?2, then la(G) ≦ k ? 2ⁿ. It is also conjectured that for any loopless graph G, ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + μ(G))/2?.     

On p-intersection representations

For a graph G = (V,E) and integer p, a p-intersection representation is a family F = {S_x: × E V} of subsets of a set S with the property that |S_u ∩ S_ν| ≥ p ∩ {u, ν} E E. It is conjectured in [1] that θ_p(G) ≤ θ (K_n/2,n/2) (1 + o(1)) holds for any graph with n vertices. This is known to be true for p = 1 by [4]. In [1], θ (K_n/2,n/2) ≥ (n² + (2p− 1n)n)/4p is proved for any n and p. Here, we show that this is asymptotically best possible. Further, we provide a bound on θp(G) for all graphs with bounded degree. In particular, we prove θp(G) ≤ O(n^1/p) for any graph Gwith the maximum degree bounded by a constant. Finally, we also investigate the value of θ_p for trees. Improving on an earlier result of M. Jacobson, A. Kézdy, and D. West, (The 2-intersection number of paths and bounded-degree trees, preprint), we show that θ₂(T) ≤ O(d√n) for any tree T with maximum-degree d and θ₂(T) ≤ O(n^3/4) for any tree on n vertices. We conjecture that our results can be further improved and that θ₂(T) ≤ O(d√n) as long as Δ(T) ≤ √n. If this conjecture is true, our method gives θ₂(T) ≤ O(n^3/4) for any tree T which would be the best possible. © 1996 John Wiley & Sons, Inc.     

Minimal rates of entropy convergence for completely ergodic systems

If (X,T) is a completely ergodic system, then there exists a positive monotone increasing sequence {a _n } _n ^1/∞ with lim _n →∞a _n =∞ and a positive concave functiong defined on [1, ∞) for whichg(x)/x ² isnot integrable such that for all nontrivial partitions α ofX into two sets.     

Local connectivity of a random graph

A graph is locally connected if for each vertex ν of degree ≧2, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order n is p = ((3/2 +?_n) log n/n)^1/2 where ?_n = (log log n + log(3/8) + 2x)/(2 log n), then the limiting probability that a random graph is locally connected is exp(-exp(-x)).     

Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method

Let G(n,c/n) and G_r(n) be an n‐node sparse random graph and a sparse random r‐regular graph, respectively, and let I(n,r) and I(n,c) be the sizes of the largest independent set in G(n,c/n) and G_r(n). The asymptotic value of I(n,c)/n as n → ∞, can be computed using the Karp‐Sipser algorithm when c ≤ e. For random cubic graphs, r = 3, it is only known that .432 ≤ lim inf_n I(n,3)/n ≤ lim sup_n I(n,3)/n ≤ .4591 with high probability (w.h.p.) as n → ∞, as shown in Frieze and Suen [Random Structures Algorithms 5 (1994), 649–664] and Bollabas [European J Combin 1 (1980), 311–316], respectively. In this paper we assume in addition that the nodes of the graph are equipped with nonnegative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit lim_n I(n,c)/n can be computed exactly even when c > e, and lim_n I(n,r)/n can be computed exactly for some r ≥ 1. For example, when the weights are exponentially distributed with parameter 1, lim_n I(n,2e)/n ≈ .5517, and lim_n I(n,3)/n ≈ .6077. Our results are established using the recently developed local weak convergence method further reduced to a certain local optimality property exhibited by the models we consider. We extend our results to maximum weight matchings in G(n,c/n) and G_r(n). For the case of exponential distributions, we compute the corresponding limits for every c > 0 and every r ≥ 2. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The type problem for random walks on trees

We consider the question of whether the simple random walk (SRW) on an infinite tree is transient or recurrent. For random-trees (all vertices of distancen from the root of the tree have degreed _n , where {d _n } are independent random variables), we prove that the SRW is a.s. transient if lim inf _n n E(log(d _n-1))>1 and a.s. recurrent if lim sup _n n E(log(d _n-1))<1. For random trees in which the degrees of the vertices are independently 2 or 3, with distribution depending on the distance from the root, a partial classification of type is obtained.Research supported in part by NSF DMS 8710027.     

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.)     

Decreasing the diameter of bounded degree graphs

Let f_d (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n₀ (D) vertices, f₂(G) = n − D − 1 and f₃(G) ≥ n − O(D³). For d ≥ 4, f_d (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of f_d (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle C_n, f_d (C_n) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000     

Zero-sum delta-systems and multiple copies of graphs

A main result proved in this paper is the following. Theorem. Let G be a noncomplete graph on n vertices with degree sequence d₁ ≥ d₂ ≥ · · · ≥ d_n and t ≥ 2 be a prime. Let m = gcd{t, d_i − d_j: 1 ≤ i < j ≤ n} and set Then R(tG, ℤ_t) = t(n + d) − d, where R is the zero-sum Ramsey number. This settles, almost completely, problems raised in [Bialostocki & Dierker, J Graph Theory, 1994; Y. Caro, J Graph Theory, 1991]. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 207–216, 1999     

Valleys and the Maximum Local Time for Random Walk in Random Environment

Let ξ (n, x) be the local time at x for a recurrent one-dimensional random walk in random environment after n steps, and consider the maximum ξ^*(n) = max _x ξ(n, x). It is known that lim sup is a positive constant a.s. We prove that lim inf is a positive constant a.s. this answers a question of P. Révész [5]. The proof is based on an analysis of the valleys in the environment, defined as the potential wells of record depth. In particular, we show that almost surely, at any time n large enough, the random walker has spent almost all of its lifetime in the two deepest valleys of the environment it has encountered. We also prove a uniform exponential tail bound for the ratio of the expected total occupation time of a valley and the expected local time at its bottom.     

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k

Let G_n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A_k, if G contains ⌊(k − 1)/2⌋ edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size ⌊n/2⌋. We prove that, for k ≥ 3, there is a constant C_k such that if 2m ≥ C_kn then A_k occurs in G_n,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000     

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s‐Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 ‐ o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n^{1+Ω(1/log log n)}. Recall that the Ising model with inverse temperature β defined on a graph G = (V,E) is the distribution over {±}^Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of β or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < ∞ and the Ising model defined on G (n, d/n), there exists a β_d > 0, such that for all β < β_d with probability going to 1 as n →∞, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd?s‐Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub‐graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and β < β_d, where d tanh(β_d) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

The 2-intersection number of paths and bounded-degree trees

We represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The 2-intersection number θ₂(G) of a graph G is the minimum size of the union of sets in such a representation. We prove that the maximum order of a path that can be represented in this way using t elements is between (t² - 19t + 4)/4 and (t² - t + 6)/4, making θ₂(P_n) asymptotic to 2√n. We also show the existence of a constant c depending on ? such that, for any tree T with maximum degree at most d, θ₂(T) ≤ c(√n)^1+?. When the maximum degree is not bounded, there is an n-vertex tree T with θ₂(T) > .945n^2/3. © 1995 John Wiley & Sons, Inc.     

Mean-Field Conditions for Percolation on Finite Graphs

Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if

lim sup  n n1/3 ?t = 1n1/3 tpt(v,v) < ￥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}      15. Moments of graphs in monotone families      Zoltn Füredi  Andr Kündgen 《Journal of Graph Theory》2006,51(1):37-48 The kth moment of the degree sequence d1 ≥ d2 ≥ …dn of a graph G is . We give asymptotically sharp bounds for μk(G) when G is in a monotone family. We use these results for the case k = 2 to improve a result of Pach, Spencer, and Tóth [15]. We answer a question of Erd?s [9] by determining the maximum variance of the degree sequence when G is a triangle‐free n‐vertex graph. © 2005 Wiley Periodicals, Inc.      16. Extremal graphs of diameter two and given maximum degree,embeddable in a fixed surface      Martin Knor  Jozef &#x;ir&#x; 《Journal of Graph Theory》1997,24(1):1-8 It is known that for each d there exists a graph of diameter two and maximum degree d which has at least ⌈(d/2)⌉ ⌈(d + 2)/2⌉ vertices. In contrast with this, we prove that for every surface S there is a constant ds such that each graph of diameter two and maximum degree d ≥ ds, which is embeddable in S, has at most ⌊(3/2)d⌋ + 1 vertices. Moreover, this upper bound is best possible, and we show that extremal graphs can be found among surface triangulations. © 1997 John Wiley & Sons, Inc.      17. How quadratic are the natural numbers?      Friedrich Roesler 《Archiv der Mathematik》1999,73(3):193-198 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=an bnn=a_n b_n the most quadratic one, i.e. such that bn - anb_n - a_n is minimal. Then the quotient k(n) : = an/bn\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+log2  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 2n)\kappa ^*(n)=\Omega (2^{\frac {1}{2}(1-\varepsilon ) {\log}\, n/{\log} _2n})for every e > 0\varepsilon>0.      18. A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>      Camino Balbuena  Alberto Márquez  José Ramón Portillo 《数学学报(英文版)》2011,27(1):135-140 The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d G (x) + d G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d G (u) ≥ k.      19. An iterated logarithm law related to decimal and continued fraction expansions      Jun Wu 《Monatshefte für Mathematik》2008,19(1):83-87 For an irrational number x and n ≥ 1, we denote by k n (x) the exact number of partial quotients in the continued fraction expansion of x given by the first n decimals of x. G. Lochs proved that for almost all x, with respect to the Lebesgue measure In this paper, we prove that an iterated logarithm law for {k n (x): n ≥ 1}, more precisely, for almost all x, for some constant σ > 0. Author’s address: Department of Mathematics, Huazhong University of Science and Technology, Wuhan, Hubei 430074, P.R. China      20. Randomly coloring sparse random graphs with fewer colors than the maximum degree      Martin Dyer  Abraham D. Flaxman  Alan M. Frieze  Eric Vigoda 《Random Structures and Algorithms》2006,29(4):450-465 We analyze Markov chains for generating a random k‐coloring of a random graph Gn,d/n. When the average degree d is constant, a random graph has maximum degree Θ(log n/log log n), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly random k‐coloring when k = Θ(log log n/log log log n), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006

Moments of graphs in monotone families

The kth moment of the degree sequence d₁ ≥ d₂ ≥ …d_n of a graph G is . We give asymptotically sharp bounds for μ_k(G) when G is in a monotone family. We use these results for the case k = 2 to improve a result of Pach, Spencer, and Tóth [15]. We answer a question of Erd?s [9] by determining the maximum variance of the degree sequence when G is a triangle‐free n‐vertex graph. © 2005 Wiley Periodicals, Inc.     

Extremal graphs of diameter two and given maximum degree,embeddable in a fixed surface

It is known that for each d there exists a graph of diameter two and maximum degree d which has at least ⌈(d/2)⌉ ⌈(d + 2)/2⌉ vertices. In contrast with this, we prove that for every surface S there is a constant d_s such that each graph of diameter two and maximum degree d ≥ d_s, which is embeddable in S, has at most ⌊(3/2)d⌋ + 1 vertices. Moreover, this upper bound is best possible, and we show that extremal graphs can be found among surface triangulations. © 1997 John Wiley & Sons, Inc.     

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.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

An iterated logarithm law related to decimal and continued fraction expansions

For an irrational number x and n ≥ 1, we denote by k _n (x) the exact number of partial quotients in the continued fraction expansion of x given by the first n decimals of x. G. Lochs proved that for almost all x, with respect to the Lebesgue measure In this paper, we prove that an iterated logarithm law for {k _n (x): n ≥ 1}, more precisely, for almost all x, for some constant σ > 0. Author’s address: Department of Mathematics, Huazhong University of Science and Technology, Wuhan, Hubei 430074, P.R. China     

Randomly coloring sparse random graphs with fewer colors than the maximum degree

We analyze Markov chains for generating a random k‐coloring of a random graph G_n,d/n. When the average degree d is constant, a random graph has maximum degree Θ(log n/log log n), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly random k‐coloring when k = Θ(log log n/log log log n), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006