Bounding Betti numbers of bipartite graph ideals

We prove a conjectured lower bound of Nagel and Reiner on Betti numbers of edge ideals of bipartite graphs.     

Spanning trees and a conjecture of Kontsevich

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.     

Markov bases for two-way subtable sum problems

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.     

Intersection theorems under dimension constraints

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 Rⁿ, 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.     

A Two-Variable Interlace Polynomial

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.     

Boolean Monomial Dynamical Systems

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     

Onf-vectors and Betti numbers of multicomplexes

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.     

Almost Covers Of 2-Arc Transitive Graphs

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 .)     

Plücker environments, wiring and tiling diagrams, and weakly separated set-systems

For the ordered set [n] of n elements, we consider the class Bn of bases B of tropical Plücker functions on ²[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 ²[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 .     

Cospectral graphs and the generalized adjacency matrix

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.     

A Symmetric Function Resolution of the Number of Permutations With Respect to Block-Stable Elements

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 k₁, ..., k_r, in terms of the moment (power) sums p_q(k₁, ..., k_r). We also consider the limit subject to the condition that exists for q = 1, 2,.... Received January 31, 2006     

Sequential access in splay trees takes linear time

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.     

An Upper Bound for the Cardinality of an <Emphasis Type="Italic">s</Emphasis>-Distance Set in Euclidean Space

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 .     

Decomposition of submodular functions

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.     

Chip firing and the tutte polynomial

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.     

On Acyclic Orientations and Sequential Dynamical Systems

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 (F_i, Y: ₂ⁿ →  ₂ⁿ)_i, and (c) a permutation π  S_n. The function F_i, 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 F_i, Y are applied. By composing the functions F_i, Y in the order given by π we obtain the sequential dynamical system (SDS):

Full-size image

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 (F_i, Y). Second, we analyze the structure of a certain class of fixed-point-free SDSs.     

Pseudo-trees and Boolean algebras

We consider Boolean algebras constructed from pseudo-trees in various ways and make comments about related classes of Boolean algebras.     

On Some Special Classes of Sequential Dynamical Systems

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.     

Decomposition of the Witt-Burnside ring and Burnside ring of an abelian profinite group

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.     

Exact Distribution of the Occurrence Number for K-tuples Over an Alphabet of Non-Equal Probability Letters

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