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).     

Extensions of the measurable choice theorem by means of forcing

Using the method of forcing of set theory, we prove the following two theorems on the existence of measurable choice functions: LetT be the closed unit interval [0,1] and letm be the usual Lebesgue measure defined on the Borel subsets ofT. Theorem1. LetS⊂T×T be a Borel set such that for alltεT,S _t ^def={x|(t,x)εS} is countable and non-empty. Then there exists a countable series of Lebesgue-measurable functionsf _n: T→T such thatS _t={f_n(t)|nεω} for alltε[0,1],W _x={y|(x,y)εW} is uncountable. Then there exists a functionh:[0,1]×[0,1]→W with the following properties: (a) for each xε[0,1], the functionh(x,·) is one-one and ontoW _x and is Borel measurable; (b) for eachy, h(·, y) is Lebesgue measurable; (c) the functionh is Lebesgue measurable.     

Independent Trees and Branchings in Planar Multigraphs

 The following statement is proved: Let G be a finite directed or undirected planar multigraph and s be a vertex of G such that for each vertex x≠s of G, there are at least k pairwise openly disjoint paths in G from x to s where k∉{3,4,5} if G is directed. Then there exist k spanning trees T ₁, … ,T _k in G directed towards s if G is directed such that for each vertex x≠s of G, the k paths from x to s in T ₁, … ,T _k are pairwise openly disjoint. – The case where G is directed and k∈{3,4,5} remains open. Received: January 30, 1995 / Revised: October 7, 1996     

Finitary reconstruction of a measure preserving transformation

