On the area of the intersection of disks in the plane

Let C₁,…, C_n and C′₁,…, C′_n be two collections of equal disks in the plane, with centers c₁,…, c_n and c′₁,…, c′_n. According to a well-known conjecture of Klee and Wagon (1991), if |c_i − c_j| ≥ |c′_i − c′_j| for all i, j, then Area(∩_i C_i) ≤ Area(∩_i C′_i).

We prove this statement in the special case when there is a continuous contraction of {c₁,…, c_n} onto {c′₁,…, c′_n}.     

Sperner''s theorem with constraints

A set X of subsets of an n-element set S is called an anti-chain if no two elements of X are related by set-wise inclusion. Sperner showed [8] that max |X|=(ⁿ_[n/2]), where |X| denotes the number of elements in X and the maximum is taken over all anti-chains of subsets of S.

Let non-negative integers i_o<n and m_io≠0, m_io+1,…m_n be given. In this paper we give an algorithm for calculating max |X| where the maximum is taken only over anti-chains containing exactly m_i i-element subsets of S for i_o i n.     

Elasticity of factorizations in integral domains

For an atomic integral domain R, define(R)=sup{mn|x₁x_m=y₁y_n, each x_i,y_jεR is irreducible}. We investigate (R), with emphasis for Krull domains R. When R is a Krull domain, we determine lower and upper bounds for (R); in particular,(R)≤max{|Cl(R)| 2, 1}. Moreover, we show that for any real numbers r≥1 or R=∞, there is a Dedekind domain R with torsion class group such that (R)=r.     

An extension theorem for t-designs

In 1994, van Trung (Discrete Math. 128 (1994) 337–348) [9] proved that if, for some positive integers d and h, there exists an S_λ(t,k,v) such that

then there exists an S_λ(v−t+1)(t,k,v+1) having v+1 pairwise disjoint subdesigns S_λ(t,k,v). Moreover, if B_i and B_j are any two blocks belonging to two distinct such subdesigns, then d|B_i∩B_j|<k−h. In 1999, Baudelet and Sebille (J. Combin. Des. 7 (1999) 107–112) proved that if, for some positive integers, there exists an S_λ(t,k,v) such that

where m=min{s,v−k} and n=min{i,t}, then there exists an

having pairwise disjoint subdesigns S_λ(t,k,v). The purpose of this paper is to generalize these two constructions in order to produce a new recursive construction of t-designs and a new extension theorem of t-designs.     

Combinatorial theorems on contractive mappings in power sets

We prove that to every positive integer n there exists a positive integer h such that the following holds: If S is a set of h elements and ƒ a mapping of the power set of S into such that ƒ(T)T for all T , then there exists a strictly increasing sequence T₁T_n of subsets of S such that one of the following three possibilities holds: (a) all sets ƒ(T_i), i= 1,…,n, are equal; (b) for all i=1,…, n, we have ƒ(T_i)=T_i; (c) T_i=ƒ(T_i+1) for all i= 1,…,n-1. This theorem generalizes theorems of the author, Rado, and Leeb. It has applications for subtrees in power sets.     

On certain incomplete statistics

The foundations of the incomplete statistics recently proposed by Wang is rediscussed in the context of the canonical statistical ensemble. It is found that the incomplete normalization condition, ∑p^q_i=1 (i=1,…,w), where p_i is the probability of a given microstate, is not compatible with the entropic non-extensive formula proposed by Tsallis. It is proved that the entropic function proposed by Wang must be written as S_q=−k_B∑p_i^2q−1ln_qp_i, whereas the form proposed by Tsallis namely, S_q=−k_B∑p_i^qln_qp_i, is directly associated with the standard normalization condition (∑_ip_i=1).     

Weight distribution of the bases of a binary matroid

Let M be a weighted binary matroid and w₁ < … < w_m be the increasing sequence of all possible distinct weights of bases of M. We give a sufficient condition for the property that w₁, …, w_m is an arithmetical progression of common difference d. We also give conditions which guarantee that w_i+1 − w_i ≤ d, 1 ≤ i ≤ m −1. Dual forms for these results are given also.     

Every tree is 3-equitable

A labeling of a graph is a function f from the vertex set to some subset of the natural numbers. The image of a vertex is called its label. We assign the label |f(u)−f(v)| to the edge incident with vertices u and v. In a k-equitable labeling the image of f is the set {0,1,2,…,k−1}. We require both the vertex labels and the edge labels to be as equally distributed as possible, i.e., if v_i denotes the number of vertices labeled i and e_i denotes the number of edges labeled i, we require |v_i−v_j|1 and |e_i−e_j|1 for every i,j in {0,1,2,…,k−1}. Equitable graph labelings were introduced by I. Cahit as a generalization for graceful labeling. We prove that every tree is 3-equitable.     

An extended result of Kleitman and Saks concerning binary trees

In a recent paper, D.J. Kleitman and M.E. Saks gave a proof of Huang's conjecture on alphabetic binary trees.

Given a set E = {e_i}, I = 0, 1, 2, …, m and assigned positive weights to its elements and supposing the elements are indexed such that w(e₀) ≤ w(e₁) ≤ … ≤w (e_m), where w(e_i) is the weight of e_i, we call the following sequence E^* a ‘saw-tooth’ sequence

E^*=(e₀,e_m,e₁,…,e_j,e_m−j,…).

Huang's conjecture is: E^* is the most expensive sequence for alphabetic binary trees. This paper shows that this property is true for the L-restricted alphabetic binary trees, where L is the maximum length of the leaves and log₂(m + 1) ≤L≤m.     

