An upper bound on the number of Steiner triple systems

Richard Wilson conjectured in 1974 the following asymptotic formula for the number of n ‐vertex Steiner triple systems: \begin{align*} STS(n) = \left( (1+o(1))\frac{n}{e^2} \right)^{\frac{n^2}{6}}\end{align*}. Our main result is that The proof is based on the entropy method. As a prelude to this proof we consider the number F(n) of 1 ‐factorizations of the complete graph on n vertices. Using the Kahn‐Lovász theorem it can be shown that We show how to derive this bound using the entropy method. Both bounds are conjectured to be sharp. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 399–406, 2013     

Non‐rainbow colorings of 3‐, 4‐ and 5‐connected plane graphs

We study vertex‐colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3 ‐connected plane graph with n vertices, then the number of colors in such a coloring does not exceed . If G is 4 ‐connected, then the number of colors is at most , and for n≡3(mod8), it is at most . Finally, if G is 5 ‐connected, then the number of colors is at most . The bounds for 3 ‐connected and 4 ‐connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129–145, 2010     

Small degree out‐branchings

Using a suitable orientation, we give a short proof of a strengthening of a result of Czumaj and Strothmann 4 : Every 2‐edge‐connected graph G contains a spanning tree T with the property that for every vertex v. As an analogue of this result in the directed case, we prove that every 2‐arc‐strong digraph D has an out‐branching B such that . A corollary of this is that every k‐arc‐strong digraph D has an out‐branching B such that , where . We conjecture that in this case would be the right (and best possible) answer. If true, this would again imply a strengthening of a result from 4 concerning spanning trees with small degrees in k‐connected graphs when k ≥ 2. We prove that for acyclic digraphs the existence of an out‐branching satisfying prescribed bounds on the out‐degrees of each vertex can be checked in polynomial time. A corollary of this is that the existence of arc‐disjoint branchings , , where the first is an out‐branching rooted at s and the second an in‐branching rooted at t, can be checked in polynomial time for the class of acyclic digraphs © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 297–307, 2003     

Hyper-rook Domain Inequalities

A hyper-rook domain of an element x in the space (words of length n over alphabets with k elements) is a sphere with center x and fixed radius j in Hamming distance. The number j determines the dimension of the hyper-rook domain. The classical (and far from solved) problem of covering by rook domains (here considered as the 1-dimensional case) is the problem of finding minimal coverings of by such spheres. Very few results are known in the literature for dimensions ≥ 2. We prove in this paper certain classes of inequalities based on coverings using matrices, which give upper and lower bounds for several cases of the problem for higher dimensions.     

Forbidden induced bipartite graphs

Given a fixed bipartite graph H, we study the asymptotic speed of growth of the number of bipartite graphs on n vertices which do not contain an induced copy of H. Whenever H contains either a cycle or the bipartite complement of a cycle, the speed of growth is . For every other bipartite graph except the path on seven vertices, we are able to find both upper and lower bounds of the form . In many cases we are able to determine the correct value of c. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 219–241, 2009     

The Khinchin Inequality for Generalized Rademacher Functions

We give a new proof of the Khinchin inequality for the sequence of k-Rademacher functions: We obtain constants which are independent of k. Although the constants are not best possible, they improve estimates of Floret and Matos [4] and they do have optimal dependence on p as p → ∞.     

Supercritical biharmonic elliptic problems in domains with small holes

