Recurrence relations based on minimization and maximization

Explicit and asymptotic solutions are presented to the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + min_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) for the cases (1) α + β < 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and g(n) = δ_nI. (2) α + β > 1, min(α, β) > 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and (a) g(n) = δ_n1, (b) g(n) = 1. The general form of this recurrence was studied extensively by Fredman and Knuth [J. Math. Anal. Appl.48 (1974), 534–559], who showed, without actually solving the recurrence, that in the above cases $\text{M(n) = Ω(n}{}^{\mathrm{<mtext>1\; +\; </mtext><mtext>1</mtext><mtext>\gamma </mtext>}}\text{)}$, where γ is defined by α^?γ + β^?γ = 1, and that $\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{M(n)}\text{n}{}^{\mathrm{1\; +\; \gamma }}$ does not exist. Using similar techniques, the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + max_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) is also investigated for the special case α = β < 1 and g(n) = 1 if n is odd = 0 if n is even.     

On total matching numbers and total covering numbers of complementary graphs

Best upper and lower bounds, as functions of n, are obtained for the quantities $\text{β}{}_2\text{(G)+β}{}_2\text{(}\text{G}\text{?}\text{)}$ and $\text{α}{}_2\text{(G)+α}{}_2\text{(}\text{G}\text{?}\text{)}$, where β₂(G) denotes the total matching number and α₂(G) the total covering number of any graph G with n vertices and with complementry graph ?.The best upper bound is obtained also for α₂(G)+β₂(G), when G is a connected graph.     

Factorizing the complete graph into factors with large star number

The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that $\text{c}{}_1{}^{\mathrm{n}}\text{k ≤ f(n, k) < c}{}_2{}^{\mathrm{n}}\text{k}$.     

Parallel calculation of a linear mapping on a computer network

We are interested in the parallel computation of a linear mapping of n real variables by a network of computers with restricted means of communication between them and without any common memory. Let $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ denote the algebra of n×n real matrices, and let G be the graph associated with a binary, reflexive and symmetric relation R over {1,2, …,n}. We define

$\text{A}{}_{\mathrm{R}}\text{= {A?M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{):a}{}_{\mathrm{ij}}\text{≠ 0}\text{implies}\text{iRj}}$

