Prikry on extenders,revisited

The extender based forcing of Gitik and Magidor is generalized to yield, given any extender j: V å M with critical point κ, a cardinal preserving generic extension with no new bounded subset of κ in which cf(κ) = ω and \(\kappa ^\omega = |j(\kappa )|\).Assuming a superstrong cardinal exists, the forcing notion is used to construct a model in which the added Prikry sequences are a scale in the normal Prikry sequence.In addition, several ways to produce generic filter over an iterated ultrapower are presented.     

Divisibility and structure constraints on automorphism groups of almost perfect 1-factorizations of

Let G be a permutation group acting on a set with N elements such that every permutation with more than m fixed points is the identity. It is easy to verify that |G| divides N(N − 1) ··· (N − m). We show that if gcd(|G|, m!) = 1, then |G| divides (N − i)(N − j) for some i and j satisfying 0 ≤ i < j ≤ m. We use this to show that any almost perfect 1-factorization of K_2n has an automorphism group whose cardinality divides (2n − i)(2n − j) for some i and j with 0 ≤ i < j ≤ 2 as long as n is odd. An almost perfect 1-factorization (or APOF) is a 1-factorization in which the union of any three distinct 1-factors is connected. This result contrasts with an example of an APOF on K₁₂ given by Cameron which has PSL(2, ℤ₁₁) as its automorphism group [with cardinality 12(11)(5)]. When n is even and the automorphism group is solvable, we show that either G acts vertex transitively and n is a power of two, or |G| divides 2n − 2^a for some integer a with 2^a dividing 2n, or else |G| divides (2n − i)(2n − j) for some i and j with 0 ≤ i < j ≤ 2. We also give a number of structure results concerning these automorphism groups. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 355–380, 1998     

A consistency result on cardinal sequences of scattered Boolean spaces

We prove that if GCH holds and τ = 〈κ_α : α < η 〉 is a sequence of infinite cardinals such that κ_α ≥ |η | for each α < η, then there is a cardinal‐preserving partial order that forces the existence of a scattered Boolean space whose cardinal sequence is τ. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

A limit theorem for expectations conditional on a sum

Let ξ₁, ξ₂, ξ₃,... be a sequence of independent random variables, such that μ _j ?E[ξ _j ], 0<α?Var[ξ _j ] andE[|ξ _j ?μ _j |^2+δ] for some δ, 0<δ?1, and everyj?1. IfU and ξ₀ are two random variables such thatE[ξ ₀ ² ]<∞ andE[|U|ξ ₀ ² ]<∞, and the vector 〈U,ξ〉 is independent of the sequence {ξ _j :j?1}, then under appropriate regularity conditions $$E\left[ {U\left| {\xi _0 + S_n } \right. = \sum\limits_{j = 1}^n {\mu _j + c_n } } \right] = E[U] + O\left( {\frac{1}{{s_n^{1 + \delta } }}} \right) + O\left( {\frac{{|c_n |}}{{s_n^2 }}} \right)$$ whereS _n ?ξ₁+ξ₂+?+ξ _n ,μ _j ?E[ξ _j ],s _n ² ?Var[S _n ], andc _n =O(s _n ).     

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.     

On Score Sequences ofk-Hypertournaments

Given two nonnegative integers n and k withn ≥ k > 1, a k -hypertournament on n vertices is a pair (V, A), where V is a set of vertices with | V | = n and A is a set of k -tuples of vertices, called arcs, such that for any k -subset S ofV , A contains exactly one of the k!k -tuples whose entries belong to S. We show that a nondecreasing sequence (r₁, r₂, , r_n) of nonnegative integers is a losing score sequence of a k -hypertournament if and only if for each j(1 ≤ j ≤ n),with equality holding whenj = n. We also show that a nondecreasing sequence (s₁,s₂ , , s_n) of nonnegative integers is a score sequence of somek -hypertournament if and only if for each j(1 ≤ j ≤ n),with equality holding whenj = n. Furthermore, we obtain a necessary and sufficient condition for a score sequence of a strong k -hypertournament. The above results generalize the corresponding theorems on tournaments.     

