From spline approximation to Roth’s equation and Schur functors

Alfeld and Schumaker provide a formula for the dimension of the space of piecewise polynomial functions, called splines, of degree d and smoothness r on a generic triangulation of a planar simplicial complex Δ, for d ≥ 3r + 1. Schenck and Stiller conjectured that this formula actually holds for all d ≥ 2r + 1. Up to this moment there was not known a single example where one could show that the bound d ≥ 2r + 1 is sharp. However, in 2005, a possible such example was constructed to show that this bound is the best possible (i.e., the Alfeld–Schumaker formula does not hold if d = 2r), except that the proof that this formula actually works if d ≥ 2r + 1 has been a challenge until now when we finally show it to be true. The interesting subtle connections with representation theory, matrix theory and commutative and homological algebra seem to explain why this example presented such a challenge. Thus in this paper we present the first example when it is known that the bound d ≥ 2r + 1 is sharp for asserting the validity of the Alfeld–Schumaker formula.     

Rainbow Connection Number and Radius

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) ≤  r(r + 2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K _1,n for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) ≤  rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 ? 1, where n is order of the graph (Caro et al. in Electron J Comb 15(1):Research paper 57, 13, 2008). It is known that computing rc(G) is NP-Hard (Chakraborty and fischer in J Comb Optim 1–18, 2009). Here, we present a (r + 3)-factor approximation algorithm which runs in O(nm) time and a (d + 3)-factor approximation algorithm which runs in O(dm) time to rainbow colour any connected graph G on n vertices, with m edges, diameter d and radius r.     

Principal Functions for Bi-free Central Limit Distributions

We find the principal function of the completely non-normal operator l(v₁) + l(v₁)* + i(r(v₂) + r(v₂)*) on a subspace of the full Fock space \({\mathcal{F}}({\mathcal{H}})\) which arises from a bi-free central limit distribution. As an application, we find the essential spectrum of this operator.     

Sequences with constant number of return words

An infinite word has the property R _m if every factor has exactly m return words. Vuillon showed that R ₂ characterizes Sturmian words. We prove that a word satisfies R _m if its complexity function is (m ? 1)n + 1 and if it contains no weak bispecial factor. These conditions are necessary for m = 3, whereas for m = 4 the complexity function need not be 3n + 1. A new class of words satisfying R _m is given.     

Estimate for index of hypersurfaces in spheres with null higher order mean curvature

In a recent paper (Barros, Sousa in: Kodai Math. J. 2009) the authors proved that closed oriented non-totally geodesic minimal hypersurfaces of the Euclidean unit sphere have index of stability greater than or equal to n + 3 with equality occurring at only Clifford tori provided their second fundamental forms A satisfy the pinching: |A|² ≥ n. The natural generalization for this pinching is ?(r + 2)S _r+2 ≥ (n ? r)S _r  > 0. Under this condition we shall extend such result for closed oriented hypersurface Σ ⁿ of the Euclidean unit sphere ${\mathbb{S}^{n+1}}$ with null S _r+1 mean curvature by showing that the index of r-stability, ${Ind_{\Sigma^n}^{r}}$ , also satisfies ${Ind_{\Sigma^n}^{r}\ge n+3}$ . Instead of the previous hypothesis if we consider ${\frac{S_{r+2}}{{S_r}}}$ constant we have the same conclusion. Moreover, we shall prove that, up to Clifford tori, closed oriented hypersurfaces ${\Sigma^{n}\subset \mathbb{S}^{n+1}}$ with S _r+1 = 0 and S _r+2 < 0 have index of r-stability greater than or equal to 2n + 5.     

Bijections on Rooted Trees with Fixed Size of Maximal Decreasing Subtrees

Recently, Seo and Shin showed that the number of rooted trees on [n + 1] = 1, 2, . . . , n+1 such that the maximal decreasing subtree with the same root has k + 1 vertices is equal to the number of functions f : [n] → [n] such that the image of f contains [k]. We give a bijective proof of this theorem.     

