Perfect matchings in random s-uniform hypergraphs

Let E = {X₁, X₂…, X_m} where the X_i ? V for 1 ≤ i ≤ m are distinct. The hypergraph G = (V, E) is said to be s-uniform if |X₁| = s for 1 ≤ i ≤ m. A set of edges M = {X_i : i ? I } is a perfect matching if (i) i ≠ j ? I implies X_i ∩ X_i = 0, and (ii) ∪_i?I X_i = V. In this article we consider the question of whether a random s-uniform hypergraph contains a perfect matching. Let s ≥ 3 be fixed and m/n^4/3 → ∞. We show that an s-uniform hypergraph with m edges chosen uniformly from [74] contains a perfect matching with high probability. This improves an earlier result of Schmidt and Shamir who showed that m/n^3/2 → ∞ suffices. © 1995 John Wiley & Sons, Inc.     

Bounds on absorption times of directionally biased random sequences

A sequence of random variables X₀,X₁, … with values in {0, 1, …, n} representing a general finite-state stochastic process with absorbing state 0 is said to be directionally biased towards 0, if, for all j > 0, ϵ_j: = inf_k>0 {j − E[X_k | X_k−1 = j]} > 0. For such sequences, let t be the expected value of the time to absorption at 0. For a fixed set of biases, the least upper bound for this time can be computed with an algorithm requiring O(n²) steps. Simple upper bounds are described. In particular, t ≤ E[b_x0], where b_i = Σ_j≤i 1/¯ϵ_j and ¯ϵ_j = min_l≥j {ϵ_l}. If all ϵ_j ≤ ϵ_{j + 1} (so ¯ϵ_j = ϵ_j) and ϵ_n < 1, this bound for t is the best possible. For certain finite stochastic processes which we term conditionally independent of X₀ = i, b(i) bounds the expected time given X₀ = i. Similar results are given for lower bounds. The results of this paper were designed to be a useful tool for determining rates of convergence of stochastic optimization algorithms. © 1996 John Wiley & Sons, Inc.     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

Large Sets of Lattices without Order Embeddings

Let I and μ be an infinite index set and a cardinal, respectively, such that |I| ≤ μ and, starting from ?₀, μ can be constructed in countably many steps by passing from a cardinal λ to 2^λ at successor ordinals and forming suprema at limit ordinals. We prove that there exists a system X = {L_i: i ∈ I} of complemented lattices of cardinalities less than |I| such that if i, j ∈ I and φ: L_i → L_j is an order embedding, then i = j and φ is the identity map of L_i. If |I| is countable, then, in addition, X consists of finite lattices of length 10. Stating the main result in other words, we prove that the category of (complemented) lattices with order embeddings has a discrete full subcategory with |I| many objects. Still in other words, the class of these lattices has large antichains (that is, antichains of size |I|) with respect to the quasiorder “embeddability.” As corollaries, we trivially obtain analogous statements for partially ordered sets and semilattices.     

Exact laws for sums of ratios of order statistics from the Pareto distribution

Consider independent and identically distributed random variables {X _nk, 1 ≤ k ≤ m, n ≤ 1} from the Pareto distribution. We select two order statistics from each row, X _n(i) ≤ X _n(j), for 1 ≤ i < j ≤ = m. Then we test to see whether or not Laws of Large Numbers with nonzero limits exist for weighted sums of the random variables R _ij = X _n(j)/X _n(i).     

On the rank of the fibers of elliptic K3 surfaces

Let X be an elliptic K3 surface endowed with two distinct Jacobian elliptic fibrations π _i , i = 1, 2, defined over a number field k. We prove that there is an elliptic curve C ⊂ X such that the generic rank over k of X after a base extension by C is strictly larger than the generic rank of X. Moreover, if the generic rank of π _j is positive then there are infinitely many fibers of π _i (j ≠ i) with rank at least the generic rank of π _i plus one.     

On B(n,k) 2-groups

A finite group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j |1 ≤ i, j ≤ n}| ≤k. In this article, we give characterizations of the B(5, 19) 2-groups, and the B(6, k) 2-groups for 21 ≤ k ≤ 28.     

Limit Theorems for Randomly Selected Ratios of Order Statistics from a Pareto Distribution

Abstract

Consider independent and identically distributed random variables {X _nk , 1 ≤ k ≤ m, n ≥ 1} from the Pareto distribution. We randomly select a pair of order statistics from each row, X _n(i) and X _n(j), where 1 ≤ i < j ≤ m. Then we test to see whether or not Strong and Weak Laws of Large Numbers with nonzero limits for weighted sums of the random variables X _n(j)/X _n(i) exist where we place a prior distribution on the selection of each of these possible pairs of order statistics.     

