Even factors, jump systems, and discrete convexity

A jump system, which is a set of integer lattice points with an exchange property, is an extended concept of a matroid. Some combinatorial structures such as the degree sequences of the matchings in an undirected graph are known to form a jump system.On the other hand, the maximum even factor problem is a generalization of the maximum matching problem into digraphs. When the given digraph has a certain property called odd-cycle-symmetry, this problem is polynomially solvable.The main result of this paper is that the degree sequences of all even factors in a digraph form a jump system if and only if the digraph is odd-cycle-symmetric. Furthermore, as a generalization, we show that the weighted even factors induce an M-convex (M-concave) function on a constant-parity jump system. These results suggest that even factors are a natural generalization of matchings and the assumption of odd-cycle-symmetry of digraphs is essential.