Decomposition of the completer-graph into completer-partiter-graphs

Forn ≥ r ≥ 1, letf _r (n) denote the minimum numberq, such that it is possible to partition all edges of the completer-graph onn vertices intoq completer-partiter-graphs. Graham and Pollak showed thatf ₂(n) =n ? 1. Here we observe thatf ₃(n) =n ? 2 and show that for every fixedr ≥ 2, there are positive constantsc ₁(r) andc ₂(r) such thatc ₁(r) ≤f _r (n)?n ^?[r/2] ≤n ₂(r) for alln ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

Extremal graphs without a semi‐topological wheel

For 2≤r∈?, let S_r denote the class of graphs consisting of subdivisions of the wheel graph with r spokes in which the spoke edges are left undivided. Let ex(n, S_r) denote the maximum number of edges of a graph containing no S_r‐subgraph, and let Ex(n, S_r) denote the set of all n‐vertex graphs containing no S_r‐subgraph that are of size ex(n, S_r). In this paper, a conjecture is put forth stating that for r≥3 and n≥2r + 1, ex(n, S_r) = (r ? 1)n ? ?(r ? 1)(r ? 3/2)? and for r≥4, Ex(n, S_r) consists of a single graph which is the graph obtained from K_{r ? 1, n ? r + 1} by adding a maximum matching to the color class of cardinality r ? 1. A previous result of C. Thomassen [A minimal condition implying a special K₄‐subdivision, Archiv Math 25 (1974), 210–215] implies that this conjecture is true for r = 3. In this paper it is shown to hold for r = 4. © 2011 Wiley Periodicals, Inc. J Graph Theory 68:326‐339, 2011     

A bound for the number of tournaments with specified scores

Let $\text{T}$(R) denote the set of all tournaments with score vector R = (r₁, r₂,…, r_n). R. A. Brualdi and Li Qiao (“Proceedings of the Silver Jubilee Conference in Combinatorics at Waterloo,” in press) conjectured that if R is strong with r₁ ≤ r₂ ≤ … ≤ r_n, then |$\text{T}$(R)| ≥ 2^n?2 with equality if and only if R = (1, 1, 2,…, n ? 3, n ? 2, n ? 2). In this paper their conjecture is proved, and this result is used to establish a lower bound on the cardinality of $\text{T}$(R) for every R.     

On special values of certain Dirichlet L-functions

Let r _k (n) denote the number of ways n can be expressed as a sum of k squares. Recently, S. Cooper (Ramanujan J. 6:469–490, [2002]), conjectured a formula for r ₉(t), t≡5 (mod 8), r ₁₁(t), t≡7 (mod 8), where t is a square-free positive integer. In this note we observe that these conjectures follow from the works of Lomadze (Akad. Nauk Gruz. Tr. Tbil. Mat. Inst. Razmadze 17:281–314, [1949]; Acta Arith. 68(3):245–253, [1994]). Further we express r ₉(t), r ₁₁(t) in terms of certain special values of Dirichlet L-functions. Combining these two results we get expressions for these special values of Dirichlet L-functions involving Jacobi symbols.      

Loi fonctionnelle du logarithme itéré pour les incréments du processus des espacements

Let a_n(l): 0 ≤ /denote the reseated empirical process based upon uniform spacings. Let {h_n, n ≥ 1 } be a sequence decreasing to 0. Under appropriate conditions on h_n. We give a functional lnw of the iterated logarithm for the set of increment functions {a_n (l + h_n.) — a_n(l): 0 ≤ / ≤ 1 -h_n}.     

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     

Double cycle covers and the petersen graph

Let O(G) denote the set of odd-degree vertices of a graph G. Let t ? N and let ??_t denote the family of graphs G whose edge set has a partition. E(g) = E₁ U E₂ U … U E_tsuch that O(G) = O(G[E_i]) (1 ? i ? t). This partition is associated with a double cycle cover of G. We show that if a graph G is at most 5 edges short of being 4-edge-connected, then exactly one of these holds: G ? ??₃, G has at least one cut-edge, or G is contractible to the Petersen graph. We also improve a sufficient condition of Jaeger for G ? ??_2p+1(p ? N).     

On Some Optimal Constructions of Chess Tournament Combinations

