Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Scheduling partial round robin tournaments subject to home away pattern sets. | Scheduling partial round robin tournaments subject to home away pattern sets Kenji Kashiwabara Department of General Systems Studies University of Tokyo 3-8-1 Komaba Meguroku Tokyo Japan kashiwa@ Submitted Oct 1 2008 Accepted Apr 24 2009 Published Apr 30 2009 Mathematics Subject Classification 90B35 Abstract We consider the following sports scheduling problem. Consider 2n teams in a sport league. Each pair of teams must play exactly one match in 2n 1 days. That is n games are held simultaneously in a day. We want to make a schedule which has n 2n 1 games for 2n 1 days. When we make a schedule the schedule must satisfy a constraint according to the HAP set which designates a home game or an away game for each team and each date. Two teams cannot play against each other unless one team is assigned to a home game and the other team is assigned to an away game. Recently D. Briskorn proposed a necessary condition for an HAP set to have a proper schedule. And he proposed a conjecture that such a condition is also sufficient. That is if a solution to the linear inequalities exists they must have an integral solution. In this paper we rewrite his conjecture by using perfect matchings. We consider a monoid in the affine space generated by perfect matchings. In terms of the Hilbert basis of such a monoid the problem is naturally generalized to a scheduling problem for not all pairs of teams described by a regular graph. In this paper we show a regular graph such that the corresponding linear inequalities have a solution but do not have any integral solution. Moreover we discuss for which regular graphs the statement generalizing the conjecture holds. 1 Introduction First consider the situation that there are 2n teams in a sport league and we have to make a schedule for any pair of teams to play exactly one match in 2n 1 days. n games are held simultaneously everyday. We have to make a schedule which have n n 1 games in 2n 1 days. Each team plays against .
