4类图完美匹配数目的递推求法

本文研究了4类特殊图完美匹配数目的显式表达式.利用划分,求和,再递推的方法分别给出了图3-n Z4,2-n(2-C6),2-n(2-K4)和3-n(C4-C6)的完美匹配数目的计算公式.     

Expectation of intrinsic volumes of random polytopes

Let K be a convex body in ℝ ^d , let j ∈ {1, …, d−1}, and let K(n) be the convex hull of n points chosen randomly, independently and uniformly from K. If ∂K is C ₊², then an asymptotic formula is known due to M. Reitzner (and due to I. Bárány if ∂K is C ₊³) for the difference of the jth intrinsic volume of K and the expectation of the jth intrinsic volume of K(n). We extend this formula to the case when the only condition on K is that a ball rolls freely inside K. Funded by the Marie-Curie Research Training Network “Phenomena in High-Dimensions” (MRTN-CT-2004-511953).     

Bounds on a generalized domination parameter

Abstract

If n is an integer, n ≥ 2 and u and v are vertices of a graph G, then u and v are said to be K_n-adjacent vertices of G if there is a subgraph of G, isomorphic to K_n , containing u and v. For n ≥ 2, a K_n- dominating set of G is a set D of vertices such that every vertex of G belongs to D or is K_n-adjacent to a vertex of D. The K_n-domination number γK_n (G) of G is the minimum cardinality among the K_n-dominating sets of vertices of G. It is shown that, for n ε {3,4}, if G is a graph of order p with no K_n-isolated vertex, then γK_n (G) ≤ p/n. We establish that this is a best possible upper bound. It is shown that the result is not true for n ≥ 5.     

The Stanley Depth in the Upper Half of the Koszul Complex

Let R = K[X₁, ?c, X_n] be a polynomial ring over some field K. In this article, we prove that the kth syzygy module of the residue class field K of R has Stanley depth n ? 1 for ?n/2? ≤k < n, as it had been conjectured by Bruns et al. in 2010. In particular, this gives the Stanley depth for a whole family of modules whose graded components have dimension greater than 1. So far, the Stanley depth is known only for a few examples of this type. Our proof consists in a close analysis of a matching in the Boolean algebra.     

Existentially complete nilpotent groups

Letn be a positive integer, letK _n denote the theory of groups nilpotent of class at mostn, and letK _n ⁺ denote the theory of torsion-free groups nilpotent of class at mostn. We show that ifn≧2 then neitherK _n norK _n ⁺ has a model companion. ForK _n we obtain the stronger result that the class of finitely generic models is disjoint from the class of infinitely generic models. We also give some other results about existentially complete nilpotent groups. Dedicated to the Memory of Abraham Robinson.     

Smallest maximal snakes of translates of convex domains

LetK be a convex domain. A maximal snake of sizen is a set of non-overlapping translatesK ₁, ...,K _N ofK, whereK _i touchesK _j if and only if |i –j|=1 and no translate ofK can touchK ₁ orK _n without intersecting an additionalK _i ,i=1, ...,n. The size of the smallest maximal snake is proved to be 11 ifK is a parallelogram and to be 10 otherwise.     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998     

Proof of a tiling conjecture of Komlós

A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 ? (1/χ_cr(H)))n, where χ_cr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003     

Kp,q-factorization of complete bipartite graphs

Let K _m,nbe a complete bipartite graph with two partite sets having m and n vertices, respectively. A K _p,q-factorization of K _m,n is a set of edge-disjoint K _p,q-factors of K _m,n which partition the set of edges of K _m,n. When p = 1 and q is a prime number, Wang, in his paper “On K _1,k -factorizations of a complete bipartite graph” (Discrete Math, 1994, 126: 359—364), investigated the K _1,q -factorization of K _m,nand gave a sufficient condition for such a factorization to exist. In the paper “K _1,k -factorizations of complete bipartite graphs” (Discrete Math, 2002, 259: 301—306), Du and Wang extended Wang’s result to the case that q is any positive integer. In this paper, we give a sufficient condition for K _m,n to have a K _p,q-factorization. As a special case, it is shown that the Martin’s BAC conjecture is true when p : q = k : (k+ 1) for any positive integer k.     

Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor

Let n≥2 be an integer. The complete graph K_n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K_n−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph K_{n, n} has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K_{n, n}, then K_{n, n}−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010     

Double coverings of 2‐paths by Hamilton cycles*

A double Dudeney set in K_n is a multiset of Hamilton cycles in K_n having the property that each 2‐path in K_n lies in exactly two of the cycles. A double Dudeney set in K_n has been constructed when n ≥ 4 is even. In this paper, we construct a double Dudeney set in K_n when n ≥ 3 is odd. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 195–206, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ) DOI 10.1002/jcd.10003     

A Class of 2-Colorable Orthogonal Double Covers of Complete Graphs by Hamiltonian Paths

K _n by a graph G is a collection ? of n spanning subgraphs of K _n , all isomorphic to G, such that any two members of ? share exactly one edge and every edge of K _n is contained in exactly two members of ?. In the 1980's Hering posed the problem to decide the existence of an ODC for the case that G is an almost-hamiltonian cycle, i.e. a cycle of length n−1. It is known that the existence of an ODC of K _n by a hamiltonian path implies the existence of ODCs of K _4n and K _16n , respectively, by almost-hamiltonian cycles. Horton and Nonay introduced 2-colorable ODCs and showed: If for n≥3 and a prime power q≥5 there are an ODC of K _n by a hamiltonian path and a 2-colorable ODC of K _q by a hamiltonian path, then there is an ODC of K _qn by a hamiltonian path. We construct 2-colorable ODCs of K _n and K _2n , respectively, by hamiltonian paths for all odd square numbers n≥9. Received: January 27, 2000     

