Games of Chains and Cutsets in the Boolean Lattice

B. Bajnok and S. Shahriari proved that in 2^[n], the Boolean lattice of order n, the width (the maximum size of an antichain) of a non-trivial cutset (a collection of subsets that meets every maximal chain and does not contain or [n]) is at least n-1. We prove that, for n5, in the Boolean lattice of order n, given -1 disjoint long chains, we can enlarge the collection to a cutset of width n-1. However, there exists a collection of long chains that cannot be so extended.     

Efficient Regular Polygon Dissections

We study the minimum number g(m,n) (respectively, p(m,n)) of pieces needed to dissect a regular m-gon into a regular n-gon of the same area using glass-cuts (respectively, polygonal cuts). First we study regular polygon-square dissections and show that n/2 -2 g(4,n) (n/2) + o(n) and n/4 g(n,4) (n/2) + o(n) hold for sufficiently large n. We also consider polygonal cuts, i.e., the minimum number p(4,n) of pieces needed to dissect a square into a regular n-gon of the same area using polygonal cuts and show that n/4 p(4,n) (n/2) + o(n) holds for sufficiently large n. We also consider regular polygon-polygon dissections and obtain similar bounds for g(m,n) and p(m,n).     

Canonical Ordering Trees and Their Applications in Graph Drawing

We study the properties of Schnyders realizers and canonical ordering trees of plane graphs. Based on these newly discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First, we show that G has a visibility representation with height at most 15n/16 . This improves the previous best bound of (n - 1). Second, we show that every plane graph G has a straight-line grid embedding on an (n - ₀ - 1) × (n - ₀ - 1) grid, where ₀ is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of (n - 1) × (n - 1). We also study the properties of the regular edge labeling of 4-connected plane triangulation. Based on these properties, we show that every such a graph has a canonical ordering tree with at most (n + 1)/2 leaves. This improves the previously known bound of (2n + 1)/3 . We show that every 4-connected plane graph has a visibility representation with height at most 3n/4 . All drawings discussed in this paper can be obtained in linear time.     

k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

A note on the independent domination number of subset graph

The independent domination number i(G) (independent number (G)) is the minimum (maximum) cardinality among all maximal independent sets of G. Haviland (1995) conjectured that any connected regular graph G of order n and degree 1/2n satisfies i(G) 2n/3 1/2. For 1 k l m, the subset graph S _m (k, l) is the bipartite graph whose vertices are the k- and l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for i(S _m (k, l)) and prove that if k + l = m then Havilands conjecture holds for the subset graph S _m (k, l). Furthermore, we give the exact value of (S _m (k, l)).This work was supported by National Natural Sciences Foundation of China (19871036).     

The number of contractible edges in 3-connected graphs

An edge of a 3-connected graph is calledcontractible if its contraction results in a 3-connected graph. Ando, Enomoto and Saito proved that every 3-connected graph of order at least five has |G|/2 or more contractible edges. As another lower bound, we prove that every 3-connected graph, except for six graphs, has at least (2|E(G)| + 12)/7 contractible edges. We also determine the extremal graphs. Almost all of these extremal graphsG have more than |G|/2 contractible edges.     

A note on the illumination of convex bodies

LetKE ^d be a convex body and letl _r(K) denote the minimum number ofr-dimensional affine subspaces ofE ^d lying outsideK with which it is possible to illuminateK, where 0rd–1. We give a new proof of the theorem thatl _r(K)(d+1)/(r+1) with equality for smoothK.The work was supported by Hung. Nat. Found. for Sci . Research No. 326-0213 and 326-0113.     

Construction of Symmetric Balanced Squares with Blocksize More than One

In this paper we study a generalization of symmetric latin squares. A symmetric balanced square of order v, side s and blocksize k is an s×s symmetric array of k-element subsets of {1,2,..., v} such that every element occurs in ks/v or ks/v cells of each row and column. every element occurs in ks²/v or ks ² v cells of the array. Depending on the values s, k and v, the problem naturally divides into three subproblems: (1) vks (2) s < v < ks (3) v s. We completely solve the first problem and we recursively reduce the third problem to the first two. For s 4 we provide direct constructions for the second problem. Moreover, we provide a general construction method for the second problem utilizing flows in a network. We have been able to show the correctness of this construction for k 3. For k4, the problem remains open.     

