On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

The Joint Distribution of Descent and Major Index over Restricted Sets of Permutations

We compute the joint distribution of descent and major index over permutations of {1,..., n} with no descents in positions {n − i, n − i + 1, ... , n − 1} for fixed i ≥ 0. This was motivated by the problem of enumerating symmetrically constrained compositions and generalizes Carlitz’s q-Eulerian polynomial. Received December 19, 2006     

On families of faces in discrete cubes

Let ℱ be a family ofn−k-dimensional faces of the discrete cube {0,1} ⁿ such that for allF ε ℱ, F ⊄ ∪ { F′: F ≠ F′ ∈ ℱ}. It is shown that ifn≥n ₀ (k) then |ℱ| ≤ . This was conjectured by Aharoni and Holzman and is the casem=2 of a more general result on faces of {0,...,m−1}ⁿ.     

Some results on odd factors of graphs

A {1, 3, …,2n ? 1}-factor of a graph G is defined to be a spanning subgraph of G, each degree of whose vertices is one of {1, 3, …, 2n ? 1}, where n is a positive integer. In this paper, we give a sufficient condition for a graph to have a {1, 3, …, 2n ? 1}-factor.     

Quasi-convex Mappings on the Unit Polydisk in $\mathbb{C}^{n}$

In this paper, the sharp estimates of all homogeneous expansions for f are established, where f(z) = (f ₁(z), f ₂(z), …, f _n (z))′ is a k-fold symmetric quasi-convex mapping defined on the unit polydisk in ℂ ⁿ and

Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs

Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 components, unless G belongs to a finite class of exceptional graphs. If δ ≥ 5, then G has a 2-factor with at most (n − 3)/(δ − 1) components, unless G is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace δ − 1 by δ, respectively.     

On Characterizations of Rigid Graphs in the Plane Using Spanning Trees

We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G. A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice.     

Internal geometry of hypersurfaces in projectively metric space

In this paper, we study the internal geometry of a hypersurface V _n−1 embedded in a projectively metric space K _n , n ≥ 3, and equipped with fields of geometric-objects { G_nⁱ,G_i } \left\{ {G_n^i,{G_i}} \right\} and { H_nⁱ,G_i } \left\{ {H_n^i,{G_i}} \right\} in the sense of Norden and with a field of a geometric object { H_nⁱ,H_n } \left\{ {H_n^i,{H_n}} \right\} in the sense of Cartan. For example, we have proved that the projective-connection space P _n−1,n−1 induced by the equipment of the hypersurface V_{n - 1}   ì   K_n,  n 3 3 {V_{n - 1}}\; \subset \;{K_n},\;n \geq 3 , in the sense of Cartan with the field of a geometrical object { H_nⁱ,H_n } \left\{ {H_n^i,{H_n}} \right\} is flat if and only if its normalization by the field of the object { H_nⁱ,G_i } \left\{ {H_n^i,{G_i}} \right\} in the tangent bundle induces a Riemannian space R _n−1 of constant curvature K = −1/c.     

A general Hobby-Rice Theorem and cake cutting

LetX be a Borel subset of a separable Banach spaceE. Letμ be a non-atomic,σ-finite, Borel measure onX. LetG ⊆L ₁ (X, Σ,μ) bem-dimensional. Theorem:There is an l ∈ E* and real numbers −∞=x ₀<x ₁<x ₂<…<x _n<x _n+1=∞with n≤m, such that for all g ∈ G,      

I sottogruppi del gruppo modulare con coefficienti del corpo di Jacobi-Eisenstein e un teorema sui gruppi finiti