Proof of the bandwidth conjecture of Bollobás and Komlós

In this paper we prove the following conjecture by Bollobás and Komlós: For every γ > 0 and integers r ≥ 1 and Δ, there exists β > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r ? 1)/r + γ)n and H is an r-chromatic graph with n vertices, bandwidth at most β n and maximum degree at most Δ, then G contains a copy of H.     

Approximating a class of combinatorial problems with rational objective function

In the late seventies, Megiddo proposed a way to use an algorithm for the problem of minimizing a linear function a ₀ + a ₁ x ₁ + . . . + a _n x _n subject to certain constraints to solve the problem of minimizing a rational function of the form (a ₀ + a ₁ x ₁ + . . . + a _n x _n )/(b ₀ + b ₁ x ₁ + . . . + b _n x _n ) subject to the same set of constraints, assuming that the denominator is always positive. Using a rather strong assumption, Hashizume et al. extended Megiddo’s result to include approximation algorithms. Their assumption essentially asks for the existence of good approximation algorithms for optimization problems with possibly negative coefficients in the (linear) objective function, which is rather unusual for most combinatorial problems. In this paper, we present an alternative extension of Megiddo’s result for approximations that avoids this issue and applies to a large class of optimization problems. Specifically, we show that, if there is an α-approximation for the problem of minimizing a nonnegative linear function subject to constraints satisfying a certain increasing property then there is an α-approximation (1/α-approximation) for the problem of minimizing (maximizing) a nonnegative rational function subject to the same constraints. Our framework applies to covering problems and network design problems, among others.     

Determination of the spacetime from local time measurements

We consider an inverse problem for a Lorentzian spacetime (M, g), and show that time measurements, that is, the knowledge of the Lorentzian time separation function on a submanifold \(\Sigma \subset M\) determine the \(C^\infty \)-jet of the metric in the Fermi coordinates associated to \(\Sigma \). We use this result to study the global determination of the spacetime (M, g) when it has a real-analytic structure or is stationary and satisfies the Einstein-scalar field equations. In addition to this, we require that (M, g) is geodesically complete modulo scalar curvature singularities. The results are Lorentzian counterparts of extensively studied inverse problems in Riemannian geometry—the determination of the jet of the metric and the boundary rigidity problem. We give also counterexamples in cases when the assumptions are not valid, and discuss inverse problems in general relativity.     

Schur–Weyl duality over finite fields

We prove a version of the Schur–Weyl duality over finite fields. We prove that for any field k, if k has at least r + 1 elements, the Schur–Weyl duality holds for the rth tensor power of a finite dimensional vector space V. Moreover, if the dimension of V is at least r + 1, the natural map ${{k\mathfrak{S}_r \to \mathsf{End}_{{\rm GL}(V)}(V^{\otimes r})}}We prove a version of the Schur–Weyl duality over finite fields. We prove that for any field k, if k has at least r + 1 elements, the Schur–Weyl duality holds for the rth tensor power of a finite dimensional vector space V. Moreover, if the dimension of V is at least r + 1, the natural map k\mathfrakS_r ? End_GL(V)(V^?r){{k\mathfrak{S}_r \to \mathsf{End}_{{\rm GL}(V)}(V^{\otimes r})}} is an isomorphism. This isomorphism may fail if dim _k V is not strictly larger than r.     

Constant-approximation for optimal data aggregation with physical interference

In this paper, we study the aggregation problem with power control under the physical interference. The maximum power is bounded. The goal is to assign power to nodes and schedule transmissions toward the sink without physical interferences such that the total number of time slots is minimized. Under the assumption that the unit disk graph G _{δ r} with transmission range δ r is connected for some constant 0 < δ ≤ 1/3^1/α , where r is the maximum transmission range determined by the maximum power, an approximation algorithm is presented with at most b ³(log₂ n + 6) + (R?1)(μ ₁ + μ ₂) time slots, where n is the number of nodes, R is the radius of graph G _{δ r} with respect to the sink, and b, μ ₁, μ ₂ are constants. Since both R and log₂ n are lower bounds for the optimal latency of aggregation in the unit disk graph G _{δ r} , our algorithm has a constant-approximation ratio for the aggregation problem in G _{δ r} .     