A matrix $\text{M∈M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ is said to be realizable on G if it can be expressed as a product of elements of A_R. Therefore, every matrix of $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ is realizable on G if and only if A_R generates $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$. We show that A_R generates $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ if and only if G is connected.     

A theorem on the expected complexity of dijkstra's shortest path algorithm

The expected number of times of updating the values of tentative distances assigned to nodes in Dijkstra's algorithm for the single-source shortest path problem is proved to be at most $\text{n}\text{log}{}_{\mathrm{e}}\text{(}\text{2m}\text{n}\text{)}$, where m and n are the number of edges and nodes respectively of a given graph. The assumption on probability distributions is as general as Spira's for the all-pair shortest path problem. As a corollary of this result, an efficient method for implementing the algorithm by means of a $\text{[}\text{log}{}_{\mathrm{e}}\text{(}\text{2m}\text{n}\text{)-}\text{ary}$ heap is presented, which has the upper bound of $\text{m + 2n}\text{log}{}_2\text{n}\text{log}{}_{\mathrm{e}}\text{(}\text{2m}\text{n}\text{)}\text{log}{}_2\text{log}{}_{\mathrm{e}}\text{(}\text{2m}\text{n}\text{)}$ binary comparisons in average on the decision tree model.     

Some properties of irreducible coverings by cliques of complete multipartite graphs

In this paper some recursion formulas and asymptotic properties are derived for the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite (labeled) graphs K_p,q. The problem of determining numbers N(p, q) has been raised by I. Tomescu (dans “Logique, Automatique, Informatique,” pp. 269–423, Ed. Acad. R.S.R., Bucharest, 1971). A result concerning the asymptotic behavior of the number of irreducible coverings by cliques of q-partite complete graphs is obtained and it is proved that , $\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{log}\text{M(n))}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 3}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$, and $\text{lim}{}_{\mathrm{n\to \infty }}\text{C(n)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{(}\text{n}\text{ln}\text{n)}\text{=}\text{1}\text{e}$, where I(n) and M(n) are the maximal numbers of irreducible coverings, respectively, coverings by cliques of the vertices of an n-vertex graph, and C(n) is the maximal number of minimal colorings of an n-vertex graph. It is also shown that maximal number of irreducible coverings by n ? 2 cliques of the vertices of an n-vertex graph (n ≥ 4) is equal to 2^n?2 ? 2 and this number of coverings is attained only for K_2,n?2 and the value of $\text{lim}{}_{\mathrm{n\to \infty }}\text{I(n, n ? k)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ is obtained, where I(n, n ? k) denotes the maximal number of irreducible coverings of an n-vertex graph by n ? k cliques.     

On the number of groups of a given order

Letting G(n) denote the number of nonisomorphic groups of order n, it is shown that for square-free n, G(n) ≤ ?(n) and G(n) ≤ (log n)^c on a set of positive density. Letting F_k(x) denote the number of n ≤ x for which G(n) = k, it is shown that $\text{F}{}_2\text{(x) =}\text{O(x(}\text{log}{}_4\text{x)}\text{(}\text{log}{}_3\text{x)}{}^2\text{)}$, where log_rx denotes the r-fold iterated logarithm.     

Elementary proof of the transformation formula for Lambert series involving generalized Dedekind sums

An elementary proof is given of the author's transformation formula for the Lambert series $\text{G}{}_{\mathrm{p}}\text{(x) =}\text{Σ}{}_{\mathrm{n?1}}{}^{\mathrm{<mtext>\infty </mtext>}}\text{n}{}^{\mathrm{?p}}\text{x}{}^{\mathrm{n}}\text{(1?x}{}^{\mathrm{n}}\text{)}$ relating G_p(e^2πiτ) to G_p(e^2πiAτ), where p > 1 is an odd integer and $\text{Aτ =}\text{(aτ + b)}\text{(cτ + d)}$ is a general modular substitution. The method extends Sczech's argument for treating Dedekind's function $\text{log}\text{η(τ) =}\text{πiτ}\text{12}\text{? G}{}_1\text{(e}{}^{\mathrm{2\pi i\tau }}\text{)}$, and uses Carlitz's formula expressing generalized Dedekind sums in terms of Eulerian functions.     

Convex polyhedra of doubly stochastic matrices: II. Graph of Ωn

Properties of the graph $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ of the polytope $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices are studied. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is not a k-dimensional rectangular parallelotope for k ≥ 2, then G($\text{F}$) is Hamilton connected. Prime factor decompositions of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ relative to Cartesian product are investigated. In particular, if $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then the number of prime graphs in any prime factor decomposition of G($\text{F}$) equals the number of connected components of the neighborhood of any vertex of G($\text{F}$). Distance properties of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ are obtained. Faces $\text{F}$ of $\text{Ω}{}_{\mathrm{n}}$ for which G($\text{F}$) is a clique of $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ are investigated.     

A note on the functional law of iterated logarithm for maxima of Gaussian sequences

Let {X_n, n ≥ 1} be a real-valued stationary Gaussian sequence with mean zero and variance one. Let M_n = max{X_t, i ≤ n} and H_n(t) = (M_[nt] ? b_n)a_n^?1 be the maximum resp. the properly normalised maximum process, where $\text{c}{}_{\mathrm{n}}\text{= (2}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, $\text{a}{}_{\mathrm{n}}\text{=}\text{(}\text{log log}\text{n)}\text{c}{}_{\mathrm{n}}$ and $\text{b}{}_{\mathrm{n}}\text{= c}{}_{\mathrm{n}}\text{?}\text{1}\text{2}\text{(}\text{log}\text{(4π}\text{log}\text{n))}\text{c}{}_{\mathrm{n}}$. We characterize the almost sure limit functions of (H_n)_n≥3 in the set of non-negative, non-decreasing, right-continuous, real-valued functions on (0, ∞), if r(n) (log n)^3?Δ = O(1) for all Δ > 0 or if r(n) (log n)^2?Δ = O(1) for all Δ > 0 and r(n) convex and fulfills another regularity condition, where r(n) is the correlation function of the Gaussian sequence.     

The toroidal thickness of the symmetric quadripartite graph

The toroidal thickness t₁(G) of a graph G is the minimum value of k for which G is the edge-union of k graphs each embeddable on a torus. It is shown that $\text{t}{}_1\text{(K}{}_{\mathrm{4(n)}}\text{) = [}\text{1}\text{2}\text{(n + 1)]}$.     

Unbounded operators: Perturbations and commutativity problems

Let H be a complex Hilbert space, and let G_i, i = 1, 2, be closed and orthogonal subspaces of the product space H × H. The subspace G = G₁ ⊕ G₂ is called a (graph) perturbation. We give conditions for invariance of regular operators (R.O.) under graph perturbations: When is the perturbation of a R.O. again a R.O.? If N is a Hilbert space we consider R.O. (i.e., densely defined and closed operators T) in H=$\text{L}$(N) such that G(T)=G(S)⊕V$\text{H}$(M, where G denotes the graph, S is a decomposable operator in H, V a decomposable partial isometry such that the initial space of V(t) is equal to M a.e. t, and finally $\text{H}$(M) is the Hardy space of analytic $\text{L}$₂ vector functions with values in M ? N × N. Such operators T commute with the bilateral shift U; but, unless M = 0, T does not commute with $\text{U}{}^1$. Conversely, this is a canonical model for all R.O. with said commutativity properties. Moreover, the model is unique when T is given, and M = G(w) where w is a partial isometry in N. The detailed structure of the model is analyzed in the special case where dim N = dim M = 1. We relate the problem to a condition of Szeg? by showing that T is a $\text{R.O. iff}\text{∝}{}_0{}^{\mathrm{2\pi }}\text{log}\text{¦ V}{}_2\text{(t)¦ dt = ?∞,}\text{where}\text{V = (V}{}_1\text{, V}{}_2\text{)}$ is the partial isometry in the special case of dimension one. Szeg?'s conditions enters in a different way in the analysis of the case M = N × N, as well as in the spectral analysis of T. Our results provide an answer to a commutativity problem posed by Fuglede. If T is an arbitrary densely defined operator, and A?B(H) is normal, we prove two theorems stating conditions for the implication $\text{A}{}_{\mathrm{\cup }}\text{T ? A}{}_{\mathrm{\cup }}{}^1\text{T}$. These conditions cannot generally be relaxed.     

Results on the edge-connectivity of graphs

It is shown that if G is a graph of order p ≥ 2 such that deg u + deg v ≥ p ? 1 for all pairs u, v of nonadjacent vertices, then the edge-connectivity of G equals the minimum degree of G. Furthermore, if deg u + deg v ≥ p for all pairs u, v of nonadjacent vertices, then either p is even and G is isomorphic to $\text{K}{}_{\mathrm{<mtext>p</mtext><mtext>2</mtext>}}\text{× K}{}_2$ or every minimum cutset of edges of G consists of the collection of edges incident with a vertex of least degree.     

Ramsey numbers for all linear forests

An (n, j) linear forest L is the disjoint union of nontrivial paths, such that j of the paths have an odd number of vertices and the union has n vertices. For L, an (n₁.j₁) linear forest and l₂ an (n.j₁) linear forest, we show that

$\text{r(L}{}_1\text{,L}{}_2\text{) = max{n}{}_1\text{·(n}{}_2\text{?j}{}_2\text{)/2 ? 1, n}{}_2\text{+ (n}{}_1\text{? j}{}_1\text{)/2 ? 1}.}$

This answers in the affirmative a conjecture of Burr and Roberts.     

Some Ramsey numbers for directed graphs

Given k directed graphs G₁,…,G_k the Ramsey number R(G₁,…, G_k) is the smallest integer n such that for any partition (U₁,…,U_k) of the arcs of the complete symmetric directed graph K_n, there exists an integer i such that the partial graph generated by U₁ contains G₁ as a subgraph. In the article we give a necessary and sufficient condition for the existence of Ramsey numbers, and, when they exist an upper bound function. We also give exact values for some classes of graphs. Our main result is: $\text{R(}\text{P}{}_{\mathrm{n}}\text{,….}\text{P}{}_{\mathrm{nk-1}}\text{, G) = n}{}_1\text{…n}{}_{\mathrm{k-1}}\text{(p-1) + 1}$, where G is a hamltonian directed graph with p vertices and $\text{P}{}_{\mathrm{n}}{}_{\mathrm{i}}$ denotes the directed path of length n_t     

A divided difference inequality for n-convex functions

For a₍₁₎ ? a₍₂₎ ? ··· ? a_(n) ? 0, b₍₁₎ ? b₍₂₎ ? ··· ? b_(n) ? 0, the ordered values of a_i, b_i, i = 1, 2,…, n, m fixed, m ? n, and p ? 1 it is shown that

$\text{∑}\text{1}\text{n}\text{a}{}_{\mathrm{i}}\text{b}{}_{\mathrm{i}}\text{?}\text{∑}\text{1}\text{m}\text{a}{}^{\mathrm{p}}{}_{\mathrm{(i)}}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}\text{∑}\text{1}\text{m?k?1}\text{b}{}^{\mathrm{q}}{}_{\mathrm{(i)}}\text{+}\text{b}{}^{\mathrm{q}}{}_{\mathrm{[m?k]}}\text{(k+1)}{}^{\mathrm{<mtext>q</mtext><mtext>p</mtext>}}{}^{\mathrm{<mtext>1</mtext><mtext>q</mtext>}}$

where $\text{1}\text{p}\text{+}\text{1}\text{q}\text{= 1, b}{}_{\mathrm{[j]}}\text{= b}{}_{\mathrm{(j)}}\text{+ b}{}_{\mathrm{(j\; +\; 1)}}\text{+ ··· + b}{}_{\mathrm{(n)}}\text{,}\text{and}\text{k}$ is the integer such that $\text{b}{}_{\mathrm{(m\; ?\; k\; ?\; 1)}}\text{?}\text{b[m ? k]}\text{(k + 1)}$ and $\text{b}{}_{\mathrm{(m\; ?\; k)}}\text{<}\text{b}{}_{\mathrm{[m\; ?\; k\; +\; 1]}}\text{k}$. The inequality is shown to be sharp. When p < 1 and a_(i)'s are in increasing order then the inequality is reversed.     

On the maximum cardinality of a consistent set of arcs in a random tournament

For any tournament T on n vertices, let h(T) denote the maximum number of edges in the intersection of T with a transitive tournament on the same vertex set. Sharpening a previous result of Spencer, it is proved that, if T_n denotes the random tournament on n vertices, then, $\text{P}$$\text{(h(T}{}_{\mathrm{n}}\text{) ≤}\text{1}\text{2}\text{(}{}_2{}^{\mathrm{n}}\text{) + 1.73n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{) → 1}$ as n → ∞.     

Cogrowth and amenability of discrete groups

Let G be a group and g₁,…, g_t a set of generators. There are approximately (2t ? 1)ⁿ reduced words in g₁,…, g_t, of length ?n. Let $\text{}\text{?}\text{gg}{}_{\mathrm{n}}$ be the number of those which represent 1_G. We show that $\text{γ =}\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{(}\text{}\text{?}\text{gg}{}_{\mathrm{n}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ exists. Clearly 1 ? γ ? 2t ? 1. $\text{η =}\text{(}\text{log}\text{γ)}\text{(}\text{log}\text{(2t ? 1))}$ is the cogrowth. 0 ? η ? 1. In fact $\text{η ∈ {0} ∪ (}\text{1}\text{2}\text{, 1¦}$. The entropic dimension of G is shown to be 1 ? η. It is then proved that d(G) = 1 if and only if G is free on g₁,…, g_t and d(G) = 0 if and only if G is amenable.