The characterization of sort sequences

A sort sequenceS _n is a sequence of all unordered pairs of indices inI _n = 1, 2, ...,n. With a sort sequenceS _n, we associate a sorting algorithmA(S _n) to sort input setX = x ₁, x₂, ..., x_n as follows. An execution of the algorithm performs pairwise comparisons of elements in the input setX as defined by the sort sequenceS _n, except that the comparisons whose outcomes can be inferred from the outcomes of the previous comparisons are not performed. Let χ(S _n) denote the average number of comparisons required by the algorithmA(S _n assuming all input orderings are equally likely. Let χ*(n) and χ°(n) denote the minimum and maximum values, respectively, of χ(S _n) over all sort sequencesS _n. Exact determination of χ*(n), χO(n) and associated extremal sort sequences seems difficult. Here, we obtain bounds on χ*(n) and χO(n).     

An extremal result for sum-free sequences

Let a₁ < a₂ < … be a sequence of positive integers such that no a_k is a sum of distinct other terms. Erdös conjectured that if a₁ ≥ n, then $\text{Σ1}\text{a}{}_{\mathrm{k}}\text{<}\text{log}\text{2 + ?}{}_{\mathrm{n}}$, where, ?_n → 0 as n → ∞. This result, which is the best possible, is established in this paper.     

On the Davenport constant and on the structure of extremal zero-sum free sequences

Let $G = C_{n_1 } \oplus \cdots \oplus C_{n_r }$ with 1 < n ₁ | ?? | n _r be a finite abelian group, d*(G) = n ₁ +??+n _r ?r, and let d(G) denote the maximal length of a zerosum free sequence over G. Then d(G) ?? d*(G), and the standing conjecture is that equality holds for G = C _n ^r . We show that equality does not hold for C ₂ ?? C _2n ^r , where n ?? 3 is odd and r ?? 4. This gives new information on the structure of extremal zero-sum free sequences over C _2n ^r .     

On the extremal sets of extremal quasiconformal mappings

The properties of the extremal sets of extremal quasiconformal mappings are discussed. It is proved that if an extremal Beltrami coefficient μ(z) is not uniquely extremal, then there exists an extremal Beltrami coefficient v(z) in its equivalent class and a compact subset E Δ with positive measure such that the essential upper bound of v(z) on E is less than the norm of [μ].     

Quadrilaterals,extremal quasiconformal extensions and Hamilton sequences

The relationship between Strebel boundary dilatation of a quasisymmetric function h of the unit circle and the dilatation indicated by the change in the modules of the quadrilaterals with vertices on the circle intrigues many mathematicians. It had been a conjecture for some time that the dilatations Ko（h） and K1（h） of h are equal before Anderson and Hinkkanen disproved this by constructing concrete counterexamples. The independent work of Wu and of Yang completely characterizes the condition for Ko（h） = K1 （h） when h has no substantial boundary point. In this paper, we give a necessary and sufficient condition to determine the equality for h admitting a substantial boundary point.     

On extremal decomposition problems

The capacity approach and symmetrization method arc adapted to some extremal decomposition problems on the unit disk or an annulus. The problems on the maximum product of the interior radii of pairwise nonoverlapping domains and the maximum product of the Robin radii of such domains are considered. New invariants with respect to the M?bius transformations of the Riemann sphere are introduced. In particular, for these invariants problems on extremal decomposition with free poles on the unit circle are investigated. Bibliography: 19 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 357, 2008, pp. 54–74.     

On extremal semi-Riemannian submanifolds

Variation of the volume of semi-Riemannian submanifolds is studied. A possible error in the second variational formula in [4] is corrected and it is shown that a semi-Riemannian submanifold cannot be extremal unless it is both definite and codefinite.     

Renewal theory for extremal Markov sequences of Kendall type

The paper deals with renewal theory for a class of extremal Markov sequences connected with the Kendall convolution. We consider here some particular cases of the Wold processes associated with generalized convolutions. We prove an analogue of the Fredholm theorem for all regular generalized convolutions algebras. Using regularly varying functions we prove a Blackwell theorem and a limit theorem for renewal processes defined by Kendall random walks.Our results set new research hypotheses for other generalized convolution algebras to investigate renewal processes constructed by Markov processes with respect to generalized convolutions.     

A note on Hamilton sequences for extremal Beltrami coefficients

F. P. Gardiner gave a sufficient condition for a sequence to be a Hamilton sequence for an extremal Beltrami coefficient. In this note, we shall consider the converse problem, proving that the condition is not necessary.

     

A note on Hamilton sequences of extremal Beltrami differentials

Let X be a hyperbolic Riemann surface and let μ be an extremal Beltrami differential on X with ${6\mu 6}_{\infty }\in (0,1)$. It is proved that, if $\{{?}_n\}$ is a Hamilton sequence of μ, then $\{{?}_n\}$ must be a Hamilton sequence of any extremal Beltrami differential ν contained in $[\mu ]$. This result proved a conjecture of the first author of this paper in 1996. This result is also a generalization of two known results.     

On solving discontinuous extremal problems

An approach to solving discontinuous problems of optimization and control is described. The approach is based on the concept of approximate gradient introduced in Ref. 1. Generalizations of the theorems of Kuhn-Tucker and Dubovitsky-Milyutin and the maximum principle of Pontryagin are proved. The mathematical constructions described allow one to solve a wide variety of applied problems of optimization and control within the class of nonsmooth (including discontinuous) functions. The paper continues the investigations of Refs. 1–2.     

Hamilton sequences for extremal quasiconformal mappings in the unit disk

By studying the mapping by heights for quadratic differentials introduced by Strebel, some relations have been established between the maximal norm sequence for quasisymmetric functions and the Hamilton sequence for extremal quasiconformal mappings in the unit disk. Consequently it is proved that a Hamilton sequence is only determined by e quasisymmetric function. Project supported by the National Natural Science Foundation of China (Grant No. 19871002).     

Uniform estimator of the extremal index of stochastic recurrent sequences

A uniform upper bound of the extremal index of some stochastic recurrent sequences is obtained in the paper. We used a new approach consisting in the consideration of sequences of observations (at deterministic or random moments of time) of a continuous time process given by a stochastic differential equation.     

On a class of extremal problems

In the paper we introduce a class of trigonometrical polynomial extremal problems depending on a continuous parameter 0≤r≤1. It turns out that the two border cases r=0 and r=1 are known problems investigated earlier by Kamae, Mendes-France, Ruzsa and the present author. We also introduce another set of extremal problems for measures with similar parametrization, and prove a duality relationship between the two type of extremal quantities. The proof relies on a minimax theorem proved earlier by the author. The known duality results are proved as corollaries. 1980 MS Classification. Primary 42A05; Secondary 46B25, 46N05.     

On extremal hypergraphs for Hamiltonian cycles

We study sufficient conditions for Hamiltonian cycles in hypergraphs, and obtain both Turán- and Dirac-type results. While the Turán-type result gives an exact threshold for the appearance of a Hamiltonian cycle in a hypergraph depending only on the extremal number of a certain path, the Dirac-type result yields a sufficient condition relying solely on the minimum vertex degree.