The Basis Number of Some Special Non-Planar Graphs

The basis number of a graph G was defined by Schmeichel to be the least integer h such that G has an h-fold basis for its cycle space. He proved that for m, n 5, the basis number b(K _m,n ) of the complete bipartite graph K _m,n is equal to 4 except for K _6,10, K _5,n and K _6,n with n = 5, 6, 7, 8. We determine the basis number of some particular non-planar graphs such as K _5,n and K _6,n , n = 5, 6, 7, 8, and r-cages for r = 5, 6, 7, 8, and the Robertson graph.     

Cyclotomic units in z p -extensions

LetK ₀ be the maximal real subfield of the field generated by thep-th root of 1 over ℚ, andK∞ be the basic Z_p-extension ofK ₀ for a fixed odd primep. LetK _n be itsn-th layer of this tower. For eachn, we denote the Sylowp-subgroup of the ideal class group ofK _n byA _n , and that ofE _n C _n byB _n , whereE _n (resp.C _n ) is the group of units (resp. cyclotomic units ofK _n . In section 2 of this paper, we describe structures of the direct and inverse limits ofB _n . The direct limit, in particular, is shown to be a direct sum of λ copies ofp-divisible groups and a finite group M, where λ is the Iwasawa λ-invariant for K∞ overK ₀. In section 3, we prove that the capitulation ofA _n inA _m is isomorphic to M form ≫n ≫ 0 by using cohomological arguments. Hence if we assume Greenberg’s conjecture (λ = 0), thenA _n is isomorphic toB _n forn ≫ 0. This paper was supported in part by a research fund for junior scholars, Korea Research Foundation The present studies were supported in part by the Basic Science Research Institute program, Ministry of Education, 1989.     

On a Number-Theoretic Result of Sylvester-Kronecker-Zsigmondy

Let K be an algebraic extension field of Q. Further, let ??_K be the domain of algebraic integers of K, and let Σ_n(x) be the n-th cyclotomic polynomial. This paper is devoted to the factorization of the principal ideal Σ_n(e) ??_K(e??_K) into prime ideals of ??_K. The main result (Theorem 3.4) can be considered as a generalization of a known result of Sylvester, Kronecker and Zsigmondy on the prime factorization of Σ_n(e) (e?Z). With Theorem 3.4., we improve corresponding results of Redei [11] and Sachs [14]. We generalize a technique developed in [8] and [3] and we study also the cases that K is a quadratic field and a cyclotomic field, respectively. Finally, we apply the results to the parameter determination of Fourier-like number-theoretic transforms in ??_K.     

Multicolor bipartite Ramsey number of C4 and large Kn,n

Let br_k(C₄;K_{n, n}) be the smallest N such that if all edges of K_{N, N} are colored by k + 1 colors, then there is a monochromatic C₄ in one of the first k colors or a monochromatic K_{n, n} in the last color. It is shown that br_k(C₄;K_{n, n}) = Θ(n²/log²n) for k?3, and br₂(C₄;K_{n, n})≥c(n n/log²n)² for large n. The main part of the proof is an algorithm to bound the number of large K_{n, n} in quasi‐random graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 47‐54, 2011     

On 4-semiregular 1-factorizations of complete graphs and complete bipartite graphs

A 4-semiregular 1-factorization is a 1-factorization in which every pair of distinct 1-factors forms a union of 4-cycles. LetK be the complete graphK _2nor the complete bipartite graphK _{n, n} .We prove that there is a 4-semiregular 1-factorization ofK if and only ifn is a power of 2 andn2, and 4-semiregular 1-factorizations ofK are isomorphic, and then we determine the symmetry groups. They are known for the case of the complete graphK _2n ,however, we prove them in a different method.     

Some observations on the oberwolfach problem

Some results concerning decompositions of K_n, K_n - F(where F denotes a 1-factor) and complements of a family of special cubic graphs into 2-factors of the same type are given. In particular, if 2d is a divisor of n, it is shown that K_n - F can be decomposed into 2-factors each of whose components is a cycle of length 2d.     

On the number of paths and cycles for almost all graphs and digraphs

In this paper it is deduced the number ofs-paths (s-cycles) havingk edges in common with a fixeds-path (s-cycle) of the complete graphK _n (orK* _n for directed graphs). It is also proved that the number of the common edges of twos-path (s-cycles) randomly chosen from the set ofs-paths (s-cycles) ofK _n (respectivelyK* _n ), are random variables, distributed asymptotically in accordance with the Poisson law whenever s/n exists, thus extending a result by Baróti. Some estimations of the numbers of paths and cycles for almost all graphs and digraphs are made by applying Chebyshev’s inequality.     

Test for properness using residue calculus

We will consider global problems in the ringK[X ₁, …,X _n] on the polynomials with coefficients in a subfieldK ofC. LetP=(P ₁, …,P _n):K ⁿ →K ⁿ be a polynomial map such that (P ₁,…,P _n) is a quasi-regular sequence generating a proper ideal, the main thing we do is to use the algebraic residues theory (as described in [5]) as a computational tool to give some result to test when a map (P ₁, …,P _n) is a proper map by computing a finite number of residue symbols.