Perfect matchings in uniform hypergraphs with large minimum degree

A perfect matching in a k-uniform hypergraph on n vertices, n divisible by k, is a set of n/k disjoint edges. In this paper we give a sufficient condition for the existence of a perfect matching in terms of a variant of the minimum degree. We prove that for every k≥3 and sufficiently large n, a perfect matching exists in every n-vertex k-uniform hypergraph in which each set of k−1 vertices is contained in n/2+Ω(logn) edges. Owing to a construction in [D. Kühn, D. Osthus, Matchings in hypergraphs of large minimum degree, J. Graph Theory 51 (1) (2006) 269–280], this is nearly optimal. For almost perfect and fractional perfect matchings we show that analogous thresholds are close to n/k rather than n/2.     

Cafiero approach to the Dieudonné type theorems

An algebra of subsets of a normal topological space containing the open sets is considered and in this context the uniform exhaustivity and uniform regularity for a family of additive functions are studied. Based on these results the Cafiero convergence theorem with the Dieudonné type conditions is proved and in this way also the Nikodým-Dieudonné convergence theorem is obtained.     

Two-sided a posteriori error bounds for incompressible quasi-Newtonian flows

Endre Süli ^{We develop a posteriori upper and lower error bounds for mixedfinite-element approximations of a general family of steady,viscous, incompressible quasi-Newtonian flows in a bounded Lipschitzdomain ; thefamily includes degenerate models such as the power law model,as well as non-degenerate ones such as the Carreau model. Theunified theoretical framework developed herein yields residual-baseda posteriori bounds which measure the error in the approximationof the velocity in the W1, r() norm and that of the pressurein the Lr'() norm, 1/r + 1/r' = 1, r (1, ).}     

Neighborhood hypergraphs of bipartite graphs

Matrix symmetrization and several related problems have an extensive literature, with a recurring ambiguity regarding their complexity and relation to graph isomorphism. We present a short survey of these problems to clarify their status. In particular, we recall results from the literature showing that matrix symmetrization is in fact NP‐hard; furthermore, it is equivalent with the problem of recognizing whether a hypergraph can be realized as the neighborhood hypergraph of a graph. There are several variants of the latter problem corresponding to the concepts of open, closed, or mixed neighborhoods. While all these variants are NP‐hard in general, one of them restricted to the bipartite graphs is known to be equivalent with graph isomorphism. Extending this result, we consider several other variants of the bipartite neighborhood recognition problem and show that they all are either polynomial‐time solvable, or equivalent with graph isomorphism. Also, we study uniqueness of neighborhood realizations of hypergraphs and show that, in general, for all variants of the problem, a realization may be not unique. However, we prove uniqueness in two special cases: for the open and closed neighborhood hypergraphs of the bipartite graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 69–95, 2008     

Discontinuous Galerkin finite element approximation of quasilinear elliptic boundary value problems I: the scalar case

^** Email: Paul.Houston{at}mcs.le.ac.uk^*** Email: Janice.Robson{at}comlab.ox.ac.uk^**** Email: Endre.Suli{at}comlab.ox.ac.uk We develop a one-parameter family of hp-version discontinuousGalerkin finite element methods, parameterised by [–1,1], for the numerical solution of quasilinear elliptic equationsin divergence form on a bounded open set ^d, d 2. In particular,we consider the analysis of the family for the equation –·{µ(x, |u|)u} = f(x) subject to mixed Dirichlet–Neumannboundary conditions on . It is assumed that µ is a real-valuedfunction, µ C( x [0, )), and thereexist positive constants m_µ and M_µ such that m_µ(t– s) µ(x, t)t – µ(x, s)s M_µ(t– s) for t s 0 and all x . Using a result from the theory of monotone operators for any valueof [–1, 1], the corresponding method is shown to havea unique solution u_DG in the finite element space. If u C¹() H^k(), k 2, then with discontinuous piecewise polynomials ofdegree p 1, the error between u and u_DG, measured in the brokenH¹()-norm, is (h^s–1/p^k–3/2), where 1 s min {p+ 1, k}.     

ON THE MINIMUM INTRINSIC 1-VOLUME OF VORONOI CELLS IN LATTICE UNIT SPHERE PACKINGS

A typical 3-dimensional (in short '3D') Voronoi cell of a 3Dlattice has six families of parallel edges. We call any six representants of these six families the generating edges of the Voronoi cell. The sum s of lengths of generating edges of a Voronoi-cell of a lattice unit sphere packing in the 3-dimensional Euclidean space is a special case of intrinsic 1-volumes of 3Dzonotopes with inradius 1 which are investigated accurately in [B]. However, the minimum of this value is unknown even in this special case. As the regular rhombic dodecahedron shows optimal properties in many similar problems, it was reasonable to conjecture that it also has the minimal s value. In this note we present a construction of a lattice unit ball packing whose Voronoi cell possesses an intrinsic 1-volume strictly less than the one of the proper regular rhombic dodecahedron, hence providing a smaller upper bound for s than it was conjectured. A further issue of the note is a formula for edge-lengths of Voronoi cells of lattice unit ball packings that can be used efficiently in similar calculations. This revised version was published online in August 2006 with corrections to the Cover Date.     

Full ordering in the Shorrocks mobility sense of the semiring of monotone doubly stochastic matrices

In this paper, we investigate the ordering on a semiring of monotone doubly stochastic transition matrices in Shorrocks’ sense. We identify a class of an equilibrium index of mobility that induces the full ordering in a semiring, while this ordering is compatible with Dardanoni’s partial ordering on a set of monotone primitive irreducible doubly stochastic matrices.     

On the coefficients of Neumann series of Bessel functions

Recently Pogány and Süli (Proc. Amer. Math. Soc. 137 (7) (2009) 2363-2368) derived a closed-form integral expression for Neumann series of Bessel functions. In this note we precisely characterize the class of functions α that generate the integral representation of a Neumann series of Bessel functions in the sense that the restriction αN_|=(αn) of a function α to the set N of all positive integers is the sequence of coefficients of the initial Neumann series.     

Tensor-Sparsity of Solutions to High-Dimensional Elliptic Partial Differential Equations

A recurring theme in attempts to break the curse of dimensionality in the numerical approximation of solutions to high-dimensional partial differential equations (PDEs) is to employ some form of sparse tensor approximation. Unfortunately, there are only a few results that quantify the possible advantages of such an approach. This paper introduces a class \(\Sigma _n\) of functions, which can be written as a sum of rank-one tensors using a total of at most \(n\) parameters, and then uses this notion of sparsity to prove a regularity theorem for certain high-dimensional elliptic PDEs. It is shown, among other results, that whenever the right-hand side \(f\) of the elliptic PDE can be approximated with a certain rate \(\mathcal {O}(n^{-r})\) in the norm of \({\mathrm H}^{-1}\) by elements of \(\Sigma _n\), then the solution \(u\) can be approximated in \({\mathrm H}^1\) from \(\Sigma _n\) to accuracy \(\mathcal {O}(n^{-r'})\) for any \(r'\in (0,r)\). Since these results require knowledge of the eigenbasis of the elliptic operator considered, we propose a second “basis-free” model of tensor-sparsity and prove a regularity theorem for this second sparsity model as well. We then proceed to address the important question of the extent to which such regularity theorems translate into results on computational complexity. It is shown how this second model can be used to derive computational algorithms with performance that breaks the curse of dimensionality on certain model high-dimensional elliptic PDEs with tensor-sparse data.