On asymmetric coverings and covering numbers

An asymmetric covering is a collection of special subsets S of an n‐set such that every subset T of the n‐set is contained in at least one special S with . In this paper we compute the smallest size of any for We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers , and we determine the following new values: , , , , and . We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10022     

The isoperimetric constant of the random graph process

The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of , taken over all nonempty subsets S ⊂ V (G) of size at most n/2, where ∂S denotes the set of edges with precisely one end in S. A random graph process on n vertices, , is a sequence of graphs, where is the edgeless graph on n vertices, and is the result of adding an edge to , uniformly distributed over all the missing edges. The authors show that in almost every graph process equals the minimal degree of as long as the minimal degree is o(log n). Furthermore, it is shown that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically Θ(log n), the ratio between the isoperimetric constant and the minimum degree falls from 1 to , its final value. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

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     

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.     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

On the Points on the Unit Circle with Finite b–Adic Expansions

Let be an arbitrary integer base and let be the number of different prime factors of with , . Further let be the set of points on the unit circle with finite –adic expansions of their coordinates and let be the set of angles of the points . Then is an additive group which is the direct sum of infinite cyclic groups and of the finite cyclic group . If in case of the points of are arranged according to the number of digits of their coordinates, then the arising sequence is uniformly distributed on the unit circle. On the other hand, in case of the only points in are the exceptional points (1, 0), (0, 1), (–1, 0), (0, –1). The proofs are based on a canonical form for all integer solutions of .     

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     

Uniqueness of Integrable Solutions ∇ζ = Gζ, ζ∣Γ = 0 for Integrable Tensor-Coefficients G and Applications to Elasticity

Let be bounded Lipschitz and relatively open. We show that the solution to the linear first order system 1 : (1) vanishes if and , (e.g. ). We prove to be a norm if with , for some p, q > 1 with 1/p + 1/q = 1 and . We give a new proof for the so called ‘in-finitesimal rigid displacement lemma’ in curvilinear coordinates: Let , satisfy for some with . Then there are and a constant skew-symmetric matrix , such that . (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Quasilinear degenerate parabolic equations of Kirchhoff type

We investigate the evolution problem where H is a Hilbert space, A is a self‐adjoint linear non‐negative operator on H with domain D(A), and is a continuous function. We prove that if , and , then there exists at least one global solution, which is unique if either m never vanishes, or m is locally Lipschitz continuous. Moreover, we prove that if for all , then this problem is well posed in H. On the contrary, if for some it happens that for all , then this problem has no solution if with β small enough. We apply these results to degenerate parabolic PDEs with non‐local non‐linearities. Copyright © 1999 John Wiley & Sons, Ltd.     

Tauberian theorem for m‐spherical transforms on the Heisenberg group

In this paper we prove a Tauberian type theorem for the space L ( H _n ). This theorem gives sufficient conditions for a L ( H _n ) submodule J ? L ( H _n ) to make up all of L ( H _n ). As a consequence of this theorem, we are able to improve previous results on the Pompeiu problem with moments on the Heisenberg group for the space L^∞( H _n ). In connection with the Pompeiu problem, given the vanishing of integrals ∫ z ^m L _g f ( z , 0) dσ ( z ) = 0 for all g ∈ H _n and i = 1, 2 for appropriate radii r₁ and r₂, we now have the (improved) conclusion f ≡ 0, where = · · · and form the standard basis for T^(0,1)( H _n ). (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Eigenvalues of Half‐Linear Boundary Value Problems

We consider the half‐linear boundary value problem where and the weight function q is assumed to change sign. We prove the existence of two sequences , of eigenvalues and derive asymptotic estimates for as .     

A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree

Let X_n be the number of cuts needed to isolate the root in a random recursive tree with n vertices. We provide a weak convergence result for X_n. The basic observation for its proof is that the probability distributions of are recursively defined by , where D_n is a discrete random variable with ? , which is independent of . This distributional recursion was not studied previously in the sense of weak convergence. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Comparing Packing Measures to Hausdorff Measures on the Line

For each 0 < s < 1, define where , denote respectively the s‐dimensional packing measure and Hausdorff measure, and the infimum is taken over all the sets E ⊂ R with . In this paper we give a nontrivial estimation of c(s), namely, for each 0 < s < 1, where . As an application, we obtain a lower density theorem for Hausdorff measures.     

Law of large numbers for increasing subsequences of random permutations

Let the random variable Z_n,k denote the number of increasing subsequences of length k in a random permutation from S_n, the symmetric group of permutations of {1,…,n}. We show that Var(Z) = o((EZ)²) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure U_n on S_n. Define the probability measure μ on S_n by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x₁,x₂,…,x}. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Extending the Erdős–Ko–Rado theorem

Let be a k‐uniform hypergraph on n vertices. Suppose that holds for all . We prove that the size of is at most if satisfies and n is sufficiently large. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Construction of graphs with given circular flow numbers

Suppose r ≥ 2 is a real number. A proper r‐flow of a directed multi‐graph is a mapping such that (i) for every edge , ; (ii) for every vertex , . The circular flow number of a graph G is the least r for which an orientation of G admits a proper r‐flow. The well‐known 5‐flow conjecture is equivalent to the statement that every bridgeless graph has circular flow number at most 5. In this paper, we prove that for any rational number r between 2 and 5, there exists a graph G with circular flow number r. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 304–318, 2003     

A generalization of the Oberwolfach problem

Let n > 1 be an integer and let a₂,a₃,…,a_n be nonnegative integers such that . Then can be factored into ‐factors, ‐factors,…, ‐factors, plus a 1‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 151–161, 2002     

Compactness Conditions for the Green Operator in Lp(ℝ) Corresponding to a General Sturm–Liouville Operator

We consider the equation ℝ, where , for ℝ, (ℝ), (ℝ), (ℝ), (ℝ) := C(ℝ)). We give necessary and sufficient conditions under which, regardless of , the following statements hold simultaneously: I) For any (ℝ) Equation (0.1) has a unique solution (ℝ) where $\int ^{\infty}_{-\infty}$ ℝ. II) The operator (ℝ) → (ℝ) is compact. Here is the Green function corresponding to (0.1). This result is applied to study some properties of the spectrum of the Sturm–Liouville operator.     

A Ramsey‐type problem and the Turán numbers*

For each n and k, we examine bounds on the largest number m so that for any k‐coloring of the edges of K_n there exists a copy of K_m whose edges receive at most k?1 colors. We show that for , the largest value of m is asymptotically equal to the Turá number , while for any constant then the largest m is asymptotically larger than that Turá number. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 120–129, 2002     

The quasi‐randomness of hypergraph cut properties

Let satisfy and suppose a k‐uniform hypergraph on n vertices satisfies the following property; in any partition of its vertices into k sets of sizes , the number of edges intersecting is (asymptotically) the number one would expect to find in a random k‐uniform hypergraph. Can we then infer that H is quasi‐random? We show that the answer is negative if and only if . This resolves an open problem raised in 1991 by Chung and Graham [J AMS 4 (1991), 151–196]. While hypergraphs satisfying the property corresponding to are not necessarily quasi‐random, we manage to find a characterization of the hypergraphs satisfying this property. Somewhat surprisingly, it turns out that (essentially) there is a unique non quasi‐random hypergraph satisfying this property. The proofs combine probabilistic and algebraic arguments with results from the theory of association schemes. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011