On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

Additive Latin transversals and group rings

LetA={a ₁, …,a _k} and {b ₁, …,b _k} be two subsets of an abelian groupG, k≤|G|. Snevily conjectured that, when |G| is odd, there is a numbering of the elements ofB such thata _i+b _i,1≤i≤k are pairwise distinct. By using a polynomial method, Alon affirmed this conjecture for |G| prime, even whenA is a sequence ofk<|G| elements. With a new application of the polynomial method, Dasgupta, Károlyi, Serra and Szegedy extended Alon’s result to the groupsZ _p ^r andZ _p ^rin the casek<p and verified Snevily’s conjecture for every cyclic group. In this paper, by employing group rings as a tool, we prove that Alon’s result is true for any finite abelianp-group withk<√2p, and verify Snevily’s conjecture for every abelian group of odd order in the casek<√p, wherep is the smallest prime divisor of |G|. This work has been supported partly by NSFC grant number 19971058 and 10271080.     

Simultaneous best approximation by three polynomials

Let [a, b] be any interval and let p₀, p₁, p_k be any three polynomials of degrees 0, 1, k, respectively, where k 2. A set of necessary and sufficient conditions for the existence of an f in C[a, b] such that p_i is the best approximation to f from the space of all polynomials of degree less than or equal to i, for all i = 0, 1, k, is given.     

Disjoint homotopic paths and trees in a planar graph

In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ², a subset {I ₁, …,I _p} of the faces ofG, and pathsC ₁, …,C _k inG, with endpoints on the boundary ofI ₁ ∪ … ∪I _p; find: pairwise disjoint simple pathsP ₁, …,P _k inG so that, for eachi=1, …,k, P _i is homotopic toC _i in the space ℝ²\(I ₁ ∪ … ∪I _p). Moreover, we prove a theorem characterizing the existence of a solution to this problem. Finally, we extend the algorithm to disjoint homotopic trees. As a corollary we derive that, for each fixedp, there exists a polynormial-time algorithm for the problem:given: a planar graphG embedded in ℝ² and pairwise disjoint setsW ₁, …,W _k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT ₁, …,T _k ofG whereT _i (i=1, …, k).     

Greene-Kleitman's theorem for infinite posets

It is proved that if (P) is a poset with no infinite chain and k is a positive integer, then there exist a partition of P into disjoint chains C _i and disjoint antichains A ₁, A ₂, ..., A _k, such that each chain C _i meets min (k, |C _i|) antichains A _j. We make a dual conjecture, for which the case k=1 is: if (P) is a poset with no infinite antichain, then there exist a partition of P into antichains A _i and a chain C meeting all A _i. This conjecture is proved when the maximal size of an antichain in P is 2.     

On the Existence of p-Bases and -Adic p-Bases of a Semi-Local Ring Extension

Let R ^p  ? R′ ? R be a tower of Noetherian semi-local rings of prime characteristic p. When R has locally p-bases over R′ which consist of countably infinite elements, we show the existence of a countably infinite subset {? _i } _i?? of R such that {? _i } _i?? is p-independent over R′, R′[? _i ] _i?? is Noetherian, and R = R′[? _i ] _i?? + ? ^{′ l} R for all l ? ?, where ?′ is the Jacobson radical of R′. Moreover, we consider the existence of p-bases in the case of a tower of semi-local affine k-algebras.     

Transversals of additive Latin squares

LetA={a ₁, …,a _k} andB={b ₁, …,b _k} be two subsets of an Abelian groupG, k≤|G|. Snevily conjectured that, whenG is of odd order, there is a permutationπ ∈S _ksuch that the sums α _i +b _i , 1≤i≤k, are pairwise different. Alon showed that the conjecture is true for groups of prime order, even whenA is a sequence ofk<|G| elements, i.e., by allowing repeated elements inA. In this last sense the result does not hold for other Abelian groups. With a new kind of application of the polynomial method in various finite and infinite fields we extend Alon’s result to the groups (ℤ _p ) ^a and in the casek<p, and verify Snevily’s conjecture for every cyclic group of odd order. Supported by Hungarian research grants OTKA F030822 and T029759. Supported by the Catalan Research Council under grant 1998SGR00119. Partially supported by the Hungarian Research Foundation (OTKA), grant no. T029132.     

Intersection theorems with geometric consequences

In this paper we prove that ifℱ is a family ofk-subsets of ann-set, μ₀, μ₁, ..., μ_s are distinct residues modp (p is a prime) such thatk ≡ μ₀ (modp) and forF ≠ F′ ≠ℱ we have |F ∩F′| ≡ μ_i (modp) for somei, 1 ≦i≦s, then |ℱ|≦( _s ⁿ ). As a consequence we show that ifR ⁿ is covered bym sets withm<(1+o(1)) (1.2) ⁿ then there is one set within which all the distances are realised. It is left open whether the same conclusion holds for compositep.     