An optimal solution for the following “chess tournament” problem is given. Let n, r be positive integers such that r<n. Put N=2n, R=2r+1. Let X_N,R be the set of all ordered pairs (T, A) of matrices of degree N such that T=(t_ij) is symmetric, A=(a_ij) is skew-symmetric, t_ij ∈,{0, 1, 2,…, R), a_ij ∈{0,1,–1}. Moreover, suppose t_ii=a_ii=0 (1?i?N). t_ij = t_ik>0 implies j=k, t_ij=0 is equivalent to a_ij=0, and |a_i1|+|a_i2|+…+|a_iN|=R (1?i?N). Let p(T, A) be the number of i such that 1?i?N and a_i1 + a_i2 + … + a_iN >0. The main result of this note is to show that max p(T, A) for (T, A)∈X_{N, R} is equal to [n(2r+1)/(r+1)], and a pair (T₀, A₀) satisfying p(T₀, A₀)=[n(2r+1)/(r+1)] is also given.     

Approximation of curves by polygons

Let A be a smooth curve in a Euclidean space E given by an arc length parametrization f: [0, 1] → E. Let π_n = {0 = t₀ ≤ t₁ ≤ … ≤ t_n = 1} be a partition of [0, 1] and let P_n be the polygon with vertices f(t₀), f(t₁),…, f(t_n). Let L(A) and L(P_n) denote the lengths of A and P_n, respectively. The paper investigates the behavior of n² |L(A) ? L(P_n)| when the partition π_n is induced by the sequence nθ(mod 1) for some irrational number θ. It turns out that this behavior depends on the partial quotients of the continued fraction expansion of θ.     

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     

Large induced forests in sparse graphs

For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K₄, then a(G) ≥ n ? e/4 ? 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n ? α(G))/(Δ ? 1)². Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

The singular values of the hadamard product of a positive semidefinite and a skew-symmetric matrix

Let σ₁(X)≤ · ≤ σ_N(X)≤0 denote the ordered singular values ofan n × n matrix X and let α₁ (X) ≤ α₂(X)≤ · ≤ α_n(X) denote its ordered main diagonal entries (assuming that they are real). Let B be any complex n × n skew-symmetric matrix and ||.|| any unitarily invariant norm. It is shown that for any rea positive semidefinite n × n matrix A.     

Asymptotic behavior of random heaps

We consider a random walk W_n on the locally free group (or equivalently a signed random heap) with m generators subject to periodic boundary conditions. Let #T(W_n) denote the number of removable elements, which determines the heap's growth rate. We prove that lim_n→∞??(#T(W_n))/m ≤ 0.32893 for m ≥ 4. This result disproves a conjecture (due to Vershik, Nechaev and Bikbov [Comm Math Phys 212 (2000), 469–501]) that the limit tends to 1/3 as m → ∞. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

A note on a conjecture about cycles with many incident chords

Given positive integers n and k, let g_k(n) denote the maximum number of edges of a graph on n vertices that does not contain a cycle with k chords incident to a vertex on the cycle. Bollobás conjectured as an exercise in [2, p. 398, Problem 13] that there exists a function n(k) such that g_k(n) = (k + 1)n ? (k + 1)² for all n ≥ n(k). Using an old result of Bondy [ 3 ], we prove the conjecture, showing that n(k) ≤ 3 k + 3. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 180–182, 2004     

Analytic Extension of Non Quasi - Analytic Whitney Jets of Beurling Type

Let (M_r)_r∈_?0 be a logarithmically convex sequence of positive numbers which verifies M₀ = 1 as well as M_r ≥ 1 for every r ∈ ? and defines a non quasi - analytic class. Let moreover F be a closed proper subset of ?ⁿ. Then for every function f on ?ⁿ belonging to the non quasi - analytic (M_r)-class of Beurling type, there is an element g of the same class which is analytic on ?,ⁿ F and such that D^αf(x) = D^αg(x) for every α ∈ ?ⁿ₀ and x ∈ F.     

Constructing Maximal Commutative Subalgebras of Matrix Rings in Small Dimensions

Let k denote an algebraically closed field of arbitrary characteristic. Let C denote the set of all commutative, finite dimensional, local k-algebras of the form (B, m, k) with i(m) ?2. Here i(m) denotes the index of nilpotency of the maximal ideal m. A Akalgebra (R, J,k)∈L is called a (c₁-construction if there exists (B, m, k)∈ £ ? {(k, (0), k)} and a finitely generated, faithful B-module N such that R,?B?(the idealization of N). (R.J.k) is called a (c_2::-construction if there exist a (B,m k)∈ L, a positive integer p $ge;2 and a nonzero z £ S_B(the socle of B) such that R?B[x]/(mX, X^p- z). Let M_n×n(K) denote the set of all n x n matrices, over k with n≥2. Let .M_n(k) denote the set of all maximal, commutative A;-subalgebras of M_n×n(k). In this paper, we show any (R J, k) ∈£?M_n;(k) with n>5 is a C₁ or C₂ -construction except for one isomorphism class. The one exception occurs when n = 5.