This paper considers thefinitary reconstruction of an ergodic measure preserving transformationT of a complete separable metric spaceX from a single trajectoryx, Tx, …, or more generally, from a suitable reconstruction sequence x=x ₁,x ₂, … withx _i∈X. Ann-sample reconstruction is a functionT _n: X ⁿ⁺¹ →X; the map (·;x ₁, …,x _n)is treated as an estimate ofT(·) based on then initial elements of x. Given a reference probability measureμ ₀ and constantM>1, functionsT ₁,T ₂, … are defined, and it is shown that for everyμ with 1/M≤dμ/dμ ₀≤M, everyμ-preserving transformationT, and every reconstruction sequence x forT, the estimates (·;x ₁, …,x _nconverge toT in the weak topology. For the family of interval exchange transformations of [0, 1] a simple family of estimates is described and shown to be consistent both pointwise and in the strong topology. However, it is also shown that no finitary estimation scheme is consistent in the strong topology for the family of all ergodic Lebesgue measure preserving transformations of the unit interval, even if x is assumed to be a generic trajectory ofT. Supported in part by NSF Grant DMS-9501926.     

Unique ergodicity of flows on homogeneous spaces

LetG be a unimodular Lie group, Γ a co-compact discrete subgroup ofG and ‘a’ a semisimple element ofG. LetT _a be the mapgΓ →ag Γ:G/Γ →G/Γ. The following statements are pairwise equivalent: (1) (T _a, G/Γ,θ) is weak-mixing. (2) (T _a, G/Γ) is topologically weak-mixing. (3) (G ^u, G/Γ) is uniquely ergodic. (4) (G ^u, G/Γ,θ) is ergodic. (5) (G ^u, G/Γ) is point transitive. (6) (G ^u, G/Γ) is minimal. If in additionG is semisimple with finite center and no compact factors, then the statement “(T _a, G/Γ,θ) is ergodic” may be added to the above list. The authors were partially supported by NSF grant MCS 75-05250.     

A simple map with no prime factors

An ergodic measure-preserving transformationT of a probability space is said to be simple (of order 2) if every ergodic joining λ ofT with itself is eitherμ×μ or an off-diagonal measureμ _S , i.e.,μ _S (A×B)=μ(A∩S ^;−n ;B) for some invertible, measure preservingS commuting withT. Veech proved that ifT is simple thenT is a group extension of any of its non-trivial factors. Here we construct an example of a weakly mixing simpleT which has no prime factors. This is achieved by constructing an action of the countable Abelian group ℤ⊕G, whereG=⊕ _i=1 ^∞ ℤ₂, such that the ℤ-subaction is simple and has centralizer coinciding with the full ℤ⊕G-action.     

Homology of balanced complexes via the Fourier transform

Let G ₀,…,G _k be finite abelian groups, and let G ₀∗⋯∗G _k be the join of the 0-dimensional complexes G _i . We give a characterization of the integral k-coboundaries of subcomplexes of G ₀∗⋯∗G _k in terms of the Fourier transform on the group G ₀×⋯×G _k . This provides a short proof of an extension of a recent result of Musiker and Reiner on a topological interpretation of the cyclotomic polynomial.     

On J. H. C. Whitehead's aspherical question I

A connected, finite two-dimensional CW-complex with fundamental group isomorphic toG is called a [G, 2] _f -complex. LetL⊲G be a normal subgroup ofG. L has weightk if and only ifk is the smallest integer such that there exists {l ₁,…,l _k}⊆L such thatL is the normal closure inG of {l ₁,…,l _k}. We prove that a [G, 2] _f -complexX may be embedded as a subcomplex of an aspherical complexY=X∪{e ₁ ² ,…,e _k ² } if and only ifG has a normal subgroupL of weightk such thatH=G/L is at most two-dimensional and defG=defH+k. Also, ifX is anon-aspherical [G, 2] _f -subcomplex of an aspherical 2-complex, then there exists a non-trivial superperfect normal subgroupP such thatG/P has cohomological dimension ≤2. In this case, any torsion inG must be inP.     

Lightly mixing is closed under countable products

Given any countable familyT ₁,T ₂, … of lightly mixing transformations, we answer a question of Friedman by showing that their direct productT ₁×T ₂×… is lightly mixing. Also, if a transformation has a generating tower of lightly mixing factors then it itself is lightly mixing. Partially supported by NSF grant DMS8501519. Nowadays calledsweeping out.     

Direct products of cyclic semigroups an unions of groups

We consider direct productsS×U_eεE G _e=S ₁×…×S _n × U_eεE G _e of non-group finite cyclic semigroupsS _i, 1 ≤i ≤n, and finite unions of finite groups U_eεE G _e We prove that if such a semigroup is isomorphic to another of the same form, sayT×U _fεF H _f =T ₁×…×U _fεF H _f , whereT _j are non-group cyclic semigroups, 1≤j≤l, and U _fεF H _f is a union of groups, thenS is isomorphic toT and U_eεE G _e is isomorphic to U_fεF H _f . We then determine when a finite semigroup has such a decomposition and show how the direct factors can be found.     

Exterior algebras and two conjectures on finite abelian groups

Let G be a finite abelian group with |G| > 1. Let a ₁, …, a _k be k distinct elements of G and let b ₁, …, b _k be (not necessarily distinct) elements of G, where k is a positive integer smaller than the least prime divisor of |G|. We show that there is a permutation π on {1, …,k} such that a ₁ b _π(1), …, a _k b _π(k) are distinct, provided that any other prime divisor of |G| (if there is any) is greater than k!. This in particular confirms the Dasgupta-Károlyi-Serra-Szegedy conjecture for abelian p-groups. We also pose a new conjecture involving determinants and characters, and show that its validity implies Snevily’s conjecture for abelian groups of odd order. Our methods involve exterior algebras and characters.     

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.     

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.     

The chromatic number of the product of two ℵ1-chromatic graphs can be countable

We prove (in ZFC) that for every infinite cardinal ϰ there are two graphsG ₀,G ₁ with χ(G ₀)=χ(G ₁)=ϰ⁺ and χ(G ₀×G ₁)=ϰ. We also prove a result from the other direction. If χ(G ₀)≧≧ℵ₀ and χ(G ₁)=k<ω, then χ(G ₀×G ₁)=k.     

The Decomposition Dimension of Graphs

 For an ordered k-decomposition ? = {G ₁, G ₂,…,G _k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G ₁), d(e, G ₂),…,d(e, G _k )), where d(e, G _i ) is the distance from e to G _i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K _n ) ≤⌊(2n + 5)/3⌋ for n≥ 3. Received: June 17, 1998 Final version received: August 10, 1999     