Bases normales,unités et conjecture faible de leopoldt

Letk be a number field,p an odd prime,R _k the ring ofp-integers ofk. We use Iwasawa theory to study theZ _p -moduleG(R _k ,Z _p ) (resp.NB (R _k ,Z _p )) ofclasses ofZ _p -extensions (resp.Z _p -extensions having a normal basis overR _k ) ofR _k . The rank ofG(G _k ,Z _p ) (resp.NB(R _k ,Z _p )) is related to Leopoldt's conjecture (resp. weak Leopoldt's conjecture) fork andp.      

Fractional dimension of partial orders

Given a partially ordered setP=(X, ), a collection of linear extensions {L ₁,L ₂,...,L _r } is arealizer if, for every incomparable pair of elementsx andy, we havex<y in someL _i (andy<x in someL _j ). For a positive integerk, we call a multiset {L ₁,L ₂,...,L _t } ak-fold realizer if for every incomparable pairx andy we havex<y in at leastk of theL _i 's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask. We prove various results about the fractional dimension of a poset.Research supported in part by the Office of Naval Research.     

A theorem on arrangements of lines in the plane

LetA be an arrangement ofn lines in the plane. IfR ₁, …,R _r arer distinct regions ofA, andR _i is ap _i-gon (i=1, …,r) then we show that . Further we show that for allr this bound is the best possible ifn is sufficiently large. Financial support for this research was provided by the Carnegie Trust for the Universities of Scotland.     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

Submodule lattice quasivarieties and exact embedding functors for rings with prime power characteristic

Given ringsR with prime power characteristicp ^k , quasivarieties (R) of lattices generated by lattices of submodules ofR-modules are studied. An algebra of expressionsd not dependent onR is developed, such that each suchd uniquely determines a two-sides ideald _R ofR. The main technical result is that (R) (S) makes all implications of the formd _s =S d_R=R true, for any such expressiond. The proof makes use of the known equivalence between (R) (S) and existence of an exact embedding functorR-Mod S -Mod. Fork 2, the ordered setW(p ^k ) of all lattice quasivarieties (R),R having characteristic p _K , is shown to be large and complicated, with ascending and descending chains and antichains having continuously many elements. More precisely,W(p ^k ) has a subset which is order isomorphic to the Boolean algebra of all subsets of a denumerably infinite set. Also, given any prime powerp ^k ,k 2, a ringR can be constructed so that (R) and (R ^op) for the opposite ringR ^op are distinct elements ofW(p ^k ).Presented by R. Freese.Research partially supported by Hungarian National Foundation for Scientific Research grant no. 1903.     

Representation of partially ordered sets

It is well known [1] that any distributive poset (short for partially ordered set) has an isomorphic representation as a poset (Q, (–) such that the supremum and the infimum of any finite setF ofp correspond, respectively, to the union and intersection of the images of the elements ofF. Here necessary and sufficient conditions are given for similar isomorphic representation of a poset where however the supremum and infimum of also infinite subsetsI correspond to the union and intersection of images of elements ofI. Presented by R. Freese.     

Betti numbers of determinantal ideals

Let R=k[x₁,…,x_n] be a polynomial ring and let IR be a graded ideal. In [T. Römer, Betti numbers and shifts in minimal graded free resolutions, arXiv: AC/070119], Römer asked whether under the Cohen–Macaulay assumption the ith Betti number β_i(R/I) can be bounded above by a function of the maximal shifts in the minimal graded free R-resolution of R/I as well as bounded below by a function of the minimal shifts. The goal of this paper is to establish such bounds for graded Cohen–Macaulay algebras k[x₁,…,x_n]/I when I is a standard determinantal ideal of arbitrary codimension. We also discuss other examples as well as when these bounds are sharp.     

Applications of dimension subgroups to the power structure ofp-groups

Dimension subgroups in characteristicp are employed in the study of the power structure of finitep-groups. We show, e.g., that ifG is ap-group of classc (p odd) andk=⌜log _p ((c+1)/(p−1))⌝, then, for alli, any product ofp ^i+k th powers inG is ap ⁱ th power. This sharpens a previous result of A. Mann. Examples are constructed in order to show that our constantk is quite often the best possible, and in any case cannot be reduced by more than 1. Partially supported by MPI funds. This author is a member of GNSAGA-CNR. Partially supported by a Rothschild Fellowship.     

An extremal problem related to probability

Summary We consider a walk from a stateA ₁ to a stateA _n+1 in which the probability of remaining atA _i isp _i , and the probability of progressing fromA _i toA _i+1 is 1 –p _i . The probabilityW _nk of reachingA _n+1 fromA ₁ in exactlyn + k steps can then be expressed as a polynomial of degreen + k in then variablesp ₁,,p _n . We determine the maximum value ofW _nk and the (unique) choice (p ₁,,p _n ) for which this extremum occurs.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.