Planar bipartite biregular degree sequences

A pair of sequences of natural numbers is called planar if there exists a simple, bipartite, planar graph for which the given sequences are the degree sequences of its parts. For a pair to be planar, the sums of the sequences have to be equal and Euler’s inequality must be satisfied. Pairs that verify these two necessary conditions are called admissible. We prove that a pair of constant sequences is planar if and only if it is admissible (such pairs can be easily listed) and is different from $\left(3^5\right|3^5)$ and $\left(3^{25}\right|5^{15})$.     

On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2

We improve parts of the results of [T. W. Cusick, P. Stanica, Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Mathematics 258 (2002) 289-301; J. Pieprzyk, C. X. Qu, Fast hashing and rotation-symmetric functions, Journal of Universal Computer Science 5 (1) (1999) 20-31]. It is observed that the n-variable quadratic Boolean functions, for , which are homogeneous rotation symmetric, may not be affinely equivalent for fixed n and different choices of s. We show that their weights and nonlinearity are exactly characterized by the cyclic subgroup 〈s−1〉 of Z_n. If , the order of s−1, is even, the weight and nonlinearity are the same and given by . If the order is odd, it is balanced and nonlinearity is given by .     

Optimization over analytic functions whose founrier coefficients are constrained

This article gives necessary and sufficient conditions for local solutions to several very general constrained optimization problems over spaces of analytic functions.The results presented here have many applications, a particular instance of which is the sup-norm approximation of functions continuous on the unit circle in the complex plane by functions continuous on the circle and analytic on the open disk and whose Fourier coefficients satisfy prescribed linear relations.Also, the results in this article generalize Nevanlinna-Pick and Caratheodory-Fejer Interpolation results to allow values of arbitrary derivatives of functions to be assigned or merely bounded. Classically, NP and CF solve only problems with consecutive derivatives specified.In engineering, constraints on the Fourier coefficients of a frequency response function correspond to constraints on its time domain behavior. Indeed the central problems of control theory involve both time and frequency domain constraints. That is precisely what the results in this paper handle.Supported in part by the AFOSR and the NSF     

Caterpillars with maximum degree 3 are antimagic

Let $G=(V,E)$ be a connected graph with $m$ edges. An antimagic labeling of $G$ is a one-to-one mapping from $E$ to $\{1,2,\dots ,m\}$ such that the vertex sum (i.e., sum of the labels assigned to edges incident to a vertex) for distinct vertices are different. A graph $G$ is called antimagic if $G$ has an antimagic labeling. It was conjectured by Hartsfield and Ringel that every tree other than $K_2$ is antimagic. The conjecture remains open though it was verified for trees with some constrains. Caterpillars are an important subclass of trees. This paper shows caterpillars with maximum degree 3 are antimagic, which gives an affirmative answer to an open problem of Lozano et al. (2019).     

Nevanlinna-Pick interpolation by rational functions with a single pole inside the unit disk

We devise an efficient algorithm that, given points z₁,…,z_k in the open unit disk D and a set of complex numbers {f_i,0,f_i,1,…,f_i,ni−1} assigned to each z_i, produces a rational function f with a single (multiple) pole in D, such that f is bounded on the unit circle by a predetermined positive number, and its Taylor expansion at z_i has f_i,0,f_i,1,…,f_i,ni−1 as its first n_i coefficients.     

Superatomic Boolean algebras constructed from strongly unbounded functions

Using Koszmider's strongly unbounded functions, we show the following consistency result: Suppose that κ, λ are infinite cardinals such that κ^{++ +} ≤ λ, κ^<κ = κ and 2^κ = κ⁺, and η is an ordinal with κ⁺ ≤ η < κ⁺⁺ and cf(η) = κ⁺. Then, in some cardinal‐preserving generic extension there is a superatomic Boolean algebra $\mathcal BUsing Koszmider's strongly unbounded functions, we show the following consistency result: Suppose that κ, λ are infinite cardinals such that κ^{++ +} ≤ λ, κ^<κ = κ and 2^κ = κ⁺, and η is an ordinal with κ⁺ ≤ η < κ⁺⁺ and cf(η) = κ⁺. Then, in some cardinal‐preserving generic extension there is a superatomic Boolean algebra $\mathcal B$ such that $\mathrm{ht}(\mathcal B) = \eta + 1$, $\mathrm{wd}_{\alpha }(\mathcal B) = \kappa$ for every α < η and $\mathrm{wd}_{\eta }(\mathcal B) = \lambda$(i.e., there is a locally compact scattered space with cardinal sequence 〈κ〉_η^??〈λ〉). Especially, $\langle {\omega }\rangle _{{\omega }_1}{}^{\smallfrown } \langle {\omega }_3\rangle$ and $\langle {\omega }_1\rangle _{{\omega }_2}{}^{\smallfrown } \langle {\omega }_4\rangle$ can be cardinal sequences of superatomic Boolean algebras.     