Let D be a bounded and smooth domain in R^N, N ≥ 5, P ∈ D. We consider the following biharmonic elliptic problemin Ω = D \B_δ (P), with p supercritical, namely . We find a sequence of resonant exponents such that if is given, with p ≠ p_j for all j, then for all δ > 0 sufficiently small, this problem is solvable (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Small complete caps in PG(N,q), q even

A new family of small complete caps in PG(N,q), q even, is constructed. Apart from small values of either N or q, it provides an improvement on the currently known upper bounds on the size of the smallest complete cap in PG(N,q): for N even, the leading term is replaced by with , for N odd the leading term is replaced by with . © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 420–436, 2007     

The generalized Randić index of trees

The generalized Randi?; index of a tree T is the sum over the edges of T of where is the degree of the vertex x in T. For all , we find the minimal constant such that for all trees on at least 3 vertices, , where is the number of vertices of T. For example, when . This bound is sharp up to the additive constant—for infinitely many n we give examples of trees T on n vertices with . More generally, fix and define , where is the number of leaves of T. We determine the best constant such that for all trees on at least 3 vertices, . Using these results one can determine (up to terms) the maximal Randi?; index of a tree with a specified number of vertices and leaves. Our methods also yield bounds when the maximum degree of the tree is restricted. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 270–286, 2007     

Eigenvalue bounds for Hill's equation

For Hill's equation the lowest eigenvalue a₀ of the boundary value problem y(x + 1) = y(x) is considered. Introducing L_p norms of the function f (x), lower bounds for a₀ which depend only on this norm are derived for p = 1,2 and ∞ by solving a variational principle. For these lower bounds analytical expressions are obtained. The quality of the approximations thus obtained is discussed for Mathieu's equation and an application in magnetohydrodynamics is considered.     

Random coloring method in the combinatorial problem of Erdős and Lovász

The work deals with a combinatorial problem of P. Erd?s and L. Lovász concerning simple hypergraphs. Let denote the minimum number of edges in an n‐uniform simple hypergraph with chromatic number at least . The main result of the work is a new asymptotic lower bound for . We prove that for large n and r satisfying the following inequality holds where . This bound improves previously known bounds for . The proof is based on a method of random coloring. We have also obtained results concerning colorings of h‐simple hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Semi-Classical Asymptotic of Spectral Function for Some h-Admissible Operators

In this paper the results from [7, 8], concerning the asymptotic behaviour of the spectral function on the diagonal for Schrodinger operators h →0, are extended to the case of some h-admissible operators, acting in Rⁿ, no 2.     

Spectral Estimations for Can nical Systems

Two–dimensional canonical systems are boundary value problems of the form with y₁(0) = 0 and Weyl's limit point case at L. The 2 × 2 matrix valued function H is real, symmetric and nonnegative, . The correspondence between canonical systems and their Titchmarsh–Weyl coefficients Q is a bijection between the class of all matrix functions H with tr H(x) = 1 a.e. on [0, L) and the class of the Nevanlinna functions ℕ augmented by the function Q ≡ 8. Each Titchmarsh–Weyl coefficient Q ∈ ℕ can be represented by means of a measure σ, the so–called spectral measure of the canonical system. In this note matrix functions H are specified whose corresponding spectral measures σ satisfy conditions of the form or . Herewith we generalize corresponding results of M.G. Krein and I. S. Kac for so–called vibrating strings.     

Über eine Verallgemeinerung des Begriffs „Charakteristik”︁ bei partiellen Differentialgleichungen erster Ordnung

As, in general, the projections of characteristics into the x-space intersect for finite values of t, the global solution of a conservation law cannot be determined from the characteristic system of the equation, is considered. Only in the linear case, this equation coincides with the equation of the projections of characteristics. For convex h and all x₀ this equation has a solution almost everywhere, and the properties of this solution permit to construct a global solution of the conservation law using strips, in the same way as this is done for linear problems by the method of characteristics.     

Trace identities for solutions of the wave equation with initial data supported in a ball

Suppose u is the solution of the initial value problem Suppose n ≥ 1 is odd, f and g are supported in a ball B with boundary S, and one of f or g is zero. We derive identities relating the norm of f or g to the norm of the trace of u on S × [0,∞) . These identities are derived using integral geometric and multiplier methods. Copyright © 2005 John Wiley & Sons, Ltd.     

Arc‐chromatic number of digraphs in which every vertex has bounded outdegree or bounded indegree

A k‐digraph is a digraph in which every vertex has outdegree at most k. A ‐digraph is a digraph in which a vertex has either outdegree at most k or indegree at most l. Motivated by function theory, we study the maximum value Φ (k) (resp. ) of the arc‐chromatic number over the k‐digraphs (resp. ‐digraphs). El‐Sahili [3] showed that . After giving a simple proof of this result, we show some better bounds. We show and where θ is the function defined by . We then study in more detail properties of Φ and . Finally, we give the exact values of and for . © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 315–332, 2006     

Strengths and Weaknesses of LH Arithmetic

In this paper we provide a new arithmetic characterization of the levels of the og‐time hierarchy (LH). We define arithmetic classes and that correspond to ‐LOGTIME and ‐LOGTIME, respectively. We break and into natural hierarchies of subclasses and . We then define bounded arithmetic deduction systems ′ whose ‐definable functions are precisely B( ‐LOGTIME). We show these theories are quite strong in that (1) LIOpen proves for any fixed m that , (2) TAC, a theory that is slightly stronger than ′ whose (LH)‐definable functions are LH, proves LH is not equal to ‐TIME(s) for any m> 0, where 2^s ∈L, s(n) ∈ ω(log n), and (3) TAC proves LH ≠ for all k and m. We then show that the theory TAC cannot prove the collapse of the polynomial hierarchy. Thus any such proof, if it exists, must be argued in a stronger systems than ours.     

Die Lösung der Prae-Maxwellschen Gleichungen mit Hilfe vollständiger Lösungssysteme

This paper deals with the Neumann problem of the pre-Maxwell partial differential equations for a vector field v defined in a region G ? R ³. We approximate its uniquely determined solution (integrability conditions assumed) uniformly on G by explicitly computable particular integrals and linear combinations of vector fields with a “fundamental” sequence of points .     

On the Multiplicity of Solutions Of a Differential Equation Arising in Chemical Reactor Theory

Consider the boundary value problem where β ? 0, τ ? 0. We are concerned with a mathematically rigorous numerical study of the number of solutions in any bounded portion of the positive quadrant (τ ? 0, β ? 0) of the τ, β plane. These correct computational results may then be matched with asymptotic (β→∞, τ ? 0) results developed earlier. These numerical results are based on the development of a posteriori error estimates for the numerical solution of an associated initial-value problem and a priori bounds on .     

Chaotic Motion Generated by Delayed Negative Feedback Part II: Construction of Nonlinearities

We construct a smooth function g* : IR ? IR with such that the equation has a slowly oscillating periodic solution y, and a slowly oscillating solution z* whose phase curve is homoclinic with respect to the orbit o of y in the space C = C⁰([1,0],IR). For an associated Poincaré map we obtain a transversal homoclinic loop. The proof of transversality employs a criterion which uses oscillation properties of solutions of variational equations. The main result is that the trajectories (ψn)^∞_-∞ of the Poincaré map in a neighbourhood of the homoclinic loop form a hyperbolic set on which the motion is chaotic.