首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
The stable Kneser graph SGn,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K2,SGn,k)?Sk. The dihedral group D2m acts canonically on SGn,k, the group C2 with 2 elements acts on K2. We almost determine the (C2×D2m)-homotopy type of Hom(K2,SGn,k) and use this to prove the following results.The graphs SG2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SGn,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SGn,k,G) is (r−1)-connected and χ(G)<r+k+2.  相似文献   

2.
We present a class of subposets of the partition lattice n with the following property: The order complex is homotopy equivalent to the order complex of n – 1, and the S n -module structure of the homology coincides with a recently discovered lifting of the S n – 1-action on the homology of n – 1. This is the Whitehouse representation on Robinson's space of fully-grown trees, and has also appeared in work of Getzler and Kapranov, Mathieu, Hanlon and Stanley, and Babson et al.One example is the subposet P n n – 1 of the lattice of set partitions n , obtained by removing all elements with a unique nontrivial block. More generally, for 2 k n – 1, let Q n k denote the subposet of the partition lattice n obtained by removing all elements with a unique nontrivial block of size equal to k, and let P n k = i = 2 k Q n i . We show that P n k is Cohen-Macaulay, and that P n k and Q n k are both homotopy equivalent to a wedge of spheres of dimension (n – 4), with Betti number . The posets Q n k are neither shellable nor Cohen-Macaulay. We show that the S n -module structure of the homology generalises the Whitehouse module in a simple way.We also present a short proof of the well-known result that rank-selection in a poset preserves the Cohen-Macaulay property.  相似文献   

3.
A finitely based equational class of idempotent algebras of type <m, n>,m, n≥2, is two-based. More generally, any finitely based equational class of idempotent algebras of type <m 1, ..., mk> withm i≥2 andk≥2 isk-based.  相似文献   

4.
Let Π be a polar space of rank n≥3. Denote by \({\mathcal{G}}_{k}(\varPi)\) the polar Grassmannian formed by singular subspaces of Π whose projective dimension is equal to k. Suppose that k is an integer not greater than n?2 and consider the relation \({\mathfrak{R}}_{i,j}\) , 0≤ijk+1, formed by all pairs \((X,Y)\in{\mathcal{G}}_{k}(\varPi)\times{\mathcal{G}}_{k}(\varPi)\) such that dim p (X Y)=k?i and dim p (XY)=k?j (X consists of all points of Π collinear to every point of X). We show that every bijective transformation of \({\mathcal{G}}_{k}(\varPi)\) preserving \({\mathfrak{R}}_{1,1}\) is induced by an automorphism of Π, except the case where Π is a polar space of type D n with lines containing precisely three points. If k=n?t?1, where t is an integer satisfying n≥2t≥4, we show that every bijective transformation of \({\mathcal{G}}_{k}(\varPi)\) preserving \({\mathfrak{R}}_{0,t}\) is induced by an automorphism of Π.  相似文献   

5.
《Journal of Complexity》1996,12(2):167-174
LetKbe a closed basic set inRngiven by the polynomial inequalities φ1≥ 0, . . . , φm≥ 0 and let Σ be the semiring generated by the φkand the squares inR[x1, . . . ,xn]. Schmüdgen has shown that ifKis compact then any polynomial function strictly positive onKbelongs to Σ. Easy consequences are (1)f≥ 0 onKif and only iffR++ Σ (Positivstellensatz) and (2) iff≥ 0 onKbutf∈ Σ then asdtends to 0+, in any representation off + das an element of Σ in terms of the φk, the squares and semiring operations, the integerN(d) which is the minimum over all representations of the maximum degree of the summands must become arbitrarily large. A one-dimensional example is analyzed to obtain asymptotic lower and upper bounds of the formcd−1/2N(d) ≤Cd−1/2log (1/d).  相似文献   

6.
We show how a simplicial complex arising from the WDVV (Witten-Dijkgraaf-Verlinde-Verlinde) equations of string theory is the Whitehouse complex. Using discrete Morse theory, we give an elementary proof that the Whitehouse complex Δn is homotopy equivalent to a wedge of (n−2)! spheres of dimension n−4. We also verify the Cohen-Macaulay property. Additionally, recurrences are given for the face enumeration of the complex and the Hilbert series of the associated pre-WDVV ring. 2000 Mathematics Subject Classification: Primary—13F55, Secondary—05E99, 55P15  相似文献   