Finite Groups Whose <Emphasis Type="Italic">n</Emphasis>-Maximal Subgroups Are Modular

Let G be a finite group. If M_n< M_n?1< · · · < M₁< M₀ = G with Mi a maximal subgroup of M_i?1 for all i = 1,..., n, then M_n (n > 0) is an n-maximal subgroup of G. A subgroup M of G is called modular provided that (i) 〈X,M ∩ Z〉 = 〈X,M〉 ∩ Z for all X ≤ G and Z ≤ G such that X ≤ Z, and (ii) 〈M,Y ∩ Z〉 = 〈M,Y 〉 ∩ Z for all Y ≤ G and Z ≤ G such that M ≤ Z. In this paper, we study finite groups whose n-maximal subgroups are modular.     

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.     

On simultaneous reduction of families of matrices to triangular or diagonal form by unitary congruences

Let {A_i }and {B_i } be two given families of n-by-n matrices. We give conditions under which there is a unitary U such that every matrix UA_iU ¹ is upper triangular. We give conditions, weaker than the classical conditions of commutativity of the whole family, under which there is a unitary U such that every matrix UA_jU ^? is upper triangular. We also give conditions under which there is one single unitary U such that every UA_iU ¹ and every UB_jU ^? is upper triangular. We give necessary and sufficient conditions for simultaneous unitary reduction to diagonal form in this way when all the A_j's are complex symmetric and all theB_j 's are Hermitian.     

A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

The scheduling problem 1|pmtn, r _j |w _j U _j calls forn jobs with arbitrary release dates and due dates to be preemptively scheduled for processing by a single machine, with the objective of minimizing the sum of the weights of the late jobs. A dynamic programming algorithm for this problem is described. Time and space bounds for the algorithm are, respectively,O(nk ² W ²) andO(k ² W), wherek is the number of distinct release dates andW is the sum of the integer job weights. Thus, for the problem 1|pmtn, r _j |U _j , in which the objective is simply to minimize the number of late jobs, the pseudopolynomial time bound becomes polynomial, i.e.O(n ³ k ²).     

Lambda-determinants and domino-tilings

Consider the 2n-by-2n matrix with m_i,j=1 for i,j satisfying |2i−2n−1|+|2j−2n−1|2n and m_i,j=0 for all other i,j, consisting of a central diamond of 1's surrounded by 0's. When n4, the λ-determinant of the matrix M (as introduced by Robbins and Rumsey [Adv. Math. 62 (1986) 169–184]) is not well defined. However, if we replace the 0's by t's, we get a matrix whose λ-determinant is well defined and is a polynomial in λ and t. The limit of this polynomial as t→0 is a polynomial in λ whose value at λ=1 is the number of domino-tilings of a 2n-by-2n square.     

Duals of holomorphic Besov spaces on the polydisks and diagonal mappings

Let U ⁿ be the unit polydisk in C ⁿ and S be the space of functions of regular variation. Let 1 ≤ p < ∞, ω = (ω ₁, ..., ω _n ), ω _j ∈ S(1 ≤ j ≤ n) and f ∈ H(U ⁿ ). The function f is said to be in holomorphic Besov space B _p (ω) if

Characterizingω 1 and the long line by their topological elementary reflections

Given a topological space 〈X, T〉 ∈M, an elementary submodel of set theory, we defineX _Mto beX ∩M with the topology generated by {U ∩M : U ∈T ∩M}. We prove that it is undecidable whetherX _Mhomeomorphic toω ₁ impliesX =X _M,yet it is true in ZFC that ifX _Mis homeomorphic to the long line, thenX =X _M.The former result generalizes to other cardinals of uncountable confinality while the latter generalizes to connected, locally compact, locally hereditarily LindelöfT ₂ spaces.     

On Polynomials with Low Peak Signal to Power (L∞ to L2 Norm) Ratios and Theorems of Kashin and Spencer

