An extension of Tutte's 1-factor theorem

We prove the following theorem: Let G be a graph with vertex-set V and ?, g be two integer-valued functions defined on V such that $\text{0}\text{?g(x) ?1??(x)}$ for all x ∈ V. Then G contains a factor F such that $\text{g(x)?d}{}_{\mathrm{F}}\text{(x)??(x)}$ for all x ∈ V if and only if for every subset X of V, $\text{?(X)}$ is at least equal to the number of connected components C of G[V ? X] such that either C = {x} and g(x) = 1, or |C| is odd ?3 and $\text{g(x) = ?(x) =}\text{1}$ for all x ∈ C. Applications are given to certain combinatorial geometries associated with factors of graphs.     

Hyperspaces of compact sets in metric linear spaces

We write 2^x for the hyperspace of all non-empty compact sets in a complete metric linear space X topologized by the Hausdorff metric. Using the notation $\text{F}$(X) = {A ϵ 2^X: A is finite}, l^f₂ = {x} = (x_i) ϵ l₂: x_i = 0 for almost all i}, and l^σ₂ = {x = (x _i) ϵ l₂:σ^∞_i=1 (ix_i)² < ∞}, we have the following theorem:A family $\text{G}$ ⊂$\text{F}$(X) is homeomorphic to l^f₂ if $\text{G}$ is σ-fd-compact, the closure $\text{G}$ of $\text{G}$ in 2^x is not locally compact and if whenever A, B ∈ $\text{G}$, λ ∈ [0, 1] and C ⊂ λA + (1 - λ)B with card C⩽ max{card A, card B} then C ϵ $\text{G}$.Moreover, for any G_δ-AR-set $\text{G}$$\text{G}$ of $\text{G}$ with $\text{G}$$\text{G}$ ⊃ $\text{G}$ we have ($\text{G}$$\text{G}$, $\text{G}$)≅(l₂, l^ƒ₂).Similar conditions for hyperspaces to be homeomorphic to l^σ₂ are also established.     

On the value of a stopped set function process

For certain types of stochastic processes {X_n | n ∈ $\text{N}$}, which are integrable and adapted to a nondecreasing sequence of σ-algebras $\text{F}$_n on a probability space (Ω, $\text{F}$, P), several authors have studied the following problems: IfSdenotes the class of all stopping times for the stochastic basis {$\text{F}$_n | n ∈ $\text{N}$}, when is$\text{sup}{}_{\mathrm{s}}\text{∫}{}_{\mathrm{\Omega }}\text{| X}{}_{\mathrm{\sigma }}\text{| dP}$finite, and when is there a stopping time $\text{σ}$ for which this supremum is attained? In the present paper we set the problem in a measure theoretic framework. This approach turns out to be fruitful since it reveals the root of the problem: It avoids the use of such notions as probability, null set, integral, and even σ-additivity. It thus allows a considerable generalization of known results, simplifies proofs, and opens the door to further research.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

On the analytic continuation of a certain Dirichlet series

A Dirichlet series associated with a positive definite form of degree δ in n variables is defined by

$\text{D}{}_{\mathrm{F}}\text{(s,p,α)}\text{=}\text{∑}\text{α∈Z}{}^{\mathrm{n}}\text{?{0}}\text{F(α)}{}^{\mathrm{?s}}\text{e(ρF(α)+〈α, α〉)}$

where ? ∈ $\text{Q}$, α ∈ $\text{Q}$ⁿ, 〈x, y〉 = x₁y₁ + ? + x_ny_n, e(a) = exp (2πia) for a ∈ $\text{R}$, and s = σ + ti is a complex number. The author proves that: (1) D_F(s, ?, α) has analytic continuation into the whole s-plane, (2) D_F(s, ?, α), ? ≠ 0, is a meromorphic function with at most a simple pole at $\text{s =}\text{n}\text{δ}$. The residue at $\text{s =}\text{n}\text{δ}$ is given explicitly. (3) ? = 0, α ? $\text{Z}$ⁿ, D_F(s, 0, α) is analytic for $\text{α>,}\text{n}\text{(δ ? 1)}$.     