A weighted geometric regularity from order restricted statistical inference

In Euclideank-space, the cone of vectors x = (x ₁,x ₂,...,x _k ) satisfyingx ₁ ≤x ₂ ≤ ... ≤x _k and $\sum\nolimits_{j = 1}^k {x_j } = 0$ is generated by the vectorsv _j = (j ?k, ...,j ?k,j, ...,j) havingj ?k’s in its firstj coordinates andj’s for the remainingk ?j coordinates, for 1 ≤j <k. In this equal weights case, the average angle between v _i and v _j over all pairs (i, j) with 1 ≤i <j <k is known to be 60°. This paper generalizes the problem by considering arbitrary weights with permutations.     

On Erdos' ten-point problem

Around 1994, Erdoset al. abstracted from their work the following problem: “Given ten pointsA _ij, 1≤i≤j≤5, on a plane and no three of them being collinear, if there are five pointsA _k, 1≤k≤5, on the plane, including points at infinity, with at least two points distinct, such thatA _i, A_j, A_ij are collinear, where 1≤i≤j≤5, is it true that there are only finitely many suchA _k's?” Erdoset al. obtained the result that generally there are at most 49 groups of suchA _k's. In this paper, using Clifford algebra and Wu's method, we obtain the results that generally there are at most 6 such groups ofA _k's.     

Common Principal Components for Dependent Random Vectors

Let the kp-variate random vector X be partitioned into k subvectors X_i of dimension p each, and let the covariance matrix Ψ of X be partitioned analogously into submatrices Ψ_ij. The common principal component (CPC) model for dependent random vectors assumes the existence of an orthogonal p by p matrix β such that β^tΨ_ijβ is diagonal for all (i, j). After a formal definition of the model, normal theory maximum likelihood estimators are obtained. The asymptotic theory for the estimated orthogonal matrix is derived by a new technique of choosing proper subsets of functionally independent parameters.     

On disjointly representable sets

A system of setsE ₁,E ₂, ...,E _k ⊂X is said to be disjointly representable if there existx ₁,x ₂, ...,x _k teX such thatx _i teE _j ⇔i=j. Letf(r, k) denote the maximal size of anr-uniform set-system containing nok disjointly representable members. In the first section the exact value off(r, 3) is determined and (asymptotically sharp) bounds onf(r, k),k>3 are established. The last two sections contain some generalizations, in particular we prove an analogue of Sauer’ theorem [16] for uniform set-systems. Dedicated to Paul Erdős on his seventieth birthday     

Cross-intersecting sub-families of hereditary families

Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if for any i and j in {1,2,…,k} with i≠j, any set in Ai intersects any set in Aj. For a finite set X, let X² denote the power set of X (the family of all subsets of X). A family H is said to be hereditary if all subsets of any set in H are in H; so H is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family H≠{∅} of X² and any k?|X|+1, both the sum and the product of sizes of k cross-intersecting sub-families A₁,A₂,…,Ak (not necessarily distinct or non-empty) of H are maxima if A₁=A₂=?=Ak=S for some largest starSofH (a sub-family of H whose sets have a common element). We prove this for the case when H is compressed with respect to an element x of X, and for this purpose we establish new properties of the usual compression operation. As we will show, for the sum, the condition k?|X|+1 is sharp. However, for the product, we actually conjecture that the configuration A₁=A₂=?=Ak=S is optimal for any hereditary H and any k?2, and we prove this for a special case.     

Tournaments and Vandermond's determinant

We prove that det |x_i^i–1|_{n × n} = Π_1≤i<i≤n (X_j – X_i) by associating a tournament to each term in the expansion of the product. All terms cancel except those corresponding to transitive tournaments, and their sum of the determinant.     

A generalization of perfect graphs—i-perfect graphs

