Cycle-saturated graphs of minimum size

A graph G is called C_k-saturated if G contains no cycles of length k but does contain such a cycle after the addition of any new edge. Bounds are obtained for the minimum number of edges in C_k-saturated graphs for all k ≠ 8 or 10 and n sufficiently large. In general, it is shown that the minimum is between n + c₁n/k and n + c₂n/k for some positive constants c₁ and C₂. Our results provide an asymptotic solution to a 15-year-old problem of Bollobás.     

Measurements of edge-uncolorability

Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let c_k be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r₃=|E|−c₃ and . We show that on one side r₃ and r₂ bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r₃ and ω are arbitrarily far apart, and show that for each 1c<2 there is a cubic graph such that ωcr₃. For k=2,3, let ζ_k denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other.     

Convex 4-valent polytopes

Let {p_k}_k≥3 be a sequence of nonnegative integers which satisfies 8 + Σ_k≥3 (k-4) p_k = 0 and p₄ ≥ p₃. Then there is a convex 4-valent polytope P in E³ such that P has exactly p_k k-gons as faces. The inequality p₄ ≥ p₃ is the best possible in the sense that for c < 1 there exist sequences that are not 4-realizable that satisfy both 8 + Σ_{k ≥3} (k - 4) p_k = 0 and p₄ > cp₃. When Σ_{k ≥ 5} p_k ≠ 1, one can make the stronger statement that the sequence {p_k} is 4-reliazable if it satisfies 8 + Σ_{k ≥ 3} (k - 4) p_k = 0 and p₄ ≥ 2Σ_{k ≥ 5} p_k + max{k ¦ p_k ≠ 0}.     

An infinite family of cubic edge- but not vertex-transitive graphs

An infinite family of cubic edge- but not vertex-transitive graphs is constructed. The graphs are obtained as regular -covers of K_3,3 where n=p₁^e₁p₂^e₂p_k^e_k where p_i are distinct primes congruent to 1 modulo 3, and e_i1. Moreover, it is proved that the Gray graph (of order 54) is the smallest cubic edge- but not vertex-transitive graph.     

Length-bounded disjoint paths in planar graphs

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r₁,s₁},…,{r_k,s_k} of G adjacent to the unbounded face, positive integers b₁,…,b_k and a function ; find: pairwise vertex-disjoint paths P₁,…,P_k such that for each i=1,…,k, P_i is a r_i−s_i-path and the sum of the l-length of all edges in P_i is at most b_i. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.     

First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.     

The existence of Schröder designs with equal-sized holes

A holey Schröder design of type h₁^n₁h₂^n₂ … h_k^n_k (HSD(h₁^n₁h₂^n₂ … h_k^n_k)) is equivalent to a frame idempotent Schröder quasigroup (FISQ(h₁^n₁h₂^n₂ … h_k^n_k)) of order n with n_i missing subquasigroups (holes) of order h_i, (1 i k), which are disjoint and spanning, that is, Σ_{1 i k} n_ih_i = n. In this paper, it is shown that an HSD(hⁿ) exists if and only if h²n(n − 1) 0 (mod 4) with expceptions (h, n) ε {{(1,5),(1,9),(2,4)}} and the possible exception of (h, n) = (6,4).     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

Upper bounds for Ramsey numbers

The Ramsey number R(G₁,G₂,…,G_k) is the least integer p so that for any k-edge coloring of the complete graph K_p, there is a monochromatic copy of G_i of color i. In this paper, we derive upper bounds of R(G₁,G₂,…,G_k) for certain graphs G_i. In particular, these bounds show that R(9,9)6588 and R(10,10)23556 improving the previous best bounds of 6625 and 23854.     

On the planarity of jump graphs

