2016/05/10 by Bıyıkoğlu, Türker, Civan, Yusuf
#05C70 #05C75 #05C76 #05E40 #05E45 #13F55 #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics
paper · doi:10.48550/arxiv.1605.02956
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)).