Nathanson Heights and the CSS Conjecture for Cayley Graphs

Abstract

Let G be a finite directed graph, \beta(G) the minimum size of a subset X of edges such that the graph G'=
(V, E / X) is directed acyclic and \gamma(G) the number of pairs of nonadjacent vertices in the undirected graph
obtained from G by replacing each directed edge with an undirected edge. Chudnovsky, Seymour and Sullivan
proved that if G is triangle-free, then \beta(G)\leq\gamma(G). They conjectured a sharper bound (so called the “CSS conjecture”) that \beta(G)\leq\gamma(G)/2. Nathanson and Sullivan verified this conjecture for the directed Cayley
graph Cay(Z/NZ, EA) whose vertex set is the additive group Z/NZ and whose edge set EA is determined by
EA = {(x, x +a) : x \in Z/NZ, a \in A} when N is prime and |A| \leq (N -1)/4 by introducing “height”. In this work,
we extend the definition of height and apply to answer the CSS conjecture for Cay(Z/NZ, EA) to any positive
integer N and |A|\leq (N-1)/4.