Random Lazy Random Walks on Arbitrary Finite Groups

This paper considers lazy random walks supported on a random subset of k elements of a finite group G with order n. If k=a log₂ n where a>1 is constant, then most such walks take no more than a multiple of log₂ n steps to get close to uniformly distributed on G. If k=log₂ n+f(n) where f(n) and f(n)/log₂ n0 as n, then most such walks take no more than a multiple of (log₂ n) ln(log₂ n) steps to get close to uniformly distributed. To get these results, this paper extends techniques of Erdös and Rényi and of Pak.     

Subsets with Restricted Movement

Let G be a finite permutation group on a set with no fixed points in and let m and k be integers with 0 < m < k. For a finite subset of the movement of is defined as move() = max_gG| ^g \ |. Suppose further that G is not a 2-group and that p is the least odd prime dividing |G| and move() m for all k-element subsets of . Then either || k + m or k (7m – 5) / 2, || (9m – 3)/2. Moreover when || > k + m, then move() m for every subset of .     

Two vertex-disjoint cycles in a graph

LetG be a graph of ordern 6 with minimum degree at least (n + 1)/2. Then, for any two integerss andt withs 3,t 3 ands + t n, G contains two vertex-disjoint cycles of lengthss andt, respectively, unless thatn, s andt are odd andG is isomorphic toK _{(n–1)/2,(n–1)/2} + K₁. We also show that ifG is a graph of ordern 8 withn even and minimum degree at leastn/2, thenG contains two vertex-disjoint cycles with any given even lengths provided that the sum of the two lengths is at mostn.     

Stationary Gaussian processes with a finite correlation function

If the correlation function vanishes outside the segment [–R, R], then an upper estimate (uniform with respect to all such processes) is possible for the probability of the fact that on an other segment [–r, r] the process remains between – and . Such an estimate is obtained, decreasing for 0 asexp(–f(r/R ln ²+ ) and, moreover,r/R may be either 0 or +. The proof is based on an estimate of the form P_mQ_n c_mn P_m Q_n for norms of polynomials on a circle in the complex plane.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 184, pp. 279–288, 1990.     

On the Continuity of Pathwise Solutions to Langevin Equations in Infinite Dimensions

We fix a rich probability space (,F,P). Let (H,) be a separable Hilbert space and let be the canonical cylindrical Gaussian measure on H. Given any abstract Wiener space (H,B,) over H, and for every Hilbert–Schmidt operator T: HBH which is (|{}|,)-continuous, where |{}| stands for the (Gross-measurable) norm on B, we construct an Ornstein–Uhlenbeck process : (,F,P)×[0,1](B,|{}|) as a pathwise solution of the following infinite-dimensional Langevin equation d _t =db _t +T( _t )dt with the initial data ₀=0, where b is a B-valued Brownian motion based on the abstract Wiener space (H,B,). The richness of the probability space (,F,P) then implies the following consequences: the probability space is independent of the abstract Wiener space (H,B,) (in the sense that (,F,P) does not depend on the choice of the Gross-measurable norm |{}|) and the space C _B consisting of all continuous B-valued functions on [0,1] is identical with the set of all paths of . Finally, we present a way to obtain pathwise continuous solutions :d _t =

Einschließungsaussagen für gewöhnliche Differentialoperatoren

Summary For differential operatorsM of second order (as defined in (1.1)) we describe a method to prove Range-Domain implications—Mu–u and an algorithm to construct these functions , , , . This method has been especially developed for application to non-inverse-positive differential operators. For example, for non-negativea ₂ and for given functions = we require =C ₀[0, 1] C ₂([0, 1]–T) whereT is some finite set), (M) (t)(t), (t[0, 1]–T) and certain additional conditions for eachtT. Such Range-Domain implications can be used to obtain a numerical error estimation for the solution of a boundary value problemMu=r; further, we use them to guarantee the existence of a solution of nonlinear boundary value problems between the bounds- and .     

