共查询到20条相似文献,搜索用时 0 毫秒
1.
Michael Goff 《Journal of Pure and Applied Algebra》2009,213(6):1170-1172
We prove a conjectured lower bound of Nagel and Reiner on Betti numbers of edge ideals of bipartite graphs. 相似文献
2.
Richard P. Stanley 《Annals of Combinatorics》1998,2(4):351-363
Kontsevich conjectured that the number of zeros over the fieldF
q
of a certain polynomialQ
G
associated with the spanning trees of a graphG is a polynomial function ofq. We show the connection between this conjecture, the Matrix-Tree Theorem, and orthogonal geometry. We verify the conjecture in certain cases, such as the complete graph, and discuss some modifications and extensions.Partially supported by NSF grant #DMS-9743966. 相似文献
3.
It is well known that for two-way contingency tables with fixed row sums and column sums the set of square-free moves of degree two forms a Markov basis. However when we impose an additional constraint that the sum of cell counts in a subtable is also fixed, then these moves do not necessarily form a Markov basis. Thus, in this paper, we show a necessary and sufficient condition on a subtable so that the set of square-free moves of degree two forms a Markov basis. 相似文献
4.
R. Ahlswede H. Aydinian L.H. Khachatrian 《Journal of Combinatorial Theory, Series A》2006,113(3):483-519
In Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21] we posed a series of extremal (set system) problems under dimension constraints. In the present paper, we study one of them: the intersection problem. The geometrical formulation of our problem is as follows. Given integers 0?t, k?n determine or estimate the maximum number of (0,1)-vectors in a k-dimensional subspace of the Euclidean n-space Rn, such that the inner product (“intersection”) of any two is at least t. Also we are interested in the restricted (or the uniform) case of the problem; namely, the problem considered for the (0,1)-vectors of the same weight ω.The paper consists of two parts, which concern similar questions but are essentially independent with respect to the methods used.In Part I, we consider the unrestricted case of the problem. Surprisingly, in this case the problem can be reduced to a weighted version of the intersection problem for systems of finite sets. A general conjecture for this problem is proved for the cases mentioned in Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21]. We also consider a diametric problem under dimension constraint.In Part II, we study the restricted case and solve the problem for t=1 and k<2ω, and also for any fixed 1?t?ω and k large. 相似文献
5.
We introduce a new graph polynomial in two variables. This interlace polynomial can be computed in two very different ways. The first is an expansion analogous to the state space expansion of the Tutte polynomial; the significant differences are that our expansion is over vertex rather than edge subsets, and the rank and nullity employed are those of an adjacency matrix rather than an incidence matrix.The second computation is by a three-term reduction formula involving a graph pivot; the pivot arose previously in the study of interlacement and Euler circuits in four-regular graphs.We consider a few properties and specializations of the two-variable interlace polynomial. One specialization, the vertex-nullity interlace polynomial, is the single-variable interlace graph polynomial we studied previously, closely related to the Tutte–Martin polynomial on isotropic systems previously considered by Bouchet. Another, the vertex-rank interlace polynomial, is equally interesting. Yet another specialization of the two-variable polynomial is the independent-set polynomial. Supported by NSF grant DMS-9971788. 相似文献
6.
An important problem in the theory of finite dynamical systems is to link the structure of a system with its dynamics. This paper contains such a link for a family of nonlinear systems over the field with two elements. For systems that can be described by monomials (including Boolean AND systems), one can obtain information about the limit cycle structure from the structure of the monomials. In particular, the paper contains a sufficient condition for a monomial system to have only fixed points as limit cycles. This condition depends on the cycle structure of the dependency graph of the system and can be verified in polynomial time.Received February 2, 2004 相似文献
7.
A multicomplexM is a collection of monomials closed under divisibility. For suchM we construct a cell complex M whosei-dimensional cells are in bijection with thef
i
monomials ofM of degreei+1. The bijection is such that the inclusion relation of cells corresponds to divisibility of monomials. We then study relations between the numbersf
i
and the Betti numbers of M. For squarefree monomials the construction specializes to the standard geometric realization of a simplicial complex.This work was supported by the Mittag-Leffler Institute during the Combinatorial Year program 1991–92. The second author also acknowledges support from the Serbian Science Foundation, Grant No. 0401D. 相似文献
8.
Let be a G-symmetric graph whose vertex set admits a nontrivial G-invariant partition with block size v. Let
be the quotient graph of relative to and [B,C] the bipartite subgraph of induced by adjacent blocks B,C of . In this paper we study such graphs for which
is connected, (G, 2)-arc transitive and is almost covered by in the sense that [B,C] is a matching of v-1 2 edges. Such graphs arose as a natural extremal case in a previous study by the author with Li and Praeger. The case
K
v+1 is covered by results of Gardiner and Praeger. We consider here the general case where
K
v+1, and prove that, for some even integer n 4,
is a near n-gonal graph with respect to a certain G-orbit on n-cycles of
. Moreover, we prove that every (G, 2)-arc transitive near n-gonal graph with respect to a G-orbit on n-cycles arises as a quotient
of a graph with these properties. (A near n-gonal graph is a connected graph of girth at least 4 together with a set of n-cycles of such that each 2-arc of is contained in a unique member of .) 相似文献
9.
For the ordered set [n] of n elements, we consider the class Bn of bases B of tropical Plücker functions on 2[n] such that B can be obtained by a series of so-called weak flips (mutations) from the basis formed by the intervals in [n]. We show that these bases are representable by special wiring diagrams and by certain arrangements generalizing rhombus tilings on an n-zonogon. Based on the generalized tiling representation, we then prove that each weakly separated set-system in 2[n] having maximum possible size belongs to Bn, yielding the affirmative answer to one conjecture due to Leclerc and Zelevinsky. We also prove an analogous result for a hyper-simplex . 相似文献
10.
Cospectral graphs and the generalized adjacency matrix 总被引:1,自引:0,他引:1
Let J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ − A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ − A for exactly one value of y. We call such graphs -cospectral. It follows that is a rational number, and we prove existence of a pair of -cospectral graphs for every rational . In addition, we generate by computer all -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of -cospectral graphs for all rational , where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of , and by computer we find all such pairs of -cospectral graphs on at most eleven vertices. 相似文献
11.
We consider a question raised by Suhov and Voice from quantum information theory and quantum computing. An element of a partition
of {1, ..., n} is said to be block-stable for
if it is not moved to another block under the action of π. The problem concerns the determination of the generating series
for elements of
with respect to the number of block-stable elements of a canonical partition of a finite n-set, with block sizes k1, ..., kr, in terms of the moment (power) sums pq(k1, ..., kr). We also consider the limit
subject to the condition that
exists for q = 1, 2,....
Received January 31, 2006 相似文献
12.
R. E. Tarjan 《Combinatorica》1985,5(4):367-378
Sleator and Tarjan have invented a form of self-adjusting binary search tree called thesplay tree. On any sufficiently long access sequence, splay trees are as efficient, to within a constant factor, as both dynamically
balanced and static optimum search trees. Sleator and Tarjan have made a much stronger conjecture; namely, that on any sufficiently
long access sequence and to within a constant factor, splay trees are as efficient asany form of dynamically updated search tree. Thisdynamic optimality conjecture implies as a special case that accessing the items in a splay tree in sequential order takes linear time, i.e.O(1) time per access. In this paper we prove this special case of the conjecture, generalizing an unpublished result of Wegman.
Oursequential access theorem not only supports belief in the dynamic optimality conjecture but provides additional insight into the workings of splay
trees. As a corollary of our result, we show that splay trees can be used to simulate output-restricted deques (double-ended
queues) in linear time. We pose several open problems related to our result. 相似文献
13.
In this paper we show that if X is an s-distance set in
m
and X is on
p concentric spheres then
Moreover if
X is antipodal, then
. 相似文献
14.
William H. Cunningham 《Combinatorica》1983,3(1):53-68
A decomposition theory for submodular functions is described. Any such function is shown to have a unique decomposition consisting of indecomposable functions and certain highly decomposable functions, and the latter are completely characterized. Applications include decompositions of hypergraphs based on edge and vertex connectivity, the decomposition of matroids based on three-connectivity, the Gomory—Hu decomposition of flow networks, and Fujishige’s decomposition of symmetric submodular functions. Efficient decomposition algorithms are also discussed. 相似文献
15.
Criel Merino López 《Annals of Combinatorics》1997,1(1):253-259
It is shown that the generating function of critical configurations of a version of a chip firing game on a graphG is an evaluation of the Tutte polynomial ofG, thus proving a conjecture of Biggs [3].
Supported by a grant from D.G.A.P.A. 相似文献
16.
C. M. Reidys 《Advances in Applied Mathematics》2001,27(4):790
We study a class of discrete dynamical systems that consists of the following data: (a) a finite (labeled) graph Y with vertex set {1, …, n}, where each vertex has a binary state, (b) a vertex labeled multi-set of functions (Fi, Y:
2n →
2n)i, and (c) a permutation π Sn. The function Fi, Y updates the binary state of vertex i as a function of the states of vertex i and its Y-neighbors and leaves the states of all other vertices fixed. The permutation π represents a Y-vertex ordering according to which the functions Fi, Y are applied. By composing the functions Fi, Y in the order given by π we obtain the sequential dynamical system (SDS):
In this paper we first establish a sharp, combinatorial upper bound on the number of non-equivalent SDSs for fixed graph Y and multi-set of functions (Fi, Y). Second, we analyze the structure of a certain class of fixed-point-free SDSs. 相似文献
Full-size image
17.
We consider Boolean algebras constructed from pseudo-trees in various ways and make comments about related classes of Boolean algebras. 相似文献
18.
Sequential Dynamical Systems (SDSs) are mathematical models for analyzing simulation
systems. We investigate phase space properties of some special classes of SDSs obtained
by restricting the local transition functions used at the nodes. We show that any SDS over the
Boolean domain with symmetric Boolean local transition functions can be efficiently simulated
by another SDS which uses only simple threshold and simple inverted threshold functions, where
the same threshold value is used at each node and the underlying graph is
d-regular for some integer
d. We establish tight or nearly tight upper and lower bounds
on the number of steps needed
for SDSs over the Boolean domain with 1-, 2- or 3-threshold functions at each of the nodes to
reach a fixed point. When the domain is a unitary semiring and each node computes a linear
combination of its inputs, we present a polynomial time algorithm to determine whether such an
SDS reaches a fixed point. We also show (through an explicit construction) that there are Boolean
SDSs with the NOR function at each node such that their phase spaces contain directed cycles
whose length is exponential in the number of nodes of the underlying graph of the SDS.AMS Subject Classification: 68Q10, 68Q17, 68Q80. 相似文献
19.
Young-Tak Oh 《Advances in Mathematics》2009,222(2):485-526
Let G, H be abelian profinite groups whose orders are coprime and assume that q ranges over the set of integers. The aim of this paper is to establish an isomorphism of functors , where denotes the q-deformed Witt-Burnside ring functor of G introduced in [Y.-T. Oh, q-Deformation of Witt-Burnside rings, Math. Z. 207 (1) (2007) 151-191]. To do this, we first establish an isomorphism of functors , where denotes the q-deformed Burnside ring functor of G which was also introduced in [Y.-T. Oh, q-Deformation of Witt-Burnside rings, Math. Z. 207 (1) (2007) 151-191]. As an application, we derive a pseudo-multiplicative property of the q-Möbius function associated to the lattice of open subgroups of the direct sum of G and H. 相似文献
20.
A nucleotide sequence can be considered as a realization of the non-equal-probability independently and identically distributed (niid) model. In this paper we derive the exact distribution of the occurrence number for each K-tuple with respect to the niid model by means of the Goulden-Jackson cluster method. An application of the probability function to get exact expectation curves [9] is presented, accompanied by comparison between the exact approach and the approximate solution.Received October 31, 2004 相似文献