In many engineering problems such as optical communications, radar and sonar problems, the electronic synthesis of speech, etc., as well as mathematical applications, a problem that arises is that of finding a waveform (trigonometric polynomial) with a specified spectrum, such that its crest factor is minimum, where the crest factor is the ratio of the peak signal energy (L_∞ norm) to the power (L₂ norm) of the waveform. The mathematical formulation of the problem is as follows: Given 1 ≤ m₁ < m₂ < … m_k ≤ n and arbitrary complex numbers a_j j = 1,…, k, we want to find signs ε_j = ±1 such that the growth of the crest factor is minimized as k and n are allowed to become arbitrarily large. Recently B. Kashin has solved special cases of this general problem using some deep geometrical results. We solve the general problem just stated and in particular obtain Kashin's results as a special case. The analogous problem where the ε_j are replaced by α_j and where the α_j are complex numbers with | α_j | = 1 is also solved. The results obtained are best possible in the sense that the asymptotic growth of the crest factors of the polynomials found is optimal. The preceding results are obtained by a solution of the following geometrical problem of independent interest: Given vectors υ₁,…, υ_k in complex n-dimensional space, where k ≤ n, we want to find signs ε_j = ±1 such that the growth of ‖ε₁υ₁ + … + ε_kυ_k‖_∞ is minimized as k and n go to infinity. As a special case of this geometrical result we obtain some combinatorial discrepancy results of J. Spencer.     

Mrówka maximal almost disjoint families for uncountable cardinals

We consider generalizations of a well-known class of spaces, called by S. Mrówka, N∪R, where R is an infinite maximal almost disjoint family (MADF) of countable subsets of the natural numbers N. We denote these generalizations by ψ=ψ(κ,R) for κ?ω. Mrówka proved the interesting theorem that there exists an R such that |βψ(ω,R)?ψ(ω,R)|=1. In other words there is a unique free z-ultrafilter p₀ on the space ψ. We extend this result of Mrówka to uncountable cardinals. We show that for κ?c, Mrówka's MADF R can be used to produce a MADF M⊂ω[κ] such that |βψ(κ,M)?ψ(κ,M)|=1. For κ>c, and every M⊂ω[κ], it is always the case that |βψ(κ,M)?ψ(κ,M)|≠1, yet there exists a special free z-ultrafilter p on ψ(κ,M) retaining some of the properties of p₀. In particular both p and p₀ have a clopen local base in βψ (although βψ(κ,M) need not be zero-dimensional). A result for κ>c, that does not apply to p₀, is that for certain κ>c, p is a P-point in βψ.     

An algorithm to compute <Emphasis Type="Italic">ω</Emphasis>-primality in a numerical monoid

Let M be a commutative, cancellative, atomic monoid and x a nonunit in M. We define ω(x)=n if n is the smallest positive integer with the property that whenever x∣a ₁???a _t , where each a _i is an atom, there is a T?{1,2,…,t} with |T|≤n such that x∣∏_k∈T a _k . The ω-function measures how far x is from being prime in M. In this paper, we give an algorithm for computing ω(x) in any numerical monoid. Simple formulas for ω(x) are given for numerical monoids of the form 〈n,n+1,…,2n?1〉, where n≥3, and 〈n,n+1,…,2n?2〉, where n≥4. The paper then focuses on the special case of 2-generator numerical monoids. We give a formula for computing ω(x) in this case and also necessary and sufficient conditions for determining when x is an atom. Finally, we analyze the asymptotic behavior of ω(x) by computing \(\lim_{x\rightarrow \infty}\frac{\omega(x)}{x}\).     

Solutions to enumeration problems for single-transition serial sequences with an adjacent series height increment bounded above

Sets of n-valued finite serial sequences are investigated. Such a sequence consists of two serial subsequences, beginning with an increasing subsequence and ending in a decreasing one (and vice versa). The structure of these sequences is determined by constraints imposed on the number of series, on series lengths, and on series heights. For sets of sequences the difference between adjacent series heights in which does not exceed a certain given value 1 ≤ |h _j+1 ? h _j | ≤ δ, two algorithms are constructed of which one assigns smaller numbers to lexicographically lower sequences and the other assigns smaller numbers to lexicographically higher sequences.     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998