共查询到20条相似文献,搜索用时 713 毫秒
1.
William T. Trotter 《Discrete Mathematics》1975,12(2):165-172
In this paper we define the n-cube Qn as the poset obtained by taking the cartesian product of n chains each consisting of two points. For a finite poset X, we then define dim2X as the smallest positive integer n such that X can be embedded as a subposet of Qn. For any poset X we then have log2 |X| ? dim2X ? |X|. For the distributive lattice , dim2L = |X| and for the crown Skn, dim2 (Skn) = n + k. For each k ? 2, there exist positive constants c1 and c2 so that for the poset X consisting of all one element and k-element subsets of an n-element set, the inequality c1 log2n < dim2(X) < c2 log2n holds for all n with k < n. A poset is called Q-critical if dim2 (X ? x) < dim2(X) for every x ? X. We define a join operation ⊕ on posets under which the collection Q of all Q-critical posets which are not chains forms a semigroup in which unique factorization holds. We then completely determine the subcollection ? Q consisting of all posets X for which dim2 (X) = |X|. 相似文献
2.
Dushnik and Miller defined the dimensions of a partially ordered set X,denoted dim X, as the smallest positive integer t for which there exist t linear extensions of X whose intersection is the partial ordering on X. Hiraguchi proved that if n ≥2 and |X| ≤2n+1, then dim X ≤ n. Bogart, Trotter and Kimble have given a forbidden subposet characterization of Hiraguchi's inequality by determining for each n ≥ 2, the minimum collection of posets ?n such that if |X| ?2n+1, the dim X < n unless X contains one of the posets from ?n. Although |?3|=24, for each n ≥ 4, ?n contains only the crown S0n — the poset consisting of all 1 element and n ? 1 element subsets of an n element set ordered by inclusion. In this paper, we consider a variant of dimension, called interval dimension, and prove a forbidden subposet characterization of Hiraguchi's inequality for interval dimension: If n ≥2 and |X 2n+1, the interval dimension of X is less than n unless X contains S0n. 相似文献
3.
Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K2 or to K2,l with l odd. 相似文献
4.
Let c(G) denote the number of components in a graph G. It is shown that if G has genus γ and isk-connected with k ? 3, then c(G ? X) ? (2/(k ? 2))(| X | ? 2 + 2γ), for all X? V(G) with | X | ? k. Some implications of this result for planar graphs (y = 0) and toroidal graphs (y = 1) are considered. 相似文献
5.
Yolandé Jacobs Elizabeth Jonck Ernst J. Joubert 《Central European Journal of Mathematics》2013,11(7):1344-1357
Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ? V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k } of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9 ≤ χρ(C 4 □ C q ). We will also show that if t is a multiple of four, then χρ(C 4 □ C q ) = 9. 相似文献
6.
7.
Let X be a set of k×k matrices in which each element is nonnegative. For a positive integer n, let P(n) be an arbitrary product of n matrices from X, with any ordering and with repetitions permitted. Define X to be a primitive set if there is a positive integer n such that every P(n) is positive [i.e., every element of every P(n) is positive]. For any primitive set X of matrices, define the index g(X) to be the least positive n such that every P(n) is positive. We show that if X is a primitive set, then g(X)?2k?2. Moreover, there exists a primitive set Y such that g(Y) = 2k?2. 相似文献
8.
For a positive integer k, let k?+?k denote the poset consisting of two disjoint k-element chains, with all points of one chain incomparable with all points of the other. Bosek, Krawczyk and Szczypka showed that for each k?≥?1, there exists a constant c k so that First Fit will use at most $c_kw^2$ chains in partitioning a poset P of width at most w, provided the poset excludes k?+?k as a subposet. This result played a key role in the recent proof by Bosek and Krawczyk that O(w 16logw ) chains are sufficient to partition on-line a poset of width w into chains. This result was the first improvement in Kierstead’s exponential bound: (5 w ???1)/4 in nearly 30 years. Subsequently, Joret and Milans improved the Bosek–Krawczyk–Szczypka bound for the performance of First Fit to 8(k???1)2 w, which in turn yields the modest improvement to O(w 14logw ) for the general on-line chain partitioning result. In this paper, we show that this class of posets admits a notion of on-line dimension. Specifically, we show that when k and w are positive integers, there exists an integer t?=?t(k,w) and an on-line algorithm that will construct an on-line realizer of size t for any poset P having width at most w, provided that the poset excludes k?+?k as a subposet. 相似文献
9.
For positive integers t?k?v and λ we define a t-design, denoted Bi[k,λ;v], to be a pair (X,B) where X is a set of points and B is a family, (Bi:i?I), of subsets of X, called blocks, which satisfy the following conditions: (i) |X|=v, the order of the design, (ii) |Bi|=k for each i?I, and (iii) every t-subset of X is contained in precisely λ blocks. The purpose of this paper is to investigate the existence of 3-designs with 3?k?v?32 and λ>0.Wilson has shown that there exists a constant N(t, k, v) such that designs Bt[k,λ;v] exist provided λ>N(t,k,v) and λ satisfies the trivial necessary conditions. We show that N(3,k,v)=0 for most of the cases under consideration and we give a numerical upper bound on N(3, k, v) for all 3?k?v?32. We give explicit constructions for all the designs needed. 相似文献
10.
David Slepian 《Stochastic Processes and their Applications》1983,14(3):249-265
Let X(t) be the ergodic Gauss–Markov process with mean zero and covariance function e?|τ|. Let D(t) be +1, 0 or ?1 according as X(t) is positive, zero or negative. We determine the non-linear estimator of X(t1) based solely on D(t), ?T ? t ? 0, that has minimal mean–squared error ε2(t1, T). We present formulae for ε2(t1, T) and compare it numerically for a range of values of t1 and T with the best linear estimator of X(t1) based on the same data. 相似文献
11.
D de Caen 《Journal of Combinatorial Theory, Series B》1983,34(3):340-349
The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let Xs(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(Xl), given that min(Xl) ≥ 1. The following lower bound on the variance of Xs is proved: , where m = |E(H)| and . This implies the following: putting t(k, l) = limn→∞T(n, l, k)(kn)?1 then t(k, l) ≥ T(s, l, k)((ks) ? 1)?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned. 相似文献
12.
Yong Hu 《Mathematische Annalen》2010,348(2):357-377
Let K = k(C) be the function field of a curve over a field k and let X be a smooth, projective, separably rationally connected K-variety with ${X(K)\neq\emptyset}Let K = k(C) be the function field of a curve over a field k and let X be a smooth, projective, separably rationally connected K-variety with X(K) 1 ?{X(K)\neq\emptyset}. Under the assumption that X admits a smooth projective model p: X? C{\pi: \mathcal{X}\to C}, we prove the following weak approximation results: (1) if k is a large field, then X(K) is Zariski dense; (2) if k is an infinite algebraic extension of a finite field, then X satisfies weak approximation at places of good reduction; (3) if k is a nonarchimedean local field and R-equivalence is trivial on one of the fibers Xp{\mathcal{X}_p} over points of good reduction, then there is a Zariski dense subset W í C(k){W\subseteq C(k)} such that X satisfies weak approximation at places in W. As applications of the methods, we also obtain the following results over a finite field k: (4) if |k| > 10, then for a smooth cubic hypersurface X/K, the specialization map X(K)? ?p ? PXp(k(p)){X(K)\longrightarrow \prod_{p\in P}\mathcal{X}_p(\kappa(p))} at finitely many points of good reduction is surjective; (5) if char k 1 2, 3{\mathrm{char}\,k\neq 2,\,3} and |k| > 47, then a smooth cubic surface X over K satisfies weak approximation at any given place of good reduction. 相似文献
13.
Samuel M Rankin 《Journal of Mathematical Analysis and Applications》1982,88(2):531-542
Existence and asymptotic behavior of solutions are given for the equation u′(t) = ?A(t)u(t) + F(t,ut) (t ? 0) and u0 = ? ? C([?r,0]; X) C. The space X is a Banach space; the family of unbounded linear operators defined on D(A) ? X → X generates a linear evolution system and F: C → X is continuous with respect to a fractional power of A(t0) for some t0 ? [0, T]. 相似文献
14.
A pair (X, ) will be a t-wise balanced design (tBD) of type t?(v, K, λ) if is a family of subsets of X, called blocks, such that: (i) , where is the set of positive integers; (ii) , for every i ? I; and (iii) if T ? X, |T| = t, then there are λ ? indices i ? I where T ? Bi. Throughout this paper we make three restrictions on our tBD's: (1) there are no repeated blocks, i.e. will be a set of subsets of X; (2) t ? K or there are no blocks of size t; and (3) or does not contain all k-subsets of X for any t<k?v. Note then that X ? . Also, if we give the parameters of a specific tBD, then we will choose a minimal K.We focus on the designs with the symmetric group Sp as automorphism group, i.e. X will be the set of labelled edges of the undirected complete graph Kp and if B ? then all subgraphs of Kp isomorphic to B are also in . Call such tBD's ‘graphical tBD's’. We determine all graphical tBD's with λ = 1 or 2 which will include one with parameters 4?(15,{5,7},1). 相似文献
15.
Erich Prisner 《Graphs and Combinatorics》1993,9(2-4):335-352
For any integerk e 1 thek- path graph Pk (G) of a graph G has all length-k subpaths ofG as vertices, and two such vertices are adjacent whenever their union (as subgraphs ofG) forms a path or cycle withk + 1 edges. Fork = 1 we get the well-known line graphP 1 (G) =L(G). Iteratedk-path graphs Pt k(G) are defined as usual by Pt k (G) := Pk(P t?1 k(G)) ift < 1, and by P1 k(G): = Pk(G). A graph G isP k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP k -converges if some iteratedk-path graph of G isP k -periodic. A graph has infiniteP k -depth if for any positive integert there is a graphH such that Pt k(H) ?G. In this paperP k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP k -converges if some iteratedk-path graph of G isP k -periodic graphs,P k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP k -converges if some iteratedk-path graph of G isP k -convergent graphs, and graphs with infiniteP k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP k -converges if some iteratedk-path graph of G isP k -depth are characterized inside some subclasses of the class of locally finite graphs fork = 1, 2. 相似文献
16.
Ramiro de la Vega 《Topology and its Applications》2006,153(12):2118-2123
We show (in ZFC) that if X is a compact homogeneous Hausdorff space then |X|?2t(X), where t(X) denotes the tightness of X. It follows that under GCH the character and the tightness of such a space coincide. 相似文献
17.
18.
Yu. V. Martsynyuk 《Mathematical Methods of Statistics》2016,25(3):219-232
Let X 1,..., X n, n > 1, be nondegenerate independent chronologically ordered realvalued observables with finite means. Consider the “no-change in the mean” null hypothesis H 0: X 1,..., X n is a randomsample on X with Var X <∞. We revisit the problem of nonparametric testing for H 0 versus the “at most one change (AMOC) in the mean” alternative hypothesis H A: there is an integer k*, 1 ≤ k* < n, such that EX 1 = · · · = EXk* ≠ EXk*+1 = ··· = EX n. A natural way of testing for H 0 versus H A is via comparing the sample mean of the first k observables to the sample mean of the last n - k observables, for all possible times k of AMOC in the mean, 1 ≤ k < n. In particular, a number of such tests in the literature are based on test statistics that are maximums in k of the appropriately individually normalized absolute deviations Δk = |S k/k - (S n - S k)/(n - k)|, where S k:= X 1 + ··· + X k. Asymptotic distributions of these test statistics under H 0 as n → ∞ are obtained via establishing convergence in distribution of supfunctionals of respectively weighted |Z n(t)|, where {Z n(t), 0 ≤ t ≤ 1}n≥1 are the tied-down partial sums processes such that if 0 ≤ t < 1, and Z n(t):= 0 if t = 1. In the present paper, we propose an alternative route to nonparametric testing for H 0 versus H A via sup-functionals of appropriately weighted |Z n(t)|. Simply considering max1?k<n Δk as a prototype test statistic leads us to establishing convergence in distribution of special sup-functionals of |Z n(t)|/(t(1 - t)) under H 0 and assuming also that E|X|r < ∞ for some r > 2. We believe the weight function t(1 - t) for sup-functionals of |Z n(t)| has not been considered before.
相似文献
$${Z_n}\left( t \right): = \left( {{S_{\left\lceil {\left( {n + 1} \right)t} \right\rceil }} - \left[ {\left( {n + 1} \right)t} \right]{S_n}/n} \right)/\sqrt n $$
19.
Let k1 ? k2 ? … ? kn be given positive integers and let F denote the set of vectors (l1, …, ln) with integer components satisfying 0 ? li ? ki, i = 1, 2, …, n. If H is a subset of F, let (l)H denote the subset of H consisting of those vectors with component sum l, and let C((l)H) denote the smallest [(l)H] elements of (l)F. The generalized Macaulay theorem due to the author and B. Lindström [3] shows that |Gamma;((C)(l)(H)|, ? |Γ(C((l)H))|, where Γ((l)H) is the setof vectors in F obtainable by subtracting l from a single component of a vector in (l)H. A method is given for computing [Γ(C((l)H)] in this paper. It is analogous to the method for computing |Γ(C(l)H))| in the k1 = … = kn = 1 case which has been given independently by Katona [4] and Kruskal [5]. 相似文献
20.
Michel Las Vergnas 《Discrete Mathematics》1976,15(1):27-39
The main result of this paper is the following theorem: Let G = (X,E) be a digraph without loops or multiple edges, |X| ?3, and h be an integer ?1, if G contains a spanning arborescence and if d+G(x)+d?G(x)+d?G(y)+d?G(y)? 2|X |?2h?1 for all x, y?X, x ≠ y, non adjacent in G, then G contains a spanning arborescence with ?h terminal vertices. A strengthening of Gallai-Milgram's theorem is also proved. 相似文献