Source author record

Carlos E. Valencia

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.AC math.NT Data Structures and Algorithms Discrete Mathematics math.OC Methodology

Catalog footprint

Research overview

15works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Signature invariants of monomial ideals

Let $I$ be a monomial ideal of a polynomial ring $R=K[x_1,\ldots,x_n]$ over a field $K$ and let ${\rm sgn}(I)$ be its signature ideal. If $I$ is not a principal ideal, we show that the depth of $R/I$ is the depth of $R/{\rm sgn}(I)$ , and the regularity of $R/{\rm sgn}(I)$ is at most the regularity of $R/I$ . For ideals of height at least $2$ , we show that the height and the associated primes of $I$ and its signature ${\rm sgn}(I)$ are the same, and we show that $I$ is Cohen--Macaulay (resp. Gorenstein) if and only if ${\rm sgn}(I)$ is Cohen--Macaulay (resp. Gorenstein), and furthermore we show that the v-number of ${\rm sgn}(I)$ is at most the v-number of $I$ . We give an algorithm to compute the signature of a monomial ideal using \textit{Macaulay} $2$ , and an algorithm to examine given families of monomial ideal by computing their signature ideals and determining which of these are either Cohen--Macaulay or Gorenstein.

preprint2025arXiv

Weighted Ehrhart functions

We give an algorithm to compute weighted Ehrhart functions of lattice polytopes for polynomial weights using Lagrange interpolation. We show how to compute generating functions of polynomials using those of unit cubes and Eulerian numbers, and use integer programming to study the algebraic properties of the Ehrhart ring of the $d$ -th unit cube. Then we show some applications to weighted Ehrhart functions and enumeration problems.

preprint2022arXiv

Algorithmic aspects of arithmetical structures

Arithmetical structures on graphs were first introduced in \cite{Lorenzini89}. Later in \cite{arithmetical} they were further studied in the setting of square non-negative integer matrices. In both cases, necessary and sufficient conditions for the finiteness of the set of arithmetical structures were given. More precisely, an arithmetical structure on a non-negative integer matrix $L$ with zero diagonal is a pair $(\mathbf{d},\mathbf{r})\in \mathbb{N}_+^n\times \mathbb{N}_+^n$ such that $(\textrm{Diag}(\mathbf{d})-L)\mathbf{r}^t=\mathbf{0}^t\text{ and }\gcd(r_1,\ldots,r_n)=1.$ Thus, arithmetical structures on $L$ are solutions of the polynomial Diophantine equation $f_L(X):=\det(\text{Diag}(X)-L)=0.$ Therefore, it is of interest to ask for an algorithm that compute them. We present an algorithm that computes arithmetical structures on a square integer non-negative matrix $L$ with zero diagonal. In order to do this we introduce a new class of Z-matrices, which we call quasi $M$ -matrices.

preprint2022arXiv

Arithmetical structures on dominated polynomials

In~\cite{algorithmic} was given an algorithm that computes arithmetical structures on matrices. We use some of the ideas contained there to get an algorithm that computes arithmetical structures over dominated polynomials. A dominated polynomial is an integer multivariate polynomial such that contains a monomial which is divided by all its monomials.

preprint2020arXiv

Computing sandpile configurations using integer linear programming

It is well known that recurrent sandpile configurations can be characterized as the optimal solution of certain optimization problems. In this article, we present two new integer linear programming models, one that computes recurrent configurations and other that computes the order of the configuration. Finally, by using duality of linear programming, we are able to compute the identity configuration for the cone of a regular graph.

preprint2018arXiv

Counting Arithmetical Structures on Paths and Cycles

Let $G$ be a finite, simple, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $\mathbf{d},\mathbf{r}$ such that $(\mathrm{diag}(\mathbf{d})-A)\mathbf{r}=0$ , where $A$ is the adjacency matrix of $G$ . We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the cokernels of the matrices $(\mathrm{diag}(\mathbf{d})-A)$ ). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\binom{2n-1}{n-1}$ , and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

preprint2014arXiv

Optimum matchings in weighted bipartite graphs

Given an integer weighted bipartite graph $\{G=(U\sqcup V, E), w:E\rightarrow \mathbb{Z}\}$ we consider the problems of finding all the edges that occur in some minimum weight matching of maximum cardinality and enumerating all the minimum weight perfect matchings. Moreover, we construct a subgraph $G_{cs}$ of $G$ which depends on an $ε$ -optimal solution of the dual linear program associated to the assignment problem on $\{G,w\}$ that allows us to reduced this problems to their unweighed variants on $G_{cs}$ . For instance, when $G$ has a perfect matching and we have an $ε$ -optimal solution of the dual linear program associated to the assignment problem on $\{G,w\}$ , we solve the problem of finding all the edges that occur in some minimum weight perfect matching in linear time on the number of edges. Therefore, starting from scratch we get an algorithm that solves this problem in time $O(\sqrt{n}m\log(nW))$ , where $n=|U|\geq |V|$ , $m=|E|$ , and $W={\rm max}\{|w(e)|\, :\, e\in E\}$ .

preprint2013arXiv

Graphs with two trivial critical ideals

