首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
A Hamilton cycle in a graph Γ is a cycle passing through every vertex of Γ. A Hamiltonian decomposition of Γ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki’s theorem from the 19th century, showing that a complete graph K n on an odd number of vertices n has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every r-regular n-vertex graph Γ with even degree r = cn for some fixed c > 1/2 has a Hamiltonian decomposition, provided n = n(c) is sufficiently large. In this paper we address the natural question of estimating H(Γ), the number of such decompositions of Γ. Our main result is that H(Γ) = r (1+o(1))nr/2. In particular, the number of Hamiltonian decompositions of K n is \({n^{\left( {1 + o\left( 1 \right)} \right){n^2}/2}}\).  相似文献   

2.
The Ramsey number r(K 3,Q n ) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and Erd?s conjectured that r(K 3,Q n )=2 n+1?1 for every n∈?, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K 3,Q n )?7000·2 n . Here we show that r(K 3,Q n )=(1+o(1))2 n+1 as n→∞.  相似文献   

3.
Let H be a finite abelian group of odd order, D be its generalized dihedral group, i.e., the semidirect product of C2 acting on H by inverting elements, where C2 is the cyclic group of order two. Let Ω (D) be the Burnside ring of D, Δ(D) be the augmentation ideal of Ω (D). Denote by Δn(D) and Qn(D) the nth power of Δ(D) and the nth consecutive quotient group Δn(D)/Δn+1(D), respectively. This paper provides an explicit Z-basis for Δn(D) and determines the isomorphism class of Qn(D) for each positive integer n.  相似文献   

4.
The cube graph Q n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2 n vertices. The Ramsey number r(Q n ;K s ) is the minimum N such that every graph of order N contains the cube graph Q n or an independent set of order s. In 1983, Burr and Erd?s asked whether the simple lower bound r(Q n ;K s )≥(s?1)(2 n ?1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.  相似文献   

5.
In a two-dimensional local field K containing the pth root of unity, a polynomial formal group F c (X, Y) = X + Y + cXY acting on the maximal ideal M of the ring of integers б K and a constructive Hilbert pairing {·, ·} c : K 2(K) × F c (M) → <ξ> c , where <ξ> c is the module of roots of [p] c (pth degree isogeny of F c ) with respect to formal summation are considered. For the extension of two-dimensional local fields L/K, a norm map of Milnor groups Norm: K 2(L) → K 2(K) is considered. Its images are called norms in K 2(L). The main finding of this study is that the norm property of pairing {·, ·}c: {x,β} c : = 0 ? x is a norm in K 2(K([p] c -1 (β))), where [p] c -1 (β) are the roots of the equation [p] c = β, is checked constructively.  相似文献   

6.
In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.  相似文献   

7.
The paper considers cubature formulas for calculating integrals of functions f(X), X = (x 1, …, x n ) which are defined on the n-dimensional unit hypercube K n = [0, 1] n and have integrable mixed derivatives of the kind \(\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)\), 0 ≤ α j ≤ 2. We estimate the errors R[f] = \(\smallint _{K^n } \) f(X)dX ? Σ k = 1 N c k f(X(k)) of cubature formulas (c k > 0) as functions of the weights c k of nodes X(k) and properties of integrable functions. The error is estimated in terms of the integrals of the derivatives of f over r-dimensional faces (rn) of the hypercube K n : |R(f)| ≤ \(\sum _{\alpha _j } \) G j )\(\int_{K^r } {\left| {\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)} \right|} \) dX r , where coefficients G j ) are criteria which depend only on parameters c k and X(k). We present an algorithm to calculate these criteria in the two- and n-dimensional cases. Examples are given. A particular case of the criteria is the discrepancy, and the algorithm proposed is a generalization of those used to compute the discrepancy. The results obtained can be used for optimization of cubature formulas as functions of c k and X(k).  相似文献   

8.
Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K n,n with n colours having all two-coloured cycles of length ≤ 2q 2, for integers n in a set of density 1 ? 3/(q ? 1). One consequence is that L(n, K n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n ? 4.  相似文献   

9.
Let c : SU(n) → PSU(n) = SU(n)/Zn be the quotient map of the special unitary group SU(n) by its center subgroup Z_n. We determine the induced homomorphism c*: H*(PSU(n)) → H*(SU(n)) on cohomologies by computing with the prime orders of binomial coefficients.  相似文献   

10.
Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, vV, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G B (n, d) and generalized Kautz digraphs G K (n, d) are good candidates for interconnection networks. Denote Δ k := (∑ j=0 k d j )?1. F. Tian and J. Xu showed that ?nΔ k ? γ k (G B (n, d)) ≤?n/d k? and ?nΔ k ? ≤ γ k (G K (n, d)) ≤ ?n/d k ?. In this paper, we prove that every generalized de Bruijn digraph G B (n, d) has the distance k-domination number ?nΔ k ? or ?nΔ k ?+1, and the distance k-domination number of every generalized Kautz digraph G K (n, d) bounded above by ?n/(d k?1+d k )?. Additionally, we present various sufficient conditions for γ k (G B (n, d)) = ?nΔ k ? and γ k (G K (n, d)) = ?nΔ k ?.  相似文献   

11.
Studying computable representations of projective planes, for the classes K of pappian, desarguesian, and all projective planes, we prove that K c /? admits no hyperarithmetical Friedberg enumeration and admits a Friedberg Δ0α+3-computable enumeration up to a Δ0 α -computable isomorphism.  相似文献   

12.
Let D be an arbitrary skew field and K a central subfield of D. We prove that D can be embedded in a skew field Δ such that w(Δ)=Δ for every nonempty Lie word w on a set of variables y1,y2,.?.?. with coefficients in K; moreover, we have for the multiplicative group Δ* that v*)=Δ* for every nonempty word \(v=x_{1}^{\varepsilon_{1}}x_{2}^{\varepsilon_{2}}\ldots x_{n}^{\varepsilon_{n}}\) (?i=±1; i=1,2,.?.?.,n).  相似文献   