7.
The following results are proved: Let A = (aij) be an n × n complex matrix, n ? 2, and let k be a fixed integer, 1 ? k ? n ? 1.(1) If there exists a monotonic G-function f = (f1,…,fn) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have
Πi∈Sfi(A)<Πi∈S|aii|,
then the rank of A is ? n ? k + 1. (2) If A is irreducible and if there exists a G-function f = (f1,…,fn) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have
Πi∈Sfi(A)<Πi∈S|aii|,
then the rank of A is ? n ? k + 1 if k ? 2, n ? 3; it is ? n ? 1 if k = 1.  相似文献   

8.
With a view toward studying the homotopy type of spaces of Boolean formulae, we introduce a simplicial complex, called the theta complex, associated to any hypergraph, which is the Alexander dual of the more well-known independence complex. In particular, the set of satisfiable formulae in k-conjunctive normal form with ?n variables has the homotopy type of Θ(Cube(n,nk)), where Cube(n,nk) is a hypergraph associated to the (nk)-skeleton of an n-cube. We make partial progress in calculating the homotopy type of theta for these cubical hypergraphs, and we also give calculations and examples for other hypergraphs as well. Indeed studying the theta complex of hypergraphs is an interesting problem in its own right.  相似文献   

9.
Vertex-colorings, edge-colorings and total-colorings of the Sierpiński gasket graphs Sn, the Sierpiński graphs S(n,k), graphs S+(n,k), and graphs S++(n,k) are considered. In particular, χ(Sn), χ(S(n,k)), χ(S+(n,k)), χ(S++(n,k)), χ(S+(n,k)), and χ(S++(n,k)) are determined.  相似文献   

10.
We denote by SG n,k the stable Kneser graph (Schrijver graph) of stable n-subsets of a set of cardinality 2n+k. For k≡3 (mod 4) and n≥2 we show that there is a component of the χ-colouring graph of SG n,k which is invariant under the action of the automorphism group of SG n,k . We derive that there is a graph G with χ(G)=χ(SG n,k ) such that the complex Hom(SG n,k ,G) is non-empty and connected. In particular, for k≡3 (mod 4) and n≥2 the graph SG n,k is not a test graph.  相似文献   

11.
Letk n be the smallest constant such that for anyn-dimensional normed spaceX and any invertible linear operatorTL(X) we have $|\det (T)| \cdot ||T^{ - 1} || \le k_n |||T|^{n - 1} $ . LetA + be the Banach space of all analytic functionsf(z)=Σ k≥0 a kzk on the unit diskD with absolutely convergent Taylor series, and let ‖fA + k≥0κ|; define ? n on $\overline D ^n $ by $ \begin{array}{l} \varphi _n \left( {\lambda _1 ,...,\lambda _n } \right) \\ = inf\left\{ {\left\| f \right\|_{A + } - \left| {f\left( 0 \right)} \right|; f\left( z \right) = g\left( z \right)\prod\limits_{i = 1}^n {\left( {\lambda _1 - z} \right), } g \in A_ + , g\left( 0 \right) = 1 } \right\} \\ \end{array} $ . We show thatk n=sup {? n1,…, λ n ); (λ1,…, λ n )∈ $\overline D ^n $ }. Moreover, ifS is the left shift operator on the space ?∞:S(x 0,x 1, …,x p, …)=(x 1,…,x p,…) and if Jn(S) denotes the set of allS-invariantn-dimensional subspaces of ?∞ on whichS is invertible, we have $k_n = \sup \{ |\det (S|_E )|||(S|_E )^{ - 1} ||E \in J_n (S)\} $ . J. J. Schäffer (1970) proved thatk n≤√en and conjectured thatk n=2, forn≥2. In factk 3>2 and using the preceding results, we show that, up to a logarithmic factor,k n is of the order of √n whenn→+∞.  相似文献   