For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph J_k(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of J_k(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J₂(G) is planar are determined.     

Closed 2-cell embeddings of graphs with no V8-minors

A closed 2-cell embedding of a graph embedded in some surface is an embedding such that each face is bounded by a cycle in the graph. The strong embedding conjecture says that every 2-connected graph has a closed 2-cell embedding in some surface. In this paper, we prove that any 2-connected graph without V₈ (the Möbius 4-ladder) as a minor has a closed 2-cell embedding in some surface. As a corollary, such a graph has a cycle double cover. The proof uses a classification of internally-4-connected graphs with no V₈-minor (due to Kelmans and independently Robertson), and the proof depends heavily on such a characterization.     

Error bounds on the power method for determining the largest eigenvalue of a symmetric, positive definite matrix

Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ₁. We consider the power method, i.e. that of choosing a vector v₀ and setting v_k = A^kv₀; then the Rayleigh quotients R_k = (Av_k, v_k)/(v_k, v_k) usually converge to λ₁ as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close R_k is to λ₁. They are both based on a bound on λ₁ − R_k involving the difference of two consecutive Rayleigh quotients and a quantity ω_k. While we do not know how to directly calculate ω_k, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ₁ − R_k which is proportional to (λ₂/λ₁)^2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ).     

Gowers norms and pseudorandom measures of subsets

Let $A \subset {{\Bbb Z}_N}$, and ${f_A}(s) = \left\{ {\begin{array}{*{20}{l}}{1 - \frac{{|A|}}{N},}&{{\rm{for}}\;s \in A,}\\{ - \frac{{|A|}}{N},}&{{\rm{for}}\;s \notin A.}\end{array}} \right.$ We define the pseudorandom measure of order k of the subset A as follows, P_k(A, N) = $\begin{array}{*{20}{c}}{\max }\\D\end{array}$|$\mathop \Sigma \limits_{n \in {\mathbb{Z}_N}}$f_A(n + c₁)f_A(n + c₂) … f_A(n + c_k)|, where the maximum is taken over all D = (c₁, c₂, . . . , c_k) ∈ ${\mathbb{Z}^k}$ with 0 ≤ c₁ < c₂ < … < c_k ≤ N - 1. The subset A ⊂ ${{\mathbb{Z}_N}}$ is considered as a pseudorandom subset of degree k if P_k(A, N) is “small” in terms of N. We establish a link between the Gowers norm and our pseudorandom measure, and show that “good” pseudorandom subsets must have “small” Gowers norm. We give an example to suggest that subsets with “small” Gowers norm may have large pseudorandom measure. Finally, we prove that the pseudorandom subset of degree L(k) contains an arithmetic progression of length k, where L(k) = 2·lcm(2, 4, . . . , 2|$\frac{k}{2}$|), for k ≥ 4, and lcm(a₁, a₂, . . . , a_l) denotes the least common multiple of a₁, a₂, . . . , a_l.     

The game of n-times nim

The following game is considered. The first player can take any number of stones, but not all the stones, from a single pile of stones. After that, each player can take at most n-times as many as the previous one. The player first unable to move loses and his opponent wins. Let f₁,f₂,… be an initial sequence of stones in increasing order, such that the second player has a winning strategy when play begins from a pile of size f_i. It is proved that there exist constants c=c(n) and k₀=k₀(n) such that f_k+1=f_k+f_k−c for all k>k₀, and lim_n→∞ c(n)/(nlogn)=1.     

Multicolored forests in complete bipartite graphs

If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a=(a₁,a₂,…,a_k), in which a_i denotes the number of edges of color i for i=1,2,…,k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph K_n,n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of K_n,n into multicolored trees.     

On the Equation n_1n_2= n_3n_4 Restricted to Factor Closed Sets

We study the number of solutions N(B,F) of the diophantine equation n_1n_2 = n_3 n_4,where 1 ≤ n_1 ≤ B,1 ≤ n_3 ≤ B,n_2,n_4 ∈ F and F[1,B] is a factor closed set.We study more particularly the case when F={m = p_1~(ε1)···p_k~(εk),ε_j∈{0,1},1 ≤ j ≤ k},p_1,...,p_k being distinct prime numbers.     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).     

Ramsey linear families and generalized subdivided graphs

The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V₁, V₂,…, V_a such that for each i at most d vertices in V₁ … V_i have neighbors in V_i+1 and r(K_k, V_i) p | V(G) |, where V_i denotes the subgraph of G induced by V_i. Then there exists a number c depending only on p, d, and k such that r(K_k, G)c | V(G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V(G) such that each component of G−I has at most d vertices and at most two neighbors in I. Then r(G,G)c | V(G) |, where c is a number depending only on d. As a special case, r(G, G) 6 | V(G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4.     

Invariant record processes and applications to best choice modelling

Let X₁, X₂,…be identically distributed random variables from an unknown continuous distribution. Further let I_r(1), I_r(2),…be a sequence of indicator functions defined on X₁, X₂,…by I_r(k) = 0 if k < r, I_r(k) = 1 if X_k is a r-record AND = 0 otherwise. Suppose that we observe X₁, X₂,… at times T₁ < T₂ <… where the T_k's are realisations of some regular counting process (N(τ)) defined on the positive half-line. Having observed [0, τ], say, the problem is to predict the future behaviour of the counting processes (R_r(τ, s))_sτ = # r-records in [τ, s]. More specifically the objective of this paper is to show that these processes can be (inhomogeneous) Poisson processes even if (N(τ))_τ0 has dependent increments.

The strong link between optimal selection and optimal stopping of record sequences or record processes, perhaps not fully recognized so far, is pointed out in this paper. It is shown to lead to a unification of the treatment of problems which, at first sight, are rather different. Moreover the stopping of record processes in continuous time can lead to rigorous and elegant solutions in cases where dynamic programming is bound to fail. Several examples will be given to facilitate a comparison with other methods.     

Graph spectra

The k-spectrum s_k(G) of a graph G is the set of all positive integers that occur as the size of an induced k-vertex subgraph of G. In this paper we determine the minimum order and size of a graph G with s_k (G) = {0, 1, …,(₂^k)} and consider the more general question of describing those sets S {0,1, … ,(₂^k)} such that S = s_k(G) for some graph G.