Some results on sperner families

Let F be a Sperner family of subsets of {1,…,m}. Bollobás showed that if $\text{A ∈ F ?}\text{A}\text{= {1,…,m}βA ∈ F}$, and if the parameters of F are p₀,…,p_m then

$\text{∑}\text{i=0}\text{[}\text{m}\text{2}\text{Pi}\text{m?1}\text{i?1}\text{+}\text{∑}\text{i=[}\text{m}\text{2}\text{]+1}\text{m}\text{Pi}\text{m?1}\text{m?i?1}\text{? 2}$

Here we generalize this result and prove some analogues of it. A corollary of Bollobás' result is that $\text{|F| ? 2(}{}_{\mathrm{<mtext>[</mtext><mtext>m</mtext><mtext>2</mtext><mtext>]?1</mtext>}}{}^{\mathrm{m?1}}\text{)}$. Purdy proved that if $\text{A ∈ F ?}\text{A}\text{? F}$ then $\text{|F| ? (}{}_{\mathrm{<mtext>[</mtext><mtext>m</mtext><mtext>2</mtext><mtext>]+1</mtext>}}{}^{\mathrm{m}}\text{)}$, which implies Bollobás' corollary. We also show that Purdy's result may be deduced from Bollobás' by a short argument. Finally, we give a canonical form for Sperner families which are also pairwise intersecting.     

On hypergraphs without two edges intersecting in a given number of vertices

Let X be a finite set of n-melements and suppose t ? 0 is an integer. In 1975, P. Erdös asked for the determination of the maximum number of sets in a family $\text{F}$ = {F₁,…, F_m}, F_i ? X, such that ∥F_i ∩ F_j∥ ≠ t for 1 ? i ≠ j ? m. This problem is solved for n ? n₀(t). Let us mention that the case t = 0 is trivial, the answer being 2^{n ? 1}. For t = 1 the problem was solved in [3]. For the proof a result of independent interest (Theorem 1.5) is used, which exhibits connections between linear algebra and extremal set theory.     

On Maillet determinant

For a positive integer m, let $\text{A = {1 ≤ a <}\text{m}\text{2}\text{| (a, m) = 1}}$ and let n = |A|. For an integer x, let R(x) be the least positive residue of x modulo m and if (x, m) = 1, let x′ be the inverse of x modulo m. If m is odd, then |R(ab′)|_a,b∈A = ?2^1?n(∏_χ(Σ_{a = 1}^{m ? 1}aχ(a))), where χ runs over all the odd Dirichlet characters modulo m.     

A remark on the tail probability of a distribution

Let {X_n}_n≥1 be a sequence of independent and identically distributed random variables. For each integer n ≥ 1 and positive constants r, t, and ?, let S_n = Σ_j=1ⁿX_j and $\text{E{N}{}_{\mathrm{\infty }}\text{(r, t, ?)} = Σ}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{n}{}^{\mathrm{r?2}}\text{P{|S}{}_{\mathrm{n}}\text{| > ?n}{}^{\mathrm{<mtext>r</mtext><mtext>t</mtext>}}\text{}}$. In this paper, we prove that (1) lim_?→0+?^α(r?1)E{N_∞(r, t, ?)} = K(r, t) if E(X₁) = 0, Var(X₁) = 1, and E(| X₁ |^t) < ∞, where 2 ≤ t < 2r ≤ 2t, $\text{K(r, t) =}\text{{2}{}^{\mathrm{<mtext>\alpha (r?1)</mtext><mtext>2</mtext>}}\text{Γ(}\text{(1 + α(r ? 1))}\text{2}\text{)}}\text{{(r ? 1) Γ(}\text{1}\text{2}\text{)}}$, and $\text{α =}\text{2t}\text{(2r ? t)}$; (2) $\text{lim}{}_{\mathrm{?\to 0+}}\text{G(t, ?)}\text{H(t, ?)}\text{= 0}$ if 2 < t < 4, E(X₁) = 0, Var(X₁) > 0, and E(|X₁|^t) < ∞, where G(t, ?) = E{N_∞(t, t, ?)} = Σ_n=1^∞n^t?2P{| S_n | > ?n} → ∞ as ? → 0+ and $\text{H(t, ?) = E{N}{}_{\mathrm{\infty }}\text{(t, t, ?)} = Σ}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{n}{}^{\mathrm{t?2}}\text{P{| S}{}_{\mathrm{n}}\text{| > ?n}{}^{\mathrm{<mtext>2</mtext><mtext>t</mtext>}}\text{} → ∞}\text{as}\text{? → 0+}$, i.e., H(t, ?) goes to infinity much faster than G(t, ?) as ? → 0+ if 2 < t < 4, E(X₁) = 0, Var(X₁) > 0, and E(| X₁ |^t) < ∞. Our results provide us with a much better and deeper understanding of the tail probability of a distribution.     

When is a Pixley-Roy hyperspace CCC?

A space X is said to satisfy condition (C) if for every Y?X with |Y|=ω₁, any family $\text{G}$ of open subsets of Y with |$\text{G}$|=ω₁ has a countable network. It is easy to see that if X satisfies condition (C), then its Pixley-Roy hyperspace $\text{F}$[X] is CCC. We show that under MA_ω1 condition (C) is also necessary for $\text{F}$[X] to be CCC, but under CH it is not.     

Forbidding just one intersection

Following a conjecture of P. Erdös, we show that if $\text{F}$ is a family of k-subsets of and n-set no two of which intersect in exactly l elements then for k ? 2l + 2 and n sufficiently large |$\text{F}$| ? (_{k ? l ? 1}^{n ? l ? 1}) with equality holding if and only if $\text{F}$ consists of all the k-sets containing a fixed (l + 1)-set. In general we show |$\text{F}$| ? d_kn^{max;{;l,k ? l ? 1};}, where d_k is a constant depending only on k. These results are special cases of more general theorems (Theorem 2.1–2.3).     

On a problem of Katona on minimal completely separating systems with restrictions

Let S be a set of n elements, and k a fixed positive integer $\text{<}\text{1}\text{2}\text{n}$. Katona's problem is to determine the smallest integer m for which there exists a family $\text{A}$ = {A₁, …, A_m} of subsets of S with the following property: |_i| ? k (i = 1, …, m), and for any ordered pair x_i, x_i ∈ S (i ≠ j) there is A₁ ∈ $\text{A}$ such that x_i ∈ A₁, x_j ? A₁. It is given in this note that $\text{m = ?}\text{2n}\text{k}\text{?}\text{if}\text{1}\text{2}\text{k}{}^2\text{? 2}$.     

On the stabilizer subgroup of a fair of matrices

Let (F,G) be a pair of matrices defined over an arbitrary field, Fn × n, Gn × m. Consider the natural action of GL_n x GL_m on this pair given by (F,G) ? (gFg^-1,gGh^-1), where (g,h) ∈ GL_n × GL_m. This action is of interest in system theory as well as the representation theory of quivers. In this paper we study the stabilizer subgroup of this action stab(F,G), i.e.

$\text{{(g,h) ∈ GL}{}_{\mathrm{n}}\text{x GL}{}_{\mathrm{m}}\text{|gFg}{}^{-1}\text{= F,gGh}{}^{-1}\text{= G}}$

.     

On intersecting families of finite sets

Let X = [1, n] be a finite set of cardinality n and let $\text{F}$ be a family of k-subsets of X. Suppose that any two members of $\text{F}$ intersect in at least t elements and for some given positive constant c, every element of X is contained in less than c |$\text{F}$| members of $\text{F}$. How large |$\text{F}$| can be and which are the extremal families were problems posed by Erdös, Rothschild, and Szemerédi. In this paper we answer some of these questions for n > n₀(k, c). One of the results is the following: let $\text{t = 1,}\text{3}\text{7}\text{< c <}\text{1}\text{2}$. Then whenever $\text{F}$ is an extremal family we can find a 7-3 Steiner system $\text{B}$ such that $\text{F}$ consists exactly of those k-subsets of X which contain some member of $\text{B}$.     

On projections and limit mappings of inverse systems of compact spaces

A compactificaton αX of a completely regular space X is “determined” by a subset F of C¹(X) if αX is the smallest compactificaton of X to which each element of F extends, and is “generated” by F if the evaluation map $\text{e}{}_{\mathrm{F}}\text{:X →}\text{R}{}^{\mathrm{n}}\text{,n = |F|}$, is an embedding and $\text{αX =}\text{e}{}_{\mathrm{F}}\text{(X)}$. Evidently, if F either determines or generates αX, then every elements of F has an extension to αX; whenever F satisfies this latter condition, the set of all such extensions is denoted F^α.A major results of our previous paper is that F determines αX if and only if F^α separates points of αX ? X. A major result of the present paper is that F generates αX if and only if F^α separates points of αX.     

Cogrowth and amenability of discrete groups

Let G be a group and g₁,…, g_t a set of generators. There are approximately (2t ? 1)ⁿ reduced words in g₁,…, g_t, of length ?n. Let $\text{}\text{?}\text{gg}{}_{\mathrm{n}}$ be the number of those which represent 1_G. We show that $\text{γ =}\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{(}\text{}\text{?}\text{gg}{}_{\mathrm{n}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ exists. Clearly 1 ? γ ? 2t ? 1. $\text{η =}\text{(}\text{log}\text{γ)}\text{(}\text{log}\text{(2t ? 1))}$ is the cogrowth. 0 ? η ? 1. In fact $\text{η ∈ {0} ∪ (}\text{1}\text{2}\text{, 1¦}$. The entropic dimension of G is shown to be 1 ? η. It is then proved that d(G) = 1 if and only if G is free on g₁,…, g_t and d(G) = 0 if and only if G is amenable.     

A note on the similarity depth

In this note we demonstrate the existence of E0L forms F and G which are n-similar, i.e. $\text{L}$ⁿ(F) = $\text{L}$ⁿ(G) but $\text{L}$ⁿ⁺¹(F)≠$\text{L}$ⁿ⁺¹(G) for n ∈ {2, 3}. This partially solves an open problem from [3].     

General theorems on rates of convergence in distribution of random variables I. General limit theorems

Let (X_n)_n?$\text{N}$ be a sequence of real, independent, not necessarily identically distributed random variables (r.v.) with distribution functions F_Xn, and S_n = Σ_i=1ⁿX_i. The authors present limit theorems together with convergence rates for the normalized sums ?(n)S_n, where ?: $\text{N}$ → $\text{R}$⁺, ?(n) → 0, n → ∞, towards appropriate limiting r.v. X, the convergence being taken in the weak (star) sense. Thus higher order estimates are given for the expression ∝_$\text{R}$f(x) d[F_?(n)Sn(x) ? F_X(x)] which depend upon the normalizing function ?, decomposability properties of X and smoothness properties of the function f under consideration. The general theorems of this unified approach subsume O- and o-higher order error estimates based upon assumptions on associated moments. These results are also extended to multi-dimensional random vectors.     

A general theory of surrogate dual and perturbational extended surrogate dual optimization problems

For the optimization problem (P) α = inf h(G), where G ≠ Ø is a subset of a locally convex space $\text{F}\text{and}\text{h: F →}\text{R}\text{?}$, we introduce and study two general concepts of dual problems, encompassing the classical surrogate dual problem. The first one involves only a family of surrogate constraints sets Δ_{G, Φ} ? F (Φ ∈ W), where W ? R^X, X being a locally convex space. The second one uses a perturbation functional $\text{?: F × X →}\text{R}\text{?}$ and a family of sets $\text{}\text{?}\text{gD}{}_{\mathrm{(F,x0),\Phi }}\text{? F × X (Φ ∈ W)}$, where W ? R^X. We give duality theorems, introduce Lagrangians, and show some relations between these problems and the dual problems to (P) defined with the aid of a perturbation and a concept of conjugation of functionals.