13.
For a positive integer m, let f(m) be the maximum value t such that any graph with m edges has a bipartite subgraph of size at least t, and let g(m) be the minimum value s such that for any graph G with m edges there exists a bipartition V (G)=V 1?V 2 such that G has at most s edges with both incident vertices in V i . Alon proved that the limsup of \(f\left( m \right) - \left( {m/2 + \sqrt {m/8} } \right)\) tends to infinity as m tends to infinity, establishing a conjecture of Erd?s. Bollobás and Scott proposed the following judicious version of Erd?s' conjecture: the limsup of \(m/4 + \left( {\sqrt {m/32} - g(m)} \right)\) tends to infinity as m tends to infinity. In this paper, we confirm this conjecture. Moreover, we extend this conjecture to k-partitions for all even integers k. On the other hand, we generalize Alon's result to multi-partitions, which should be useful for generalizing the above Bollobás-Scott conjecture to k-partitions for odd integers k.  相似文献   

14.
A general theorem (principle of a priori boundedness) on solvability of the boundary value problem dx = dA(t) · f(t, x), h(x) = 0 is established, where f: [a, b]×R n → R n is a vector-function belonging to the Carathéodory class corresponding to the matrix-function A: [a, b] → R n×n with bounded total variation components, and h: BVs([a, b],R n ) → R n is a continuous operator. Basing on the mentioned principle of a priori boundedness, effective criteria are obtained for the solvability of the system under the condition x(t1(x)) = B(x) · x(t 2(x))+c 0, where t i: BVs([a, b],R n ) → [a, b] (i = 1, 2) and B: BVs([a, b], R n ) → R n are continuous operators, and c 0 ∈ R n .  相似文献   

15.
A k-total coloring of a graph G is a mapping ?: V (G) ? E(G) → {1; 2,..., k} such that no two adjacent or incident elements in V (G) ? E(G) receive the same color. Let f(v) denote the sum of the color on the vertex v and the colors on all edges incident with v: We say that ? is a k-neighbor sum distinguishing total coloring of G if f(u) 6 ≠ f(v) for each edge uvE(G): Denote χ Σ (G) the smallest value k in such a coloring of G: Pil?niak and Wo?niak conjectured that for any simple graph with maximum degree Δ(G), χ Σ ≤ Δ(G)+3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for K 4-minor free graph G with Δ(G) > 5; χ Σ = Δ(G) + 1 if G contains no two adjacent Δ-vertices, otherwise, χ Σ (G) = Δ(G) + 2.  相似文献   

16.
The author has established that if [λn] is a convex sequence such that the series Σn -1λn is convergent and the sequence {K n} satisfies the condition |K n|=O[log(n+1)]k(C, 1),k?0, whereK n denotes the (R, logn, 1) mean of the sequence {n log (n+1)a n}, then the series Σlog(n+1)1-kλn a n is summable |R, logn, 1|. The result obtained for the particular casek=0 generalises a previous result of the author [1].  相似文献   

17.
Any (measurable) function K from Rn to R defines an operator K acting on random variables X by K(X) = K(X1,..., Xn), where the Xj are independent copies of X. The main result of this paper concerns continuous selectors H, continuous functions defined in Rn and such that H(x1, x2,..., xn) ∈ {x1, x2,..., xn}. For each such continuous selector H (except for projections onto a single coordinate) there is a unique point ωH in the interval (0, 1) so that, for any random variable X, the iterates H(N) acting on X converge in distribution as N → ∞ to the ωH-quantile of X.  相似文献   

18.
Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uvE(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that GF if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each GF, G is not Z 3-connected if and only if G is one of K 2,n?2, K 3,n?3, K 2,n?2 + , K 3,n?3 + or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].  相似文献   

19.
It is shown that Leighton’s conjecture about singular points of meromorphic functions represented by C-fractions Kn=1(a n z αn /1) with exponents α1, α2,... tending to infinity, which was proved by Gonchar for a nondecreasing sequence of exponents, holds also for meromorphic functions represented by continued fractions Kn=1(a n A n (z)/1), where A1,A2,... is a sequence of polynomials with limit distribution of zeros whose degrees tend to infinity.  相似文献   

20.
We introduce the notion of property (RD) for a locally compact, Hausdorff and r-discrete groupoid G, and show that the set S 2 l (G) of rapidly decreasing functions on G with respect to a continuous length function l is a dense spectral invariant and Fréchet *-subalgebra of the reduced groupoid C*-algebra C r * (G) of G when G has property (RD) with respect to l, so the K-theories of both algebras are isomorphic under inclusion. Each normalized cocycle c on G, together with an invariant probability measure on the unit space G 0 of G, gives rise to a canonical map τ c on the algebra C c (G) of complex continuous functions with compact support on G. We show that the map τ c can be extended continuously to S 2 l (G) and plays the same role as an n-trace on C r * (G) when G has property (RD) and c is of polynomial growth with respect to l, so the Connes’ fundament paring between the K-theory and the cyclic cohomology gives us the K-theory invariants on C r * (G).  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号