Sommario Introduzione — § 1 – 1. L'indice μ(n) dei sottogruppi Г_μ(n) del gruppo Γ di sostituzioni lineari unimodulari con coefficienti del campo diJacobi-Eisenstein — 2. Il poliedro fondamentale del sottogruppo Г_μ(1−ε) — § 2 – 3. I campi fondamentali dei gruppi Г_μ(n) — 4. Impossibilità di limitare con un numero finito di piani e sfere di riflessione i poliedri fondamentali dei gruppi Г_μ(n), conn intero razionale pari, diverso da 2 — § 3 – 5. Relazioni fondamentali fra le sostituzioni generatrici del gruppo di sostituzioni lineari con coefficienti del corpo K_ε con determinante ±1 — § 4 – 6. Sulla indipendenza delle sostituzioniS,T,U, generatrici del gruppo finito G_2μ(n) e sulle loro relazioni caratteristiche nel gruppo G_2μ(n) — § 5 – 7. Dimostrazione del teorema fondamentale sui gruppi G_2μ(n). Lemmi preliminari — 8, Dimostrazione del teorema fondamentale nel caso di moduli primi con 2(1−ε) — § 6 – 9. Il teorema fondamentale per i modulim(1−ε), 3m, 2m, 2m(1−ε), 6m conm primo con 6 – 10. Immagine geometrica dei gruppi G_2μ(1−ε) — § 7 – 11. Il gruppo delle sostituzioni unimodulari , [c/1+4ma]=+1, e il caso eccezionale dei moduli 4m – 12. Il gruppo delle sostituzioni unimodulari [c/1+3m(1−ε)a]₃=+1 e il caso eccezionale dei moduli 3(1−ε)m.     

Maximal partial packings of $${Z_2^n}$$ with perfect codes

A maximal partial Hamming packing of is a family of mutually disjoint translates of Hamming codes of length n, such that any translate of any Hamming code of length n intersects at least one of the translates of Hamming codes in . The number of translates of Hamming codes in is the packing number, and a partial Hamming packing is strictly partial if the family does not constitute a partition of . A simple and useful condition describing when two translates of Hamming codes are disjoint or not disjoint is proved. This condition depends on the dual codes of the corresponding Hamming codes. Partly, by using this condition, it is shown that the packing number p, for any maximal strictly partial Hamming packing of , n = 2 ^m −1, satisfies . It is also proved that for any n equal to 2 ^m −1, , there exist maximal strictly partial Hamming packings of with packing numbers n−10,n−9,n−8,...,n−1. This implies that the upper bound is tight for any n = 2 ^m −1, . All packing numbers for maximal strictly partial Hamming packings of , n = 7 and 15, are found by a computer search. In the case n = 7 the packing number is 5, and in the case n = 15 the possible packing numbers are 5,6,7,...,13 and 14.      

Canonical Representations on Lobachevsky Spaces: An Interaction with an Overalgebra

We define canonical representations R _λ , , for the Lobachevsky space ℒ=G/K of dimension n−1 where G=SO₀(n−1,1), K=SO(n−1), as the restriction to G of maximal degenerate series representations of the overgroup . We determine explicitly the interaction of Lie operators of with operators intertwining canonical representations and representations of G associated with a cone. Supported by the Russian Foundation for Basic Research: grants No. 05-01-00074a and No. 05-01-00001a, the Netherlands Organization for Scientific Research (NWO): grant 047-017-015, the Scientific Program “Devel. Sci. Potent. High. School”: project RNP.2.1.1.351 and Templan No. 1.2.02.     

Homological Connectivity Of Random 2-Complexes

Let Δ_n−1 denote the (n − 1)-dimensional simplex. Let Y be a random 2-dimensional subcomplex of Δ_n−1 obtained by starting with the full 1-dimensional skeleton of Δ_n−1 and then adding each 2−simplex independently with probability p. Let denote the first homology group of Y with mod 2 coefficients. It is shown that for any function ω(n) that tends to infinity

<Emphasis Type="Italic">k</Emphasis>-factors in regular graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.     

Moments of randomly stopped sums-revisited

