arXiv:1605.02956 [math.CO]AbstractReferencesReviewsResources
Projective dimension of (hyper)graphs and the Castelnuovo-Mumford regularity of bipartite graphs
Published 2016-05-10Version 1
We prove that the projective dimension of any (hyper)graph can be bounded from above by the (Castelnuovo-Mumford) regularity of its Levi graph (or incidence bipartite graph). This in particular brings the use of regularity's upper bounds on the calculation of projective dimension of (hyper)graphs. When G is just a (simple) graph, we prove that there exists an induced subgraph H of G such that prod-dim(G)=reg(S(H)), where S(H) is the subdivision graph of H. Moreover, we show that known upper bounds on prod-dim(G) involving domination parameters are in fact upper bounds to reg(S(G)).
Comments: 21 pages
Related articles: Most relevant | Search more
Matchings, coverings, and Castelnuovo-Mumford regularity
Vertex decomposable graphs, codismantlability, Cohen-Macaulayness and Castelnuovo-Mumford regularity
arXiv:1412.5920 [math.CO] (Published 2014-12-18)
Connectivity through bounds for the Castelnuovo-Mumford regularity