On Cross-intersecting Families of Sets

A family of -element subsets and a family of k-element subsets of an n-element set are cross-intersecting if every set from has a nonempty intersection with every set from . We compare two previously established inequalities each related to the maximization of the product , and give a new and short proof for one of them. We also determine the maximum of for arbitrary positive weights ,_k.     

Minimal Connected τ-Critical Hypergraphs

A hypergraph is τ-critical if τ(−{E})<τ() for every edge E ∈ , where τ() denotes the transversal number of . We show that if is a connected τ-critical hypergraph, then −{E} can be partitioned into τ()−1 stars of size at least two, for every edge E ∈ . An immediate corollary is that a connected τ-critical hypergraph has at least 2τ()−1 edges. This extends, in a very natural way, a classical theorem of Gallai on colour-critical graphs, and is equivalent to a theorem of Füredi on t-stable hypergraphs. We deduce a lower bound on the size of τ-critical hypergraphs of minimum degree at least two.     

A Note on Convex Decompositions of a Set of Points in the Plane

For any set P of n points in general position in the plane there is a convex decomposition of P with at most elements. Moreover, any minimal convex decomposition of such a set P has at most elements, where k is the number of points in the boundary of the convex hull of P.Partially supported by Conacyt, MexicoFinal version received: November 10, 2003     

Topologically transitive extensions of bounded operators

Let X be any Banach space and T a bounded operator on X. An extension of the pair (X,T) consists of a Banach space in which X embeds isometrically through an isometry i and a bounded operator on such that When X is separable, it is additionally required that be separable. We say that is a topologically transitive extension of (X, T) when is topologically transitive on , i.e. for every pair of non-empty open subsets of there exists an integer n such that is non-empty. We show that any such pair (X,T) admits a topologically transitive extension , and that when H is a Hilbert space, (H,T) admits a topologically transitive extension where is also a Hilbert space. We show that these extensions are indeed chaotic.Mathematics Subject Classification (2000): 47 A 16     

Infinitely many solutions of a semilinear problem for the Heisenberg Laplacian on the Heisenberg group

We study the semilinear equationwhere is the Heisenberg Laplacian and is the Heisenberg group. The function f C²(×, ) is supposed to satisfy some (subcritical) growth conditions and to be left invariant under the action of the subgroup of consisting of points with integer coordinates.. We show the existence of infinitely many solutions in the space S₁²(), which is the Heisenberg analogue of the Sobolev space W^1,2(^N).Mathematics Subject Classification (2000): 22E30, 22E27     

Associated primes and cofiniteness of local cohomology modules

Let be an ideal of Noetherian ring R and let s be a non-negative integer. Let M be an R-module such that is finite R-module. If s is the first integer such that the local cohomology module is non -cofinite, then we show that is finite. In particular, the set of associated primes of is finite. Let be a local Noetherian ring and let M be a finite R-module. We study the last integer n such that the local cohomology module is not -cofinite and show that n just depends on the support of M.The research of the first author was supported in part by a grant from IPM (No. 83130114).The second author was supported by a grant from University of Tehran (No. 6103023/1/01).     

The Maximum Size of 3-Wise Intersecting and 3-Wise Union Families

Let be an n-uniform hypergraph on 2n vertices. Suppose that and holds for all F₁,F₂,F₃ ∈ . We prove that the size of is at most . The second author was supported by MEXT Grant-in-Aid for Scientific Research (B) 16340027     

On the Set of Cycle Lengths in a Hamiltonian Graph with a Given Maximum Degree

Let n and be two integers such that 2n–1. We describe the set of cycle lengths occurring in any hamiltonian graph G of order n and maximum degree . We conclude that for the case this set contains all the integers belonging to the union [3,2–n+2][n–+2,+1], and for it contains every integer between 3 and +1. We also study the set of cycle lengths in a hamiltonian graph with two fixed vertices of large degree sum. Our main results imply that the stability s(P) for the property of being pancyclic satisfies      

On an eigenvalue problem related to the critical exponent

In this paper we study the eigenvalue problemwhere is a smooth bounded domain, and u is a positive solution of the problemsuch thatwhere S is the best Sobolev constant for the embedding of H¹₀() into L²*(), We prove several estimates for the eigenvalues _i, of (I), i=2,..,N+2 and some qualitative properties of the corresponding eigenfunctions.Supported by M.I.U.R., project Variational methods and nonlinear differential equations.     

On the logarithmic plurigenera of complements of plane curves

Let B be a (not necessarily irreducible) plane curve in ². In the present article, we prove that if and only if Moreover, we determine the curve B when and Mathematics Subject Classification (2000): 14R05, 14H50, 14J26     

Spanning Trails Connecting Given Edges

