Graph orientation is the process of orienting the edges of an undirected graph to obtain a directed graph, and is a topic that has been actively studied in the fields of combinatorial optimization and graph theory. In this talk, we will present our latest results on "reconfiguration of graph orientations", where the directions of some edges are flipped one by one while maintaining a certain connectivity constraint. Our main result is that "for an arbitrary orientation of a 2k-edge-connected undirected graph, we can monotonically increase the edge-connectivity by flipping the directions of some edges one by one, and finally obtain a k-edge-connected orientation." This result strengthens the classical Nash-Williams' theorem, and is useful when discussing the connectivity of the edge-flip graph of k-edge-connected orientations.
This result is based on joint research with some members of this project, and will be presented at SODA2022.