Morse theory for analytic functions on surfaces

In this paper we deal with analytic functions defined on a compact two dimensional Riemannian surface S whose critical points are semi degenerated (critical points having a non identically vanishing Hessian). To any element p of the set of semi degenerated critical points Q we assign an unique index which can take the values −1, 0 or 1, and prove that Q is made up of finitely many (critical) points with non zero index and embedded circles. Further, we generalize the famous Morse result by showing that the sum of the indexes of the critical points of f equals χ (S), the Euler characteristic of S. As an intermediate result we locally describe the level set of f near a point p ∈Q. We show that the level set f ⁻¹(f (p)) is either a) the set {p}, or b) the graph of a smooth curve passing through p, or c) the graphs of two smooth curves tangent at p or d) the graphs of two smooth curves building at p a cusp shape.     

Several classes of even-variable 1-resilient rotation symmetric Boolean functions with high algebraic degree and nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, some classes of 2m-variable (m is an odd integer) 1-resilient rotation symmetric Boolean functions are got, whose nonlinearity and algebraic degree are studied. For the first time, we obtain 2m-variable 1-resilient rotation symmetric Boolean functions having high nonlinearity and optimal algebraic degree. In addition, we obtain a class of non-linear rotation symmetric 1-resilient function for every $n\ge 5$, and a class of quadratic rotation symmetric $(k?1)$-resilient function of $n=3k$ variables, where k is an integer.     

Gallai’s path decomposition conjecture for graphs of small maximum degree

Gallai’s path decomposition conjecture states that the edges of any connected graph on $n$ vertices can be decomposed into at most $\frac{n+1}{2}$ paths. We confirm that conjecture for all graphs with maximum degree at most five.     

On the Nevanlinna-Pick interpolation problem for generalized stieltjes functions

The solutions of the Nevanlinna-Pick interpolation problem for generalized Stieltjes matrix functions are parametrized via a fractional linear transformation over a subset of the class of classical Stieltjes functions. The fractional linear transformation of some of these functions may have a pole in one or more of the interpolation points, hence not all Stieltjes functions can serve as a parameter. The set of excluded parameters is characterized in terms of the two related Pick matrices.Dedicated to the memory of M. G. Kreîn     

Intersection Matrices Revisited

Several intersection matrices of s‐subsets versus k‐subsets of a v‐set are introduced in the literature. We study these matrices systematically through counting arguments and generating function techniques. A number of new or known identities appear as natural consequences of this viewpoint; especially, use of the derivative operator and some related operators reveals some connections between intersection matrices and the “combinatorics of creation‐annihilation.” As application, the eigenvalues of several intersection matrices including some generalizations of the adjacency matrices of the Johnson scheme are derived; two new bases for the Bose–Mesner algebra of the Johnson scheme are introduced and the associated intersection numbers are obtained as well. Finally, we determine the rank of some intersection matrices. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 383–397, 2012     

Random walks on quasisymmetric functions

Conditions are provided under which an endomorphism on quasisymmetric functions gives rise to a left random walk on the descent algebra which is also a lumping of a left random walk on permutations. Spectral results are also obtained. Several important random walks are now realized this way: Stanley's QS-distribution results from endomorphisms given by evaluation maps, a-shuffles result from the ath convolution power of the universal character, and the Tchebyshev operator of the second kind introduced recently by Ehrenborg and Readdy yields traditional riffle shuffles. A conjecture of Ehrenborg regarding the spectra for a family of random walks on ab-words is proven. A theorem of Stembridge from the theory of enriched P-partitions is also recovered as a special case.     

Quasi-symmetric functions and the KP hierarchy

Quasi-symmetric functions arise in an approach to solve the Kadomtsev-Petviashvili (KP) hierarchy. This moreover features a new nonassociative product of quasi-symmetric functions that satisfies simple relations with the ordinary product and the outer coproduct. In particular, supplied with this new product and the outer coproduct, the algebra of quasi-symmetric functions becomes an infinitesimal bialgebra. Using these results we derive a sequence of identities in the algebra of quasi-symmetric functions that are in formal correspondence with the equations of the KP hierarchy.     

Some functional equations in the space of uniform distribution functions

In this paper various functional equations which arise in the study of binary operations on the set of uniform probability distribution functions are considered and solved.     

Attractive cycles in the iteration of meromorphic functions

Summary The existence of attractive cycles constitutes a serious impediment to the solution of nonlinear equations by iterative methods. This problem is illustrated in the case of the solution of the equationz tanz=c, for complex values ofc, by Newton's method. Relevant results from the theory of the iteration of rational functions are cited and extended to the analysis of this case, in which a meromorphic function is iterated. Extensive numerical results, including many attractive cycles, are summarized.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under grants A3028 and A7691