Alon-Tarsi Conjecture

Author

Eric W. Weisstein
December 18, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/Alon-TarsiConjecture.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Alon-TarsiConjecture.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Code

This code by Hans Michel:

LatinSquares[n_Integer?Positive]:=Module[{s,ss,l={},i,j},
s=Table[j,{i,n},{j,n}];
ss=Table[{},{i,n}];
Choose[ro_,cl_]:=Module[{e1,e2,i},e1=s[[ro,cl]];
For[i=cl,i≤n,i++,e2=s[[ro,i]];
If[!MemberQ[ss[[cl]],e2],s[[ro,cl]]=e2;s[[ro,i]]=e1;AppendTo[ss[[cl]],e2];
If[cl≠n,Choose[ro,cl+1],If[ro≠n,Choose[ro+1,1],AppendTo[l,s]];
];(*End If cl not eq n*)
s[[ro,i]]=e2;ss[[cl]]=DeleteCases[ss[[cl]],e2];
];(*End If Member*)
];
(*End For*)
s[[ro,cl]]=e1;
];
Choose[1,1];
l
]

LatinSquareParity[l_]:=Times@@Flatten[(Signature/@#)&/@{l,Transpose[l]},1]

Alon-Tarsi Number

at={1,1,-1,4,-24,2304,368640,6210846720};

difs=MapIndexed[Switch[#2[[1]],
1,1,
_?OddQ,0,
_,#2[[1]]!(#2[[1]]-1)!#1]&,at]

squares=Take[{1,2,12,576,161280,812851200,61479419904000,108776032459082956800,5524751496156892842531225600,9982437658213039871725064756920320000,776966836171770144107444346734230682311065600000},8];

fd=Take[{1,1,2,24,1344,1128960,12198297600,2697818265354240,15224734061278915461120,2750892211809148994633229926400,19464657391668924966616671344752852992000},8];

SplitLengths[l_List]:=Which[
Length[l]==1&&l[[1,1]]==1,{Length[l[[1]]],0},
Length[l]==1&&l[[1,1]]==-1,{0,Length[l[[1]]]},
True,Length/@Reverse[l]
]

(table=Table[Flatten[{
n,
s=Split[p=Sort[LatinSquareParity/@(ls=LatinSquares[n])]];
Length[Flatten[p]],
{#,Subtract@@#}&@SplitLengths[s],
Length[fd=Select[ls,Union[Tr[#,List]]=={1}&]],
{#,1/(n-1)!Subtract@@#}&@SplitLengths[Split[Sort[LatinSquareParity/@fd]]],
at[[n]]
}],
{n,5}]);//Timing

TableForm[table,TableHeadings->{None,{"n","L(n)","els(n)","ols(n)","els(n)-ols(n)","fd(n)","fdels(n)","fdols(n)","(fdels(n)-fdols(n))/(n-1)!","at(n)"}}]

TableForm[Table[{n,squares[[n]],(difs[[n]]+squares[[n]])/2,(difs[[n]]-squares[[n]])/2,difs[[n]],fd[[n]],
(fd[[n]]+at[[n]](n-1)!)/2,(fd[[n]]-at[[n]](n-1)!)/2,at[[n]]},{n,8}],TableHeadings->{None,{"n","L(n)","els(n)","ols(n)","els(n)-ols(n)","fd(n)","fdels(n)","fdols(n)","(fdels(n)-fdols(n))/(n-1)!","at(n)"}}]