Coloring graphs from random lists of fixed size

Let G = G(n) be a graph on n vertices with maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list uniformly at random from all k‐subsets of a color set of size . Such a list assignment is called a random ‐list assignment. In this paper, we are interested in determining the asymptotic probability (as ) of the existence of a proper coloring ? of G, such that for every vertex v of G. We show, for all fixed k and growing n, that if , then the probability that G has such a proper coloring tends to 1 as . A similar result for complete graphs is also obtained: if and L is a random ‐list assignment for the complete graph K_n on n vertices, then the probability that K_n has a proper coloring with colors from the random lists tends to 1 as .Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 317‐327, 2014     

Gelfand numbers of operators with values in a Hilbert space

In the paper we prove two inequalities involving Gelfand numbers of operators with values in a Hilbert space. The first inequality is a Rademacher version of the main result in [Pa-To-1] which relates the Gelfand numbers of an operator from a Banach spaceX intol ₂ ⁿ with a certain Rademacher average for the dual operator. The second inequality states that the Gelfand numbers of an operatoru froml ₁ ^N into a Hilbert space satisfy the inequality

Linear fractional composition operators on H2

If ? is an analytic function mapping the unit diskD into itself, the composition operatorC _? is the operator onH ² given byC _?f=fo?. The structure of the composition operatorC _? is usually complex, even if the function ? is fairly simple. In this paper, we consider composition operators whose symbol ? is a linear fractional transformation mapping the disk into itself. That is, we will assume throughout that $$\varphi \left( z \right) = \frac{{az + b}}{{cz + d}}$$ for some complex numbersa, b, c, d such that ? maps the unit diskD into itself. For this restricted class of examples, we address some of the basic questions of interest to operator theorists, including the computation of the adjoint.     

Generalized quasilinearization method for reaction-diffusion equations under nonlinear and nonlocal flux conditions

In this paper we consider an initial boundary value problem for a reaction-diffusion equation under nonlinear and nonlocal Robin type boundary condition. Assuming the existence of an ordered pair of upper and lower solutions we establish a generalized quasilinearization method for the problem under consideration whose characteristic feature consists in the construction of monotone sequences converging to the unique solution within the interval of upper and lower solutions, and whose convergence rate is quadratic. Thus this method provides an efficient iteration technique that produces not only improved approximations due to the monotonicity of its iterates, but yields also a measure of the convergence rate.     

On interpolation by radial polynomials

A lemma of Micchelli's, concerning radial polynomials and weighted sums of point evaluations, is shown to hold for arbitrary linear functionals, as is Schaback's more recent extension of this lemma and Schaback's result concerning interpolation by radial polynomials. Schaback's interpolant is explored. Happy 60th and beyond, Charlie! Mathematics subject classifications (2000) 41A05, 41A6.     

How to grow it? Strategies of mathematical development presented by the example of enumerating certain set partitions

Mathematische Semesterberichte - We describe in the form of a dialogue a development of various reflections on the combinatorics of set partitions; among the topics we pursue are...     

Unitary equivalence of one-parameter groups of Toeplitz and composition operators

The composition operators on H² whose symbols are hyperbolic automorphisms of the unit disk fixing ±1 comprise a one-parameter group and the analytic Toeplitz operators coming from covering maps of annuli centered at the origin whose radii are reciprocals also form a one-parameter group. Using the eigenvectors of the composition operators and of the adjoints of the Toeplitz operators, a direct unitary equivalence is found between the restrictions to zH² of the group of Toeplitz operators and the group of adjoints of these composition operators. On the other hand, it is shown that there is not a unitary equivalence of the groups of Toeplitz operators and the adjoints of the composition operators on the whole of H², but there is a similarity between them.     

Retracing the residual curve of a Lyapunov equation solver

Let A∈ℝ ^n×n and let B∈ℝ ^n×p and consider the Lyapunov matrix equation AX+XA ^T +BB ^T =0. If A+A ^T <0, then the extended Krylov subspace method (EKSM) can be used to compute a sequence of low rank approximations of X. In this paper we show how to construct a symmetric negative definite matrix A and a column vector B, for which the EKSM generates a predetermined residual curve.     

On the equivalence of quadratic APN functions

Establishing the CCZ-equivalence of a pair of APN functions is generally quite difficult. In some cases, when seeking to show that a putative new infinite family of APN functions is CCZ inequivalent to an already known family, we rely on computer calculation for small values of n. In this paper we present a method to prove the inequivalence of quadratic APN functions with the Gold functions. Our main result is that a quadratic function is CCZ-equivalent to the APN Gold function x^2r+1{x^{2^r+1}} if and only if it is EA-equivalent to that Gold function. As an application of this result, we prove that a trinomial family of APN functions that exist on finite fields of order 2 ⁿ where n ≡ 2 mod 4 are CCZ inequivalent to the Gold functions. The proof relies on some knowledge of the automorphism group of a code associated with such a function.