A note on the Structure of Turán Densities of Hypergraphs

Let r ≥ 2 be an integer. A real number α ∈ [0, 1) is a jump for r if there exists c > 0 such that no number in (α, α + c) can be the Turán density of a family of r-uniform graphs. A result of Erd?s and Stone implies that every α ∈ [0, 1) is a jump for r = 2. Erd?s asked whether the same is true for r ≥ 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumps for every r ≥ 3. However, there are still a lot of open questions on determining whether or not a number is a jump for r ≥ 3. In this paper, we first find an infinite sequence of non-jumps for r = 4, then extend one of them to every r ≥ 4. Our approach is based on the techniques developed by Frankl and Rödl.     

Sphere coverings and identifying codes

In any connected, undirected graph G = (V, E), the distance d(x, y) between two vertices x and y of G is the minimum number of edges in a path linking x to y in G. A sphere in G is a set of the form S _r (x) = {y ∈ V : d(x, y) = r}, where x is a vertex and r is a nonnegative integer called the radius of the sphere. We first address in this paper the following question: What is the minimum number of spheres with fixed radius r ≥ 0 required to cover all the vertices of a finite, connected, undirected graph G? We then turn our attention to the Hamming Hypercube of dimension n, and we show that the minimum number of spheres with any radii required to cover this graph is either n or n + 1, depending on the parity of n. We also relate the two above problems to other questions in combinatorics, in particular to identifying codes.     

The formation of black holes in spherically symmetric gravitational collapse

We consider the spherically symmetric, asymptotically flat Einstein–Vlasov system. We find explicit conditions on the initial data, with ADM mass M, such that the resulting spacetime has the following properties: there is a family of radially outgoing null geodesics where the area radius r along each geodesic is bounded by 2M, the timelike lines \({r=c\in [0,2M]}\) are incomplete, and for r > 2M the metric converges asymptotically to the Schwarzschild metric with mass M. The initial data that we construct guarantee the formation of a black hole in the evolution. We give examples of such initial data with the additional property that the solutions exist for all r ≥ 0 and all Schwarzschild time, i.e., we obtain global existence in Schwarzschild coordinates in situations where the initial data are not small. Some of our results are also established for the Einstein equations coupled to a general matter model characterized by conditions on the matter quantities.     

On the Enumeration of Non-Crossing Pairings of Well-Balanced Binary Strings

A non-crossing pairing on a binary string pairs ones and zeroes such that the arcs representing the pairings are non-crossing. A binary string is well-balanced if it is of the form ${1^{a_1} 0^{a_1}1^{a_2} 0^{a_2} . . .1^{a_r} 0^{a_r}}$ . In this paper we establish connections between non-crossing pairings of well-balanced binary strings and various lattice paths in plane. We show that for well-balanced binary strings with a ₁ ≤ a ₂ ≤  . . . ≤  a _r , the number of non-crossing pairings is equal to the number of lattice paths on the plane with certain right boundary, and hence can be enumerated by differential Goncarov polynomials. For the regular binary strings S =  (1 ^k 0 ^k ) ⁿ , the number of non-crossing pairings is given by the (k + 1)-Catalan numbers. We present a simple bijective proof for this case.     

On multiplicative functions which are additive on sums of primes

