tailieunhanh - Báo cáo toán học: "Equitable hypergraph orientation"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Equitable hypergraph orientations. | Equitable hypergraph orientations Yair Caro Douglas West t Raphael Yuster Ỉ Submitted Dec 14 2010 Accepted May 13 2011 Published May 23 2011 Mathematics Subject Classification 05C65 Abstract A classical result in graph theory asserts that every graph can be oriented so that the indegree and outdegree of each vertex differ by at most 1. We study the extent to which the result generalizes to uniform hypergraphs. 1 Introduction In recent years many researchers have begun to study hypergraph generalizations of classical results in graph theory. Areas of study include Turan-type problems matchings and factors and properties of random structures. In this spirit we consider the generalization of an elementary classical result. An orientation of a graph is obtained by assigning a direction order to each edge. An orientation is fully balanced if each vertex has the same number of edges entering it and exiting it. An even graph is a graph whose vertex degrees are all even. The existence of Eulerian circuits in connected even graphs implies that all even graphs have fully balanced orientations. An easy consequence is that every graph has an equitable orientation where an orientation is equitable if for every vertex the numbers of entering and exiting edges differ by at most 1. In this note we generalize equitable orientation to the setting of uniform hypergraphs. An orientation of a hypergraph associates with each edge an ordering of its vertices an edge of size r can be ordered in r ways with each vertex in one of r positions. Let H denote an orientation of an r-uniform hypergraph H. For a set S of positions and a set Department of Mathematics University of Haifa-Oranim Tivon 36006 Israel yacaro@. Department of Mathematics University of Illinois Urbana IL 61801 . west@. Research supported by the National Security Agency under Award H98230-10-1-0363. Department of Mathematics University of Haifa Haifa 31905 Israel raphy@. THE .