共查询到20条相似文献,搜索用时 15 毫秒
1.
Jakob Jonsson 《Journal of Combinatorial Theory, Series A》2005,112(1):117-142
For n?3, let Ωn be the set of line segments between vertices in a convex n-gon. For j?1, a j-crossing is a set of j distinct and mutually intersecting line segments from Ωn such that all 2j endpoints are distinct. For k?1, let Δn,k be the simplicial complex of subsets of Ωn not containing any (k+1)-crossing. For example, Δn,1 has one maximal set for each triangulation of the n-gon. Dress, Koolen, and Moulton were able to prove that all maximal sets in Δn,k have the same number k(2n-2k-1) of line segments. We demonstrate that the number of such maximal sets is counted by a k×k determinant of Catalan numbers. By the work of Desainte-Catherine and Viennot, this determinant is known to count quite a few other objects including fans of non-crossing Dyck paths. We generalize our result to a larger class of simplicial complexes including some of the complexes appearing in the work of Herzog and Trung on determinantal ideals. 相似文献
2.
For all non-negative integers n1,n2,n3,j1,j2 and j3 with nk+jk>1 for k=1,2,3, (nk,jk)≠(nl,jl) if k≠l, j3=n3−1 and jk≠nk−1 for k=1,2, we study the center variety of the 6-parameter family of real planar polynomial vector given, in complex notation, by , where z=x+iy and A,B,C∈C\{0}. 相似文献
3.
Given a convex n-gon P in R2 with vertices in general position, it is well known that the simplicial complex θ(P) with vertex set given by diagonals in P and facets given by triangulations of P is the boundary complex of a polytope of dimension n−3. We prove that for any non-convex polygonal region P with n vertices and h+1 boundary components, θ(P) is a ball of dimension n+3h−4. We also provide a new proof that θ(P) is a sphere when P is convex with vertices in general position. 相似文献
4.
Let D(G)=(di,j)n×n denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vi and vj in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized. 相似文献
5.
P. Jacob 《Discrete Mathematics》2009,309(4):878-886
A bijection is presented between (1): partitions with conditions fj+fj+1≤k−1 and f1≤i−1, where fj is the frequency of the part j in the partition, and (2): sets of k−1 ordered partitions (n(1),n(2),…,n(k−1)) such that and , where mj is the number of parts in n(j). This bijection entails an elementary and constructive proof of the Andrews multiple-sum enumerating partitions with frequency conditions. A very natural relation between the k−1 ordered partitions and restricted paths is also presented, which reveals our bijection to be a modification of Bressoud’s version of the Burge correspondence. 相似文献
6.
For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant cD such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−cD if and only if for every n≥cD+3, has a cycle of order at least n−cD. Furthermore, we discuss some consequences and variants of this result. 相似文献
7.
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,n−k)), where Cube(n,n−k) is a hypergraph associated to the (n−k)-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. 相似文献
8.
Christian Stump 《Journal of Combinatorial Theory, Series A》2011,118(6):1794-1800
We connect k-triangulations of a convex n-gon to the theory of Schubert polynomials. We use this connection to prove that the simplicial complex with k-triangulations as facets is a vertex-decomposable triangulated sphere, and we give a new proof of the determinantal formula for the number of k-triangulations. 相似文献
9.
Oscar Rojo 《Linear algebra and its applications》2006,414(1):199-217
Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let nk−j+1 and dk−j+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of T for the case of two vertices in level 1 (nk = 2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are , 2 ? j ? k, while the diagonal entries are 0, …, 0, ±1, in the case of the adjacency matrix, and d1, d2, …, dk−1, dk ± 1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree. 相似文献
10.
Hiro Ito 《Discrete Applied Mathematics》2006,154(16):2330-2334
Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x0,x1,…,xn-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex xi and define the area AP(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size cH(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:
- •
- AP(H)?AP(H′) for all convex n-gons P.
- •
- cH(i,j,k)?cH′(i,j,k) for all convex three-cuts C(i,j,k).
11.
R.M. Green 《Advances in Mathematics》2009,222(1):216-239
We construct a CW decomposition Cn of the n-dimensional half cube in a manner compatible with its structure as a polytope. For each 3?k?n, the complex Cn has a subcomplex Cn,k, which coincides with the clique complex of the half cube graph if k=4. The homology of Cn,k is concentrated in degree k−1 and furthermore, the (k−1)st Betti number of Cn,k is equal to the (k−2)nd Betti number of the complement of the k-equal real hyperplane arrangement. These Betti numbers, which also appear in theoretical computer science, numerical analysis and engineering, are the coefficients of a certain Pascal-like triangle (Sloane's sequence A119258). The Coxeter groups of type Dn act naturally on the complexes Cn,k, and thus on the associated homology groups. 相似文献
12.
Gábor Hetyei 《Journal of Combinatorial Theory, Series A》2008,115(4):569-592
We generalize the notion of the Tchebyshev transform of a graded poset to a triangulation of an arbitrary simplicial complex in such a way that, at the level of the associated F-polynomials j∑fj−1(j(x−1)/2), the triangulation induces taking the Tchebyshev transform of the first kind. We also present a related multiset of simplicial complexes whose association induces taking the Tchebyshev transform of the second kind. Using the reverse implication of a theorem by Schelin we observe that the Tchebyshev transforms of Schur stable polynomials with real coefficients have interlaced real roots in the interval (−1,1), and present ways to construct simplicial complexes with Schur stable F-polynomials. We show that the order complex of a Boolean algebra is Schur stable. Using and expanding the recently discovered relation between the derivative polynomials for tangent and secant and the Tchebyshev polynomials we prove that the roots of the corresponding pairs of derivative polynomials are all pure imaginary, of modulus at most one, and interlaced. 相似文献
13.
A. Algaba 《Journal of Mathematical Analysis and Applications》2003,278(1):109-124
We study polynomial systems with degeneracy at infinity and a center-focus equilibrium at the origin. We give some general properties related to the existence of polynomial commutators and use these properties in order to characterize uniformly isochronous polynomial centers with polynomial commutator and, also, we show that the commutator of the centers of the analytic systems whose angular speed is constant can be chosen of radial form. Finally, we characterize the systems (−y+Ps+∑j=kn−1xHj,x+Qs+∑j=kn−1yHj)t with polynomial commutator, with Pj,Qj,Hj and Kj homogeneous polynomials. 相似文献
14.
For each positive integer j, let βj(n):=∑p|npj. Given a fixed positive integer k, we show that there are infinitely many positive integers n having at least two distinct prime factors and such that βj(n)|n for each j∈{1,2,…,k}. 相似文献
15.
In dimension n?3, for k≈|x|2m that can be written as a sum of squares of smooth functions, we prove that a C2 convex solution u to a subelliptic Monge-Ampère equation detD2u=k(x,u,Du) is itself smooth if the elementary (n−1)st symmetric curvature kn−1 of u is positive (the case m?2 uses an additional nondegeneracy condition on the sum of squares). Our proof uses the partial Legendre transform, Calabi's identity for ∑uijσij where σ is the square of the third order derivatives of u, the Campanato method Xu and Zuily use to obtain regularity for systems of sums of squares of Hörmander vector fields, and our earlier work using Guan's subelliptic methods. 相似文献
16.
17.
For a contraction A on a Hilbert space H, we define the index j(A) (resp., k(A)) as the smallest nonnegative integer j (resp., k) such that ker(I−Aj∗Aj) (resp., ker(I−Ak*Ak)∩ker(I−AkAk∗)) equals the subspace of H on which the unitary part of A acts. We show that if , then j(A)?n (resp., k(A)?⌈n/2⌉), and the equality holds if and only if A is of class Sn (resp., one of the three conditions is true: (1) A is of class Sn, (2) n is even and A is completely nonunitary with ‖An−2‖=1 and ‖An−1‖<1, and (3) n is even and A=U⊕A′, where U is unitary on a one-dimensional space and A′ is of class Sn−1). 相似文献
18.
Kazuhiro Takimoto 《Journal of Mathematical Analysis and Applications》2005,309(1):227-237
We consider the removability of singular sets for the curvature equations of the form Hk[u]=ψ, which is determined by the kth elementary symmetric function, in an n-dimensional domain Ω. We prove that, for 1?k?n−1 and a compact set K whose (n−k)-dimensional Hausdorff measure is zero, any generalized solution to the curvature equation on Ω?K is always extendable to a generalized solution on the whole domain Ω. 相似文献
19.
We show that for every k-automatic sequence there exists a natural number p>0 such that the sequences of the form (kpn+j)n?0 with j=0,…,p−1 are scaling sequences for f. Moreover, we demonstrate that every limit set is the union of certain basic limit sets. 相似文献
20.
In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x1,x2,…,xk?nk there exist k distinct integers j1,j2,…,jk so that xi= aii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k). 相似文献