Sports scheduling for not all pairs of teams
| dc.creator | Kashiwabara, Kenji | |
| dc.date | 2008-09-22 | |
| dc.date | 2008-09-24 | |
| dc.date.accessioned | 2026-07-07T10:04:33Z | |
| dc.date.available | 2026-07-07T10:04:33Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0809.3682 | |
| dc.identifier | http://arxiv.org/abs/0809.3682 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/169721 | |
| dc.subject | Combinatorics | |
| dc.title | Sports scheduling for not all pairs of teams | |
| dc.type | text |