Suppose that is the set of connected graphs such that a graph G if and only if G satisfies both (F1) if X is an edge cut of G with |X|3, then there exists a vertex v of degree |X| such that X consists of all the edges incident with v in G, and (F2) for every v of degree 3, v lies in a k-cycle of G, where 2k3.In this paper, we show that if G and (G)3, then for every pair of edges e,fE(G), G has a trail with initial edge e and final edge f which contains all vertices of G. This result extends several former results.     

On Resolvable Multipartite G-Designs II

In this paper, it has been proved that and are factorable, where ⊗ denotes wreath product of graphs. As a consequence, a resolvable (k,n,k,2λ) multipartite –design exists for even k. These results generalize the results of Ushio on –factorizations of complete tripartite graphs.     

On Cyclic Packing of a Tree

We prove that there exists a packing of copies of a tree of size into K_n. Moreover, the proof provides an easy algorithm.Acknowledgments. The research of the second author was partially supported by Deutscher Akademischer Austauschdienst.     

A Lower Bound for the Rectilinear Crossing Number

We give a new lower bound for the rectilinear crossing number of the complete geometric graph K_n. We prove that and we extend the proof of the result to pseudolinear drawings of K_n. Dedicated to the memory of our good friend and mentor Víctor Neumann-Lara. Received: April, 2003 Final version received: March 18, 2005     

The cofinality of the saturated uncountable random graph

Assuming CH, let be the saturated random graph of cardinality ₁. In this paper we prove that it is consistent that and can be any two prescribed regular cardinals subject only to the requirement      

A new condensation principle

We generalize (A), which was introduced in [Sch], to larger cardinals. For a regular cardinal >₀ we denote by (A) the statement that and for all regular >,is stationary in It was shown in [Sch] that can hold in a set-generic extension of L. We here prove that can hold in a set-generic extension of L as well. In both cases we in fact get equiconsistency theorems. This strengthens results of [Rä00] and [Rä01]. is equivalent with the existence of 0^#.Mathematics Subject Classification (1991): Primary 03E55, 03E15, Secondary 03E35, 03E60     

Even 2 × 2 Submatrices of a Random Zero-One Matrix

Consider an m×n zero-one matrix A. An s×t submatrix of A is said to be even if the sum of its entries is even. In this paper, we focus on the case m=n and s=t=2. The maximum number M(n) of even 2×2 submatrices of A is clearly and corresponds to the matrix A having, e.g., all ones (or zeros). A more interesting question, motivated by Turán numbers and Hadamard matrices, is that of the minimum number m(n) of such matrices. It has recently been shown that for some constant B. In this paper we show that if the matrix A=A_n is considered to be induced by an infinite zero one matrix obtained at random, then where E_n denotes the number of even 2×2 submatrices of A_n. Results such as these provide us with specific information about the tightness of the concentration of E_n around its expected value of Acknowledgments. The research of both authors was supported by NSF Grant DMS-0139291 and conducted at East Tennessee State University during the Summer of 2002, when Johnson was a student in Godboles Research Experiences for Undergraduates Program. The valuable suggestions of two anonymous referees are gratefully acknowledged.     

Prediction for discrete time series

Let {X_n} be a stationary and ergodic time series taking values from a finite or countably infinite set Assume that the distribution of the process is otherwise unknown. We propose a sequence of stopping times _n along which we will be able to estimate the conditional probability P(=x|X₀,...,) from data segment (X₀,...,) in a pointwise consistent way for a restricted class of stationary and ergodic finite or countably infinite alphabet time series which includes among others all stationary and ergodic finitarily Markovian processes. If the stationary and ergodic process turns out to be finitarily Markovian (among others, all stationary and ergodic Markov chains are included in this class) then almost surely. If the stationary and ergodic process turns out to possess finite entropy rate then _n is upperbounded by a polynomial, eventually almost surely.Mathematics Subject Classification (2000): 62G05, 60G25, 60G10     

Models of set theory with definable ordinals

A DO model (here also referred to a Paris model) is a model of set theory all of whose ordinals are first order definable in . Jeffrey Paris (1973) initiated the study of DO models and showed that (1) every consistent extension T of ZF has a DO model, and (2) for complete extensions T, T has a unique DO model up to isomorphism iff T proves V=OD. Here we provide a comprehensive treatment of Paris models. Our results include the following:1. If T is a consistent completion of ZF+VOD, then T has continuum-many countable nonisomorphic Paris models.2. Every countable model of ZFC has a Paris generic extension.3. If there is an uncountable well-founded model of ZFC, then for every infinite cardinal there is a Paris model of ZF of cardinality which has a nontrivial automorphism.4. For a model ZF, is a prime model is a Paris model and satisfies AC is a minimal model. Moreover, Neither implication reverses assuming Con(ZF).Mathematics Subject Classification (2000): 03C62, 03C50, Secondary 03H99