Mathematics – Combinatorics
Scientific paper
2008-09-22
Mathematics
Combinatorics
Scientific paper
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 table, 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 a HAP table 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.
Kashiwabara Kenji
No associations
LandOfFree
Sports scheduling for not all pairs of teams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Sports scheduling for not all pairs of teams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sports scheduling for not all pairs of teams will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-299735