Let ${f : \mathbb{N} \to \mathbb{C}}$ be a multiplicative function satisfying f(p ₀) ≠ 0 for at least one prime number p ₀, and let k ≥ 2 be an integer. We show that if the function f satisfies f(p ₁ + p ₂ + . . . + p _k ) = f(p ₁) + f(p ₂) + . . . + f(p _k ) for any prime numbers p ₁, p ₂, . . . ,p _k then f must be the identity f(n) = n for each ${n \in \mathbb{N}}$ . This result for k = 2 was established earlier by Spiro, whereas the case k = 3 was recently proved by Fang. In the proof of this result for k ≥ 6 we use a recent result of Tao asserting that every odd number greater than 1 is the sum of at most five primes.     

Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions

We survey the properties of two parameters introduced by C. Ding and the author for quantifying the balancedness of vectorial functions and of their derivatives. We give new results on the distribution of the values of the first parameter when applied to F + L, where F is a fixed function and L ranges over the set of linear functions: we show an upper bound on the nonlinearity of F by means of these values, we determine then the mean of these values and we show that their maximum is a nonlinearity parameter as well, we prove that the variance of these values is directly related to the second parameter. We briefly recall the known constructions of bent vectorial functions and introduce two new classes obtained with Gregor Leander. We show that bent functions can be used to build APN functions by concatenating the outputs of a bent (n, n/2)-function and of some other (n, n/2)-function. We obtain this way a general infinite class of quadratic APN functions. We show that this class contains the APN trinomials and hexanomials introduced in 2008 by L. Budaghyan and the author, and a class of APN functions introduced, in 2008 also, by Bracken et al.; this gives an explanation of the APNness of these functions and allows generalizing them. We also obtain this way the recently found Edel?CPott cubic function. We exhibit a large number of other sub-classes of APN functions. We eventually design with this same method classes of quadratic and non-quadratic differentially 4-uniform functions.     

On Quadratic Integral Polynomials with only Finitely Many Roots in any Commutative Finite-Dimensional Algebra

The monic quadratic polynomials f with integer coefficients such that each commutative finite-dimensional algebra over a field contains only finitely many roots of f are determined as the polynomials of the form f = X ² + (2m + 1)X + m ² + m, where ${m \in \mathbb{Z}}$ .     

Infeasible Mehrotra-Type Predictor-Corrector Interior-Point Algorithm for the Cartesian P *(κ)-LCP Over Symmetric Cones

We propose an infeasible Mehrotra-type predictor-corrector algorithm with a new center parameter updating scheme for Cartesian P _*(κ)-linear complementarity problem over symmetric cones. Based on the Nesterov-Todd direction, we show that the iteration-complexity bound of the proposed algorithm is 𝒪((1 + κ)³ r ²log ε^?1), where r is the rank of the associated Euclidean Jordan algebras and κ is the handicap of the problem and ε > 0 is the required precision. Some numerical results are reported as well.     

Infinitely many Gerretsen-Blundon style quadratic inequalities, all strongest in Blundon’s sense

Blundon has proved that if R, r and s are respectively the circumradius, the inradius and the semiperimeter of a triangle, then the strongest possible inequalities of the form q(R, r) ≤ s ² ≤ Q(R, r) that hold for all triangles becoming equalities for the equilaterals where q, Q real quadratic forms, occur for the Gerretsen forms q _B (R, r) = 16Rr ? 5r ² and Q _B (R, r) = 4R ² + 4Rr + 3r ²; strongest in the sense that if Q is a quadratic form and s ² ≤ Q(R, r) ≤ Q _B (R, r) for all triangles then Q(R, r) = Q _B (R, r), and similarly for q _B (R, r). In this paper we prove that Q _B (resp. q _B ) is just one of infinitely many forms that appear as minimal (resp. maximal) elements in the partial order induced by the comparability relation in a certain set of forms, and we conclude that all these minimal forms are strongest in Blundon’s sense. We actually find all possible such strongest forms. Moreover we find all possible quadratic forms q, Q for which q(R, r) ≤ s ² ≤ Q(R, r) for all triangles and which hold as equalities for the equilaterals.