Theorems on equalization and monomiality in a relatively free Grassmann algebra

In this paper, we prove theorems on equalization and monomiality, which are essential for developing the structural theory of T-spaces in a relatively free algebra k〈1, x ₁,…, x _i ,…〉/([[x ₁ , x ₂], x ₃]) ^T over an infinite field k of characteristic p > 2. Additionally, some specifics of the case p = 2 are considered.     

On the Cohen–Lusk theorem

Let G be a finite group and X be a G-space. For a map f: X → ℝ ^m , the partial coincidence set A(f, k), k ≤ |G|, is the set of points x ∈ X such that there exist k elements g ₁,…, g _k of the group G, for which f(g ₁ x) = ⋅⋅⋅ = f(g _k x) holds. We prove that the partial coincidence set is nonempty for G = ℤ _p ⁿ under some additional assumptions. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 8, pp. 61–67, 2007.     

Relatively pseudocomplemented semilattices amalgamate strongly

Letk be any finite or infinite cardinal andS _ω the symmetric group of denumerable infinite degree. It is shown that fori<k ifG _i is thei-th row of a matrix whose columns are allk-termed sequences of elements ofS _ω in each of which all but a finite number of terms are equal to the identity ofS _ω thenG _i 's (withG _i ⁻¹ 's defined in an obvious way and with coordinatewise multiplication amongG _i 's andG _i ⁻¹'s) generate the Free Group onk free generatorsG _i . Analogously, Free Abelian and other types of free groups are also constructed. Presented by L. Fuchs.     

Topological realizations of families of ergodic automorphisms, multitowers and orbit equivalence

We study minimal topological realizations of families of ergodic measure preserving automorphisms (e.m.p.a.'s). Our main result is the following theorem. Theorem: Let {T_p:p∈I} be an arbitrary finite or countable collection of e.m.p.a.'s on nonatomic Lebesgue probability spaces (Y _p v _p ). Let S be a Cantor minimal system such that the cardinality of the set ε _S of all ergodic S-invariant Borel probability measures is at least the cardinality of I. Then for any collection {μ _p :pεI} of distinct measures from ε _S there is a Cantor minimal system S′ in the topological orbit equivalence class of S such that, as a measure preserving system, (S ¹,μ _p ) is isomorphic to T_p for every p∈I. Moreover, S′ can be chosen strongly orbit equivalent to S if and only if all finite topological factors of S are measure-theoretic factors of T_p for all p∈I. This result shows, in particular, that there are no restrictions at all for the topological realizations of countable families of e.m.p.a.'s in Cantor minimal systems. Namely, for any finite or countable collection {T ₁,T₂,…} of e.m.p.a.'s of nonatomic Lebesgue probability spaces, there is a Cantor minimal systemS, whose collection {μ1,μ2…} of ergodic Borel probability measures is in one-to-one correspondence with {T ₁,T₂,…}, and such that (S,μ _i ) is isomorphic toT _i for alli. Furthermore, since realizations are taking place within orbit equivalence classes of a given Cantor minimal system, our results generalize the strong orbit realization theorem and the orbit realization theorem of [18]. Those theorems are now special cases of our result where the collections {T _p}, {T _p }{μ _p } consist of just one element each. Research of I.K. was supported by NSF grant DMS 0140068.     

Joint ergodicity and mixing

The study of jointly ergodic measure preserving transformations of probability spaces, begun in [1], is continued, and notions of joint weak and strong mixing are introduced. Various properties of ergodic and mixing transformations are shown to admit analogues for several transformations. The case of endomorphisms of compact abelian groups is particularly emphasized. The main result is that, given such commuting endomorphisms σ₁σ₂,...,σ, ofG, the sequence ((1/N)Σ _n=0 ^N−1 σ ₁ ⁿ f ¹·σ ₂ ⁿ f ²· ··· · σ _s ⁿ f ^sconverges inL ²(G) for everyf ₁,f ₂,…,f _s∈L ^∞(G). If, moreover, the endomorphisms are jointly ergodic, i.e., if the limit of any sequence as above is Π _i=1 ^s ∫ _G f ₁ d μ, where μ is the Haar measure, then the convergence holds also μ-a.e.