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.     

Reconstructing under Group Actions

We give a bound on the reconstructibility of an action GX in terms of the reconstructibility of a the action NX, where N is a normal subgroup of G, and the reconstructibility of the quotient G/N. We also show that if the action GX is locally finite, in the sense that every point is either in an orbit by itself or has finite stabilizer, then the reconstructibility of GX is at most the reconstructibility of G. Finally, we give some applications to geometric reconstruction problems.     

Canonical Pattern Ramsey Numbers

A color pattern is a graph whose edges have been partitioned into color classes. A family of color patterns is a Ramsey family provided there is some sufficiently large integer N such that in any edge coloring of the complete graph K_N there is an (isomorphic) copy of at least one of the patterns from . The smallest such N is the Ramsey number of the family . The classical Canonical Ramsey theorem of Erds and Rado asserts that the family of color patterns is a Ramsey family if it consists of monochromatic, rainbow (totally multicolored) and lexically colored complete graphs. In this paper we treat the asymmetric case by studying the Ramsey number of families containing a rainbow triangle, a lexically colored complete graph and a fixed arbitrary monochromatic graph. In particular we give asymptotically tight bounds for the Ramsey number of a family consisting of rainbow and monochromatic triangle and a lexically colored K_N. Among others, we prove some canonical Ramsey results for cycles.     

The structure of <Emphasis Type="Italic">F</Emphasis>-pure rings

For a reduced F-finite ring R of characteristic p>0 and q=p^e one can write where M_q has no free direct summands over R. We investigate the structure of F-finite, F-pure rings R by studying how the numbers a_q grow with respect to q. This growth is quantified by the splitting dimension and the splitting ratios of R which we study in detail. We also prove the existence of a special prime ideal (R) of R, called the splitting prime, that has the property that R/(R) is strongly F-regular. We show that this ideal captures significant information with regard to the F-purity of R.Dedicated to Professor Melvin Hochster on the occasion of his sixtieth birthday     

Extremal Problems for Imbalanced Edges

Albertson [2] has introduced the imbalance of an edge e=uv in a graph G as |d_G(u)−d_G(v)|. If for a graph G of order n and size m the minimum imbalance of an edge of G equals d, then our main result states that with equality if and only if G is isomorphic to We also prove best-possible upper bounds on the number of edges uv of a graph G such that |d_G(u)−d_G(v)|≥d for some given d.     

Cyclicity of elliptic curves modulo <Emphasis Type="Italic">p</Emphasis> and elliptic curve analogues of Linnik’s problem

Let E be an elliptic curve defined over and of conductor N. For a prime we denote by the reduction of E modulo p. We obtain an asymptotic formula for the number of primes p x for which is cyclic, assuming a certain generalized Riemann hypothesis. The error terms that we get are substantial improvements of earlier work of J-P. Serre and M. Ram Murty. We also consider the problem of finding the size of the smallest prime p = p_E for which the group is cyclic and we show that, under the generalized Riemann hypothesis, p_E = ((log N)^{4 +} ) if E is without complex multiplication, and p_E = ((log N)^{2 +} ) if E is with complex multiplication, for any 0 < < 1.Mathematics Subject Classification (2001):11G05, 11N36, 11R45Research supported in part by an Ontario Graduate Scholarship.Research supported in part by an NSERC grant.Revised version: 11 April 2004     

Bipartite Subgraphs and Quasi-Randomness

We say that a family of graphs is p-quasi-random, 0<p<1, if it shares typical properties of the random graph G(n,p); for a definition, see below. We denote by the class of all graphs H for which and the number of not necessarily induced labeled copies of H in G_n is at most (1+o(1))p^e(H)n^v(H) imply that is p-quasi-random. In this note, we show that all complete bipartite graphs K_a,b, a,b2, belong to for all 0<p<1.Acknowledgments We would like to thank Andrew Thomason for fruitful discussions and Yoshi Kohayakawa for organizing Extended Workshop on Combinatorics in eq5 Paulo, Ubatuba, and Rio de Janeiro, where a part of this work was done. We also thank the referees for their careful work.The first author was partially supported by NSF grant INT-0072064The second author was partially supported by NSF grants DMS-9970622, DMS-0301228 and INT-0072064Final version received: October 24, 2003     

3-Wise Exactly 1-Intersecting Families of Sets