Let i be a positive integer. We generalize the chromatic number _X(G) of G and the clique number o(G) of G as follows: The i-chromatic number of G, denoted by _X(G), is the least number k for which G has a vertex partition V₁, V₂,…, V_k such that the clique number of the subgraph induced by each V_j, 1 ≤ j ≤ k, is at most i. The i-clique number, denoted by o_i(G), is the i-chromatic number of a largest clique in G, which equals [o(G/i]. Clearly _X1(G) = _X(G) and o₁(G) = o(G). An induced subgraph G′ of G is an i-transversal iff o(G′) = i and o(G − G′) = o(G) − i. We generalize the notion of perfect graphs as follows: (1) A graph G is i-perfect iff _Xi(H) = o_i(H) for every induced subgraph H of G. (2) A graph G is perfectly i-transversable iff either o(G) ≤ i or every induced subgraph H of G with o(H) > i contains an i-transversal of H. We study the relationships among i-perfect graphs and perfectly i-transversable graphs. In particular, we show that 1-perfect graphs and perfectly 1-transversable graphs both coincide with perfect graphs, and that perfectly i-transversable graphs form a strict subset of i-perfect graphs for every i ≥ 2. We also show that all planar graphs are i-perfect for every i ≥ 2 and perfectly i-transversable for every i ≥ 3; the latter implies a new proof that planar graphs satisfy the strong perfect graph conjecture. We prove that line graphs of all triangle-free graphs are 2-perfect. Furthermore, we prove for each i greater than or equal to2, that the recognition of i-perfect graphs and the recognition of perfectly i-transversable graphs are intractable and not likely to be in co-NP. We also discuss several issues related to the strong perfect graph conjecture. © 1996 John Wiley & Sons, Inc.     

Path Ramsey numbers in multicolorings

In this paper we consider the general Ramsey number problem for paths when the complete graph is colored with k colors. Specifically, given paths P_i1, P_i2,…, P_ik with i₁, i₂,…, i_k vertices, we determine for certain i_j (1 ≤ j ≤ k) the smallest positive integer n such that a k coloring of the complete graph K_n contains, for some l, a P_il in the lth color. For k = 3, given i₂, i₃, the problem is solved for all but a finite number of values of i₁. The procedure used in the proof uses an improvement of an extremal theorem for paths by P. Erdös and T. Gallai.     

On three-designs of small order

For positive integers t?k?v and λ we define a t-design, denoted B_i[k,λ;v], to be a pair (X,B) where X is a set of points and B is a family, (B_i:i?I), of subsets of X, called blocks, which satisfy the following conditions: (i) |X|=v, the order of the design, (ii) |B_i|=k for each i?I, and (iii) every t-subset of X is contained in precisely λ blocks. The purpose of this paper is to investigate the existence of 3-designs with 3?k?v?32 and λ>0.Wilson has shown that there exists a constant N(t, k, v) such that designs B_t[k,λ;v] exist provided λ>N(t,k,v) and λ satisfies the trivial necessary conditions. We show that N(3,k,v)=0 for most of the cases under consideration and we give a numerical upper bound on N(3, k, v) for all 3?k?v?32. We give explicit constructions for all the designs needed.     

The Grothendieck ring of varieties and piecewise isomorphisms

Let K ₀(Var _k ) be the Grothendieck ring of algebraic varieties over a field k. Let X, Y be two algebraic varieties over k which are piecewise isomorphic (i.e. X and Y admit finite partitions X ₁, ..., X _n , Y ₁, ..., Y _n into locally closed subvarieties such that X _i is isomorphic to Y _i for all i ≤ n), then [X] = [Y] in K ₀(Var _k ). Larsen and Lunts ask whether the converse is true. For characteristic zero and algebraically closed field k, we answer positively this question when dim X ≤ 1 or X is a smooth connected projective surface or if X contains only finitely many rational curves.     

Tychonoff products of compact spaces in ZF and closed ultrafilters

Let {(X_i, T_i): i ∈I } be a family of compact spaces and let X be their Tychonoff product. ??(X) denotes the family of all basic non‐trivial closed subsets of X and ??_R(X) denotes the family of all closed subsets H = V × ΠX_i of X, where V is a non‐trivial closed subset of ΠX_i and Q_H is a finite non‐empty subset of I. We show: (i) Every filterbase ?? ? ??_R(X) extends to a ??_R(X)‐ultrafilter ? if and only if every family H ? ??(X) with the finite intersection property (fip for abbreviation) extends to a maximal ??(X) family F with the fip. (ii) The proposition “if every filterbase ?? ? ??_R(X) extends to a ??_R(X)‐ultrafilter ?, then X is compact” is not provable in ZF. (iii) The statement “for every family {(X_i, T_i): i ∈ I } of compact spaces, every filterbase ?? ? ??_R(Y), Y = Π_{i ∈I}Y_i, extends to a ??_R(Y)‐ultrafilter ?” is equivalent to Tychonoff's compactness theorem. (iv) The statement “for every family {(X_i, T_i): i ∈ ω } of compact spaces, every countable filterbase ?? ? ??_R(X), X = Π_{i ∈ω}X_i, extends to a ??_R(X)‐ultrafilter ?” is equivalent to Tychonoff's compactness theorem restricted to countable families. (v) The countable Axiom of Choice is equivalent to the proposition “for every family {(X_i, T_i): i ∈ ω } of compact topological spaces, every countable family ?? ? ??(X) with the fip extends to a maximal ??(X) family ? with the fip” (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)