Some best possible bounds concerning the traces of finite sets II

LetX be ann-element set and be a family of its subsets. Consider the family _x = {F – {x} : F } for a givenx X. We write(m, n) (m – k, n – 1), when for all with || m, there exists an elementx ofX such that| _x| m – k. We show that (m, n) (m – 10,n – 1) for allm 5n and (m, n) (m – 13,n – 1) for allm 29n/5.     

The central limit theorem for Chébli-Trimèche hypergroups

Let (S _nn>-1) be a random walk on a hypergroup ( ₊ , *), i.e., a Markov chain with transition kernelN(x, A) = _x * (A), where is a fixed probability measure on ₊ such that the second moment exists. Then depending on the growth of the hypergroup two situations can occur: when ( ₊ , *) is of exponential growth then it is shown thatS _n is asymptotically normal. In the case of polynomial growth {more precisely, if the densityA of the Haar measure of ( ₊ , *) satisfies lim[A()/A()]=}, the normalized variablesS _n/[n Var()/(+1)]^1/2 converge to a Rayleigh distribution with parameter .     

Slope Estimates of Artin–Schreier Curves

Let X/F_p be an Artin–Schreier curve defined by the affine equation y ^p –y=f(x) where f(x)F_p[x] is monic of degree d. In this paper we develop a method for estimating the first slope of the Newton polygon of X. Denote this first slope by NP₁(X/F_p). We use our method to prove that if p>d2 then NP₁(X/F_p)(p–1)/d/(p–1). If p>2d4, we give a sufficient condition for the equality to hold.     

Regular (2, 2)-systems

Let (E,I) be an independence system over the finite setE = {e ₁, ,e _n }, whose elements are orderede ₁ e _n . (E,I) is called regular, if the independence of {e _l , ,e _{l k} },l ₁ < <l _k , implies that of {e _{m l} , ,e _{m k} }, wherem _l < ··· <m _k andl ₁ m ₁, ,l _k m _k . (E,I) is called a 2-system, if for anyI I,e E I the setI {e } contains at most 2 distinct circuitsC, C I and the number 2 is minimal with respect to this property. If, in addition, for any two independent setsI andJ the family (C J, C C (J, I)), whereC(J, I) denotes {C C:e J I C {e}}, can be partitioned into 2 subfamilies each of which possesses a transversal, then (E,I) is called a (2, 2)-system. In this paper we characterize regular 2-systems and we show that the classes of regular 2-systems resp. regular (2, 2)-systems are identical.     

Some extensions of the Hewitt-Savage zero-one law

Summary Let denote the class of infinite product probability measures = ₁× ₂× defined on an infinite product of replications of a given measurable space (X, A), and let denote the subset of for which (A) =0 or 1 for each permutation invariant event A. Previous works by Hewitt and Savage, Horn and Schach, Blum and Pathak, and Sendler (referenced in the paper) discuss very restrictive sufficient conditions under which a given member , of belongs to . In the present paper, the class is shown to possess several closure properties. E.g., if and _{0 n} for some n 1, then ₀× ₁× ₂×.... While the current results do not permit a complete characterization of they demonstrate conclusively that is a much larger subset of than previous results indicated. The interesting special case X={0,1} is discussed in detail.Research supported by the National Science Foundation under grant No. MCS75-07556     

On Localization of Connective Covers

A result of Neisendorfer says that, for every connected p-complete finite complex Y with ₂Y torsion, the p-completion of P_{K(/p, 1)} (Ym) and Y are of the same homotopy type for any positive integer m. Here, P_{K(/p, 1)}(Ym) is the periodization functor of Bousfield and Ym) is the m-connective cover of the space Y. The proof of this result depends on Millers Theorem of Sullivans conjecture. The aim in this paper is to study the phenomenon without the use of Millers Theorem.AMS Subject Classification (2000): 55P60