12.
In this paper, we show that the truncated binomial polynomials defined by \(P_{n,k}(x)={\sum }_{j=0}^{k} {n \choose j} x^{j}\) are irreducible for each k≤6 and every nk+2. Under the same assumption nk+2, we also show that the polynomial P n,k cannot be expressed as a composition P n,k (x) = g(h(x)) with \(g \in \mathbb {Q}[x]\) of degree at least 2 and a quadratic polynomial \(h \in \mathbb {Q}[x]\). Finally, we show that for k≥2 and m,nk+1 the roots of the polynomial P m,k cannot be obtained from the roots of P n,k , where mn, by a linear map.  相似文献   

13.
《Discrete Applied Mathematics》2002,116(1-2):115-126
For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a uv geodesic or vu geodesic in D. For SV(D), I[S] is the union of all closed intervals I[u,v] with u,vS. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽kn−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con+(G) is the maximum such convexity number. It is shown that con+(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.  相似文献   

14.
In the case of a multinomial distribution Π1(1-Π1)+Π2(1-Π2)+…+ Πk(1-Πk) is at times referred to as Gini's index of diversity. In this paper, we present the distributional properties of the statistic
, based on samples of size n for a homogeneous multinomial distribution. For 2≤n≤ 12 and 2≤k≤12, we give a short table of the pdf, cdf, and the moments of D. For large values of n, we mention some results for the asymptotic distribution of D for the general multinomial distribution.  相似文献   

15.
In this paper we study the homotopy type of Hom(Cm,Cn), where Ck is the cyclic graph with k vertices. We enumerate connected components of Hom(Cm,Cn) and show that each such component is either homeomorphic to a point or homotopy equivalent to S1. Moreover, we prove that Hom(Cm,Ln) is either empty or is homotopy equivalent to the union of two points, where Ln is an n-string, i.e., a tree with n vertices and no branching points.  相似文献   

16.
17.
Sharpening (a particular case of) a result of Szemerédi and Vu [4] and extending earlier results of Sárközy [3] and ourselves [2], we find, subject to some technical restrictions, a sharp threshold for the number of integer sets needed for their sumset to contain a block of consecutive integers, whose length is comparable with the lengths of the set summands.A corollary of our main result is as follows. Let k,l≥1 and n≥3 be integers, and suppose that A 1,…,A k ?[0,l] are integer sets of size at least n, none of which is contained in an arithmetic progression with difference greater than 1. If k≥2?(l?1)/(n?2)?, then the sumset A 1+???+A k contains a block of at least k(n?1)+1 consecutive integers.  相似文献   

18.
Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that Hom(K m, Kn) is homotopy equivalent to a wedge of (nm)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ 1 k (Hom(K m, G))≠0, thenχ(G)≥k+m; here ℤ2-action is induced by the swapping of two vertices inK m, and ϖ1 is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.  相似文献   

19.
By [4], a semigroupS is called an (n, m)-commutative semigroup (n, m ∈ ?+, the set of all positive integers) if $$x_1 x_2 \cdot \cdot \cdot x_n y_1 y_2 \cdot \cdot \cdot y_m = y_1 y_2 \cdot \cdot \cdot y_m x_1 x_2 \cdot \cdot \cdot x_n $$ holds for allx 1,...,x n ,y 1,...,y m S It is evident that ifS is an (n, m)-commutative semigroup then it is (n′,m′)-commutative for alln′n andm′m. In this paper, for an arbitrary semigroupS, we determine all pairs (n, m) of positive integersn andm for which the semigroupS is (n, m)-commutative. In our investigation a special type of function mapping ?+ into itself plays an important role. These functions which are defined and discussed here will be called permutation functions.  相似文献   

20.
In a previous work, we defined a family of subcomplexes of the n-dimensional half cube by removing the interiors of all half cube shaped faces of dimension at least k, and we proved that the reduced homology of such a subcomplex is concentrated in degree k−1. This homology module supports a natural action of the Coxeter group W(Dn) of type D. In this paper, we explicitly determine the characters (over C) of these homology representations, which turn out to be multiplicity free. Regarded as representations of the symmetric group Sn by restriction, the homology representations turn out to be direct sums of certain representations induced from parabolic subgroups. The latter representations of Sn agree (over C) with the representations of Sn on the (k−2)-nd homology of the complement of the k-equal real hyperplane arrangement.  相似文献   

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

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