The critical ideals of a graph are the determinantal ideals of the generalized Laplacian matrix associated to a graph. A basic property of the critical ideals of graphs asserts that the graphs with at most k trivial critical ideals, $Γ_{\leq k}$ , are closed under induced subgraphs. In this article we find the set of minimal forbidden subgraphs for $Γ_{\leq 2}$ , and we use this forbidden subgraphs to get a classification of the graphs in $Γ_{\leq 2}$ . As a consequence we give a classification of the simple graphs whose critical group has two invariant factors equal to one. At the end of this article we give two infinite families of forbidden subgraphs.

preprint2013arXiv

On bounds for some graph invariants

Let $G$ be a graph without isolated vertices and let $α(G)$ be its stability number and $τ(G)$ its covering number. The {\it $α_{v}$ -cover} number of a graph, denoted by $α_{v}(G)$ , is the maximum natural number $m$ such that every vertex of $G$ belongs to a maximal independent set with at least $m$ vertices. In the first part of this paper we prove that $α(G)\leq τ(G)[1+α(G)-α_{v}(G)]$ . We also discuss some conjectures analogous to this theorem. In the second part we give a lower bound for the number of edges of a graph $G$ as a function of the stability number $α(G)$ , the covering number $τ(G)$ and the number of connected components $c(G)$ of $G$ . Namely, let $α$ and $τ$ be two natural numbers and let $$ Γ(α,τ)= \min{\sum_{i=1}^α\bin{z_i}{2} | z_1+...+z_α= α+τ{and} z_i \geq 0 \forall i=1,..., α}. $$ Then if $G$ is any graph, we have: $|E(G)| \geq α(G)-c(G)+ Γ(α(G), τ(G)).$

preprint2013arXiv

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Grobner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.

preprint2013arXiv

Small clique number graphs with three trivial critical ideals

The critical ideals of a graph are the determinantal ideals of the generalized Laplacian matrix associated to a graph. In this article we provide a set of minimal forbidden graphs for the set of graphs with at most three trivial critical ideals. Then we use these forbidden graphs to characterize the graphs with at most three trivial critical ideals and clique number equal to 2 and 3.

preprint2012arXiv

Dimension Reduction in Principal Component Analysis for Trees

The statistical analysis of tree structured data is a new topic in statistics with wide application areas. Some Principal Component Analysis (PCA) ideas were previously developed for binary tree spaces. In this study, we extend these ideas to the more general space of rooted and labeled trees. We re-define concepts such as tree-line and forward principal component tree-line for this more general space, and generalize the optimal algorithm that finds them. We then develop an analog of classical dimension reduction technique in PCA for the tree space. To do this, we define the components that carry the least amount of variation of a tree data set, called backward principal components. We present an optimal algorithm to find them. Furthermore, we investigate the relationship of these the forward principal components, and prove a path-independency property between the forward and backward techniques. We apply our methods to a data set of brain artery data set of 98 subjects. Using our techniques, we investigate how aging affects the brain artery structure of males and females. We also analyze a data set of organization structure of a large US company and explore the structural differences across different types of departments within the company.

preprint2011arXiv

On the Sandpile group of the cone of a graph

In this article, we give a partial description of the sandpile group of the cone of the cartesian product of graphs in function of the sandpile group of the cone of their factors. Also, we introduce the concept of uniform homomorphism of graphs and prove that every surjective uniform homomorphism of graphs induces an injective homomorphism between their sandpile groups. As an application of these result we obtain an explicit description of a set of generators of the sandpile group of the cone of the hypercube of dimension d.

preprint2010arXiv

On the critical group of matrices

Given a graph G with a distinguished vertex s, the critical group of (G,s) is the cokernel of their reduced Laplacian matrix L(G,s). In this article we generalize the concept of the critical group to the cokernel of any matrix with entries in a commutative ring with identity. In this article we find diagonal matrices that are equivalent to some matrices that generalize the reduced Laplacian matrix of the path, the cycle, and the complete graph over an arbitrary commutative ring with identity. We are mainly interested in those cases when the base ring is the ring of integers and some subrings of matrices. Using these equivalent diagonal matrices we calculate the critical group of the m-cones of the l-duplications of the path, the cycle, and the complete graph. Also, as byproduct, we calculate the critical group of another matrices, as the m-cones of the l-duplication of the bipartite complete graph with m vertices in each partition, the bipartite complete graph with 2m vertices minus a matching.

preprint2005arXiv

Explicit representations by halfspaces of the edge cone of a graph

Let G be an arbitrary simple graph. The main results are explicit representations of the edge cone of G as a finite intersection of closed halfspaces. If G is bipartite and connected we determine the facets of the edge cone and present a canonical irreducible representation.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Carlos E. Valencia

Research overview

Is this your work?

15 publications

Signature invariants of monomial ideals

Weighted Ehrhart functions

Algorithmic aspects of arithmetical structures

Arithmetical structures on dominated polynomials

Computing sandpile configurations using integer linear programming

Counting Arithmetical Structures on Paths and Cycles

Optimum matchings in weighted bipartite graphs

Graphs with two trivial critical ideals

On bounds for some graph invariants

On the critical ideals of graphs

Small clique number graphs with three trivial critical ideals

Dimension Reduction in Principal Component Analysis for Trees

On the Sandpile group of the cone of a graph

On the critical group of matrices

Explicit representations by halfspaces of the edge cone of a graph

See the researcher in context

Building this map preview