Narrow Results

We use purely combinatorial arguments to give a formula to compute all graded Betti numbers of path ideals of paths and cycles. As a consequence, we can give new and short proofs for the known formulas of regularity and projective dimensions of path ideals of paths.

Given any fixed integer q ≥ 2, a q-monomial is of the format such that 1 ≤ s_j ≤ q - 1, 1 ≤ j ≤ t. q-monomials are natural generalizations of multilinear monomials. Recent research on testing multilinear monomials and q-monomials for prime q in multivariate polynomials relies on the property that Z_q is a field when q ≥ 2 is prime. When q > 2 is not prime, it remains open whether the problem of testing q-monomials can be solved in some compatible complexity. In this paper, we present a randomized O*(7.15^k) algorithm for testing q-monomials of degree k that are found in a multivariate polynomial that is represented by a tree-like circuit with a polynomial size, thus giving a positive, affirming answer to the above question. Our algorithm works regardless of the primality of q and improves upon the time complexity of the previously known algorithm for testing q-monomials for prime q > 7.