Let f(l, t, n) be the maximal size of a family such that any l2 sets of have an exactly t1-element intersection. If l3, it trivially comes from [8] that the optimal families are trivially intersecting (there is a t-element core contained by all the members of the family). Hence it is easy to determine Let g(l,t,n) be the maximal size of an l-wise exaclty t-intersecting family that is not trivially t-intersecting. We give upper and lower bounds which only meet in the following case: g(3, 1, n) = n^2/3(1 + o(1)).     

Cumulants are universal homomorphisms into Hausdorff groups

This is a contribution to the theory of sums of independent random variables at an algebraico-analytical level: Let Prob denote the convolution semigroup of all probability measures on with all moments finite, topologized by polynomially weighted total variation. We prove that the cumulant sequence regarded as a function from Prob into the additive topological group ofall real sequences, is universal among continuous homomorphisms from Prob into Hausdorff topological groups, in the usual sense that every other such homomorphism factorizes uniquely through . An analogous result, referring to just the first cumulants,holds for the semigroup of all probability measures with existing rth moments. In particular, there is no nontrivial continuous homomorphism from the convolution semigroup of all probability measures, topologized by the total variation metric, into any Hausdorff topological group.Mathematics Subject Classification (2000): 60B15, 60E10, 60G50     

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.     

Some Geometric Aspects of Operators Acting from L 1

We study some properties of the space (L₁,X) of all continuous linear operators acting from L₁ to a Banach space X. It is proved that every operator T ∈ (L₁, X) ``almost' attains its norm at the entire positive cone of functions supported at some suitable measurable subset , μ(A) > 0. Using this fact and a new elementary technique we prove that every operator T∈ (L₁) = (L₁, L₁) is uniquely represented in the form T= R+S, R, S∈ (L₁) , where R is representable and S possess a special property (*). Moreover, this representation generates a decomposition of the space (L₁) into complemented subspaces by means of contractive projections (the fact that the subspace of all representable operators is complemented in (L₁) was proved before by Z. Liu).     

Restricting semistable bundles on the projective plane to conics

We study the restrictions of rank 2 semistable vector bundles E on to conics. A Grauert-Mülich type theorem on the generic splitting is proven. The jumping conics are shown to have the scheme structure of a hypersurface of degree c₂(E) when c₁(E)=0 and of degree c₂(E)–1 when c₁(E)=–1. Some examples of jumping conics and jumping lines are studied in detail.Mathematics Subject Classification (2000):Primary:14J60; Secondary:14F05     

Maximality of Positive Operator-valued Measures

A positive operator-valued measure is a (weak-star) countably additive set function from a σ-field Σ to the space of nonnegative bounded operators on a separable complex Hilbert space . Such functions can be written as M = V*E(·)V in which E is a spectral measure acting on a complex Hilbert space and V is a bounded operator from to such that the only closed linear subspace of , containing the range of V and reducing E (Σ), is itself. Attention is paid to an existing notion of maximality for positive operator-valued measures. The purpose of this paper is to show that M is maximal if and only if E, in the above representation of M, generates a maximal commutative von Neumann algebra.     

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     

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     

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.     

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.     

Measures with Bounded Variation with Respect to a Normed Ideal of Operators and Applications

We introduce in a natural way the notion of measure with bounded variation with respect to a normed ideal of operators and prove that for each maximal normed ideal of operators (, ), is true the following result: If U ∈ L(C(T,X), Y) with G the representing measure of U and G : Σ → ((X, Y),) has bounded variation, then U ∈ (C(T,X), Y). As an application of this result we prove that an injective tensor product of an integral operator with an operator belonging to a maximal normed ideal of operators (,) belongs also to (, ).     

The Medvedev lattice of computably closed sets

Simpson introduced the lattice of Π⁰₁ classes under Medvedev reducibility. Questions regarding completeness in are related to questions about measure and randomness. We present a solution to a question of Simpson about Medvedev degrees of Π⁰₁ classes of positive measure that was independently solved by Simpson and Slaman. We then proceed to discuss connections to constructive logic. In particular we show that the dual of does not allow an implication operator (i.e. that is not a Heyting algebra). We also discuss properties of the class of PA-complete sets that are relevant in this context. Supported by the Austrian Research Fund (Lise Meitner grant M699-N05).