Cycle decompositions of crowns

For an integer n3, the crown S_n⁰ is defined to be the graph with vertex set {x₀,x₁,…,x_n−1,y₀,y₁,…,y_n−1} and edge set {x_iy_j: 0i,jn−1, i≠j}. In this paper we give some sufficient conditions for the edge decomposition of the crown into isomorphic cycles.     

MEROMORPHIC FUNCTIONS SHARING TWO FINITE SETS

Let S1 ＝ {∞} and S2 ＝ {w: Ps(w)＝ 0}, Ps(w) being a uniqueness polynomial under some restricted conditions. Then, for any given nonconstant meromorphic function f, there exist at most finitely many nonconstant meromorphic functions g such that f-1(Si) ＝ g-1(Si)(i ＝ 1,2), where f-1(Si) and g-1(Si) denote the pull-backs of Si considered as a divisor, namely, the inverse images of Si counted with multiplicities, by f and g respectively.     

Length-bounded disjoint paths in planar graphs

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r₁,s₁},…,{r_k,s_k} of G adjacent to the unbounded face, positive integers b₁,…,b_k and a function ; find: pairwise vertex-disjoint paths P₁,…,P_k such that for each i=1,…,k, P_i is a r_i−s_i-path and the sum of the l-length of all edges in P_i is at most b_i. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.     

Loopless generation of up–down permutations

An up–down permutation P=(p₁,p₂,…,p_n) is a permutation of the integers 1 to n which satisfies constraints specified by a sequence C=(c₁,c₂,…,c_n−1) of U's and D's of length n−1. If c_i is U then p_i<p_i+1 otherwise p_i−1>p_i. A loopless algorithm is developed for generating all the up–down permutations satisfying any sequence C. Ranking and unranking algorithms are discussed.     

A generalization of carathéodory''s theorem

The following theorem is proved. If the sets and a εⁿ⁺¹_i=1 conv V_i, then there exist elements v_i ε V_i (i=1…,n+1) such that a ε conv{v₁,…,v_n+1}. This is generalization of Carathéodory's theorem. By applying this and similar results some open questions are answered.     

A characterization on n-critical economical generalized tic-tac-toe games

There is a so called generalized tic-tac-toe game playing on a finite set X with winning sets A₁, A₂,…, A_m. Two players, F and S, take in turn a previous untaken vertex of X, with F going first. The one who takes all the vertices of some winning set first wins the game. Erd s and Selfridge proved that if |A₁|=|A₂|==|A_m|=n and m<2ⁿ⁻¹, then the game is a draw. This result is best possible in the sense that once m=2ⁿ⁻¹, then there is a family A₁, A₂,…, A_m so that F can win. In this paper we characterize all those sets A₁,…, A_2n−1 so that F can win in exactly n moves. We also get similar result in the biased games.     

An efficient algorithm for the parametric resource allocation problem

The parametric resource allocation problem asks to minimize the sum of separable single-variable convex functions containing a parameter λ, Σ_{i = 1}ⁿ (ƒ_i(x_i + λg_i(x_i)), under simple constraints Σ_{i = 1}ⁿ x_i = M, l_i≤x_i≤u_i and x_i: nonnegative integers for i = 1, 2, …, n, where M is a given positive integer, and l_i and u_i are given lower and upper bounds on x_i. This paper presents an efficient algorithm for computing the sequence of all optimal solutions when λ is continuously changed from 0 to ∞. The required time is O(G√Mlog² n + n log n + n log(M/n)), where G = Σ_{i = 1}ⁿ u_i − Σ_{i = 1n} l_i and an evaluation of ƒ_i(·) or g_i(·) is assumed to be done in constant time.     

First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.     

All trees are 1-embeddable and all except stars are 2-embeddable

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K_1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e₁, e₂ of edges, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e₁, e₂}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K_1,n−1 are 2-embeddable. In a certain sense, this result is sharp.     

On the Glivenko–Cantelli theorem for generalized empirical processes based on strong mixing sequences

Given \s{X_i, i 1\s} as non-stationary strong mixing (n.s.s.m.) sequence of random variables (r.v.'s) let, for 1 i n and some γ ε [0, 1],

F₁(x)=γP(X_i<x)+(1-γ)P(X_ix)

and

I_i(x)=γI(X_i<x)+(1-γ)I(X_ix)

. For any real sequence \s{C_i\s} satisfying certain conditions, let

.

In this paper an exponential type of bound for P(D_n ), for any >0, and a rate for the almost sure convergence of D_n are obtained under strong mixing. These results generalize those of Singh (1975) for the independent and non-identically distributed sequence of r.v.'s to the case of strong mixing.     

Limiting values of the variance and the moments of the dimension of a sum or intersection of random vector subspaces

Let W be an n-dimensional vector space over a field F; for each positive integer m, let the m-tuples (U₁, …, U_m) of vector subspaces of W be uniformly distributed; and consider the statistics X_m,1 dim_F(∑_i=1^m U_i) and X_m,2 dim_F (∩_i=1^m U_i). If F is finite of cardinality q, we determine lim E(X_m,1^k), and lim E(X_m,2^k), and hence, lim var(X_m,1) and lim var(X_m,2), for any k > 0, where the limits are taken as q → ∞ (for fixed n). Further, we determine whether these, and other related, limits are attained monotonically. Analogous issues are also addressed for the case of infinite F.