Conditions are obtained for (*)E|S _T |^γ<∞, γ>2 whereT is a stopping time and {S _n=∑ ₁ ⁿ ,X _j ℱ _n ,n⩾1} is a martingale and these ensure when (**)X _n ,n≥1 are independent, mean zero random variables that (*) holds wheneverET ^γ/2<∞, sup _n≥1 E|X _n |^γ<∞. This, in turn, is applied to obtain conditions for the validity ofE|S _k,T |^γ<∞ and of the second moment equationES _k,T ² =σ ² EΣ _j=k ^T S _k−1,j−1 ² where and {X _n , n≥1} satisfies (**) and ,n≥1. The latter is utilized to elicit information about a moment of a stopping rule. It is also shown for i.i.d. {X _n , n≥1} withEX=0,EX ²=1 that the a.s. limit set of {(n log logn)^−k/2 S _k,n ,n≥k} is [0,2 ^k/2/k!] or [−2 ^k/2/k!] according ask is even or odd and this can readily be reformulated in terms of the corresponding (degenerate kernel)U-statistic .     

On the Fon-Der-Flaass interpretation of extremal examples for Turán’s (3, 4)-problem

Fon-Der-Flaass (1988) presented a general construction that converts an arbitrary [(C)\vec]₄\vec C_4 -free oriented graph Γ into a Turán (3, 4)-graph. He observed that all Turán-Brown-Kostochka examples result from his construction, and proved the lower bound $\tfrac{4} {9} $\tfrac{4} {9} (1 − o(1)) on the edge density of any Turán (3, 4)-graph obtainable in this way. In this paper we establish the optimal bound $\tfrac{3} {7} $\tfrac{3} {7} (1 − o(1)) on the edge density of any Turán (3, 4)-graph resulting from the Fon-Der-Flaass construction under any of the following assumptions on the undirected graph G underlying the oriented graph Γ: (i) G is complete multipartite; (ii) the edge density of G is not less than $\tfrac{2} {3} - \varepsilon $\tfrac{2} {3} - \varepsilon for some absolute constant ε > 0. We are also able to improve Fon-Der-Flaass’s bound to $\tfrac{7} {{16}} $\tfrac{7} {{16}} (1 − o(1)) without any extra assumptions on Γ.     

Construction of <Emphasis Type="Italic">σ</Emphasis>-orthogonal polynomials and gaussian quadrature formulas

Let dα be a measure on R and let σ = (m ₁, m ₂,...,m _n ), where m _k ≥ 1, k = 1,2,...,n, are arbitrary real numbers. A polynomial ω _n (x) := (x − x ₁)(x − x ₂)...(x − x _n ) with x ₁ ≤ x ₂ ≤ ... ≤ x _n is said to be the nth σ-orthogonal polynomial with respect to dα if the vector of zeros (x ₁, x ₂, ..., x _n)^T is a solution of the extremal problem

Asymptotic formulas for the hyperġeometric function2 F 1 of matrix argument,useful in multivariate analysis

Summary LetS _i have the Wishart distributionW _p(∑_i,n_i) fori=1,2. An asymptotic expansion of the distribution of for large n=n₁+n₂ is derived, when∑ ₁∑ ₂ ⁻¹ =I+n^−1/2θ, based on an asymptotic solution of the system of partial differential equations for the hypergeometric function₂ F ₁, obtained recently by Muirhead [2]. Another asymptotic formula is also applied to the distributions of −2 log λ and −log|S ₂(S ₁+S ₂)⁻¹| under fixed∑ ₁∑ ₂ ⁻¹ , which gives the earlier results by Nagao [4]. Some useful asymptotic formulas for₁ F ₁ were investigated by Sugiura [7].     

Classification of linear controlled systems under state and input transformations

The article investigates issues of classification of linear controlled systems under a change of coordinates in their state and input spaces. The classification problem is completely solved for n-dimensional systems with (n − 1)-dimensional inputs; polynomial relative GL_n( \mathbbC ) ×GL_m( \mathbbC ) G{L_n}\left( \mathbb{C} \right) \times G{L_m}\left( \mathbb{C} \right) -invariants on the space of controlled systems are computed.     

Addendum To Schrijver's Work On Minimum Permanents

Let denote the set of n×n binary matrices which have each row and column sum equal to k. For 2≤k≤n→∞ we show that is asymptotically equal to (k−1)^k−1k^2−k. This confirms Conjecture 23 in Minc's catalogue of open problems. * Written while the author was employed by the Department of Computer Science at the Australian National University.