Return to Answer

Jean Gallier gives this bound (Proposition 4.16 in Ch.4 of "Discrete Math" preprint)

$$f(n,k) < 2^{n-1} \frac{{n \choose k+1}}{n \choose n/2}$$

where $f(N,k)=\sum_{i=0}^k {N\choose i}$, and $k\le n/2-1$ for even $n$

It seems to be worse than Michael's bound except for large values of k

Here's a plot of f(50,k) (blue circles), Michael Lugo's bound (brown diamonds) and Gallier's (magenta squares)

n = 50;
bisum[k_] := Total[Table[Binomial[n, x], {x, 0, k}]];
bibound[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lugobound[k_] := Binomial[n, k] (n - (k - 1))/(n - (2 k - 1));
ListPlot[Transpose[{bisum[#], bibound[#], lugobound[#]} & /@ 
   Range[0, n/2 - 1]], PlotRange -> All, PlotMarkers -> Automatic]

Edit The proof, Proposition 3.8.2 from Lovasz "Discrete Math".

Lovasz gives another bound (Theorem 5.3.2) in terms of exponential which seems fairly close to previous one

$$f(n,k)\le 2^{n-1} \exp (\frac{(n-2k-2)^2}{4(1+k-n)}$$ Lovasz bound is the top one.

n = 50;
gallier[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lovasz[k_] := 2^(n - 1) Exp[(n - 2 k - 2)^2/(4 (1 + k - n))];
ListPlot[Transpose[{gallier[#], lovasz[#]} & /@ Range[0, n/2 - 1]], 
 PlotRange -> All, PlotMarkers -> Automatic]

Jean Gallier gives this bound (Proposition 4.16 in Ch.4 of "Discrete Math" preprint)

$$f(n,k) < 2^{n-1} \frac{{n \choose k+1}}{n \choose n/2}$$

where $f(N,k)=\sum_{i=0}^k {N\choose i}$, and $k\le n/2-1$ for even $n$

It seems to be worse than Michael's bound except for large values of k

Here's a plot of f(50,k) (blue circles), Michael Lugo's bound (brown diamonds) and Gallier's (magenta squares)

n = 50;
bisum[k_] := Total[Table[Binomial[n, x], {x, 0, k}]];
bibound[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lugobound[k_] := Binomial[n, k] (n - (k - 1))/(n - (2 k - 1));
ListPlot[Transpose[{bisum[#], bibound[#], lugobound[#]} & /@ 
   Range[0, n/2 - 1]], PlotRange -> All, PlotMarkers -> Automatic]

Edit The proof, Proposition 3.8.2 from Lovasz "Discrete Math".

Lovasz gives another bound (Theorem 5.3.2) in terms of exponential which seems fairly close to previous one

$$f(n,k)\le 2^{n-1} \exp (\frac{(n-2k-2)^2}{4(1+k-n)}$$ Lovasz bound is the top one.

n = 50;
gallier[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lovasz[k_] := 2^(n - 1) Exp[(n - 2 k - 2)^2/(4 (1 + k - n))];
ListPlot[Transpose[{gallier[#], lovasz[#]} & /@ Range[0, n/2 - 1]], 
 PlotRange -> All, PlotMarkers -> Automatic]

Jean Gallier gives this bound (Proposition 4.16 in Ch.4 of "Discrete Math" preprint)

$$f(n,k) < 2^{n-1} \frac{{n \choose k+1}}{n \choose n/2}$$

where $f(N,k)=\sum_{i=0}^k {N\choose i}$, and $k\le n/2-1$ for even $n$

It seems to be worse than Michael's bound except for large values of k

Here's a plot of f(50,k) (blue circles), Michael Lugo's bound (brown diamonds) and Gallier's (magenta squares)

n = 50;
bisum[k_] := Total[Table[Binomial[n, x], {x, 0, k}]];
bibound[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lugobound[k_] := Binomial[n, k] (n - (k - 1))/(n - (2 k - 1));
ListPlot[Transpose[{bisum[#], bibound[#], lugobound[#]} & /@ 
   Range[0, n/2 - 1]], PlotRange -> All, PlotMarkers -> Automatic]

Edit For proof, Jean Gallier refers to Lovasz who gives a proof for bound which seems quite on the surface, although numerically it's very close to his bound $$f(n,k)\le 2^{n-1} \exp (\frac{(n-2k-2)^2}{4(1+k-n)}$$ Lovasz bound is the top one.

n = 50;
gallier[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lovasz[k_] := 2^(n - 1) Exp[(n - 2 k - 2)^2/(4 (1 + k - n))];
ListPlot[Transpose[{gallier[#], lovasz[#]} & /@ Range[0, n/2 - 1]], 
 PlotRange -> All, PlotMarkers -> Automatic]

Jean Gallier gives this bound (Proposition 4.16 in Ch.4 of "Discrete Math" preprint)

$$f(n,k) < 2^{n-1} \frac{{n \choose k+1}}{n \choose n/2}$$

where $f(N,k)=\sum_{i=0}^k {N\choose i}$, and $k\le n/2-1$ for even $n$

It seems to be worse than Michael's bound except for large values of k

Here's a plot of f(50,k) (blue circles), Michael Lugo's bound (brown diamonds) and Gallier's (magenta squares)

n = 50;
bisum[k_] := Total[Table[Binomial[n, x], {x, 0, k}]];
bibound[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lugobound[k_] := Binomial[n, k] (n - (k - 1))/(n - (2 k - 1));
ListPlot[Transpose[{bisum[#], bibound[#], lugobound[#]} & /@ 
   Range[0, n/2 - 1]], PlotRange -> All, PlotMarkers -> Automatic]

Edit The proof, Proposition 3.8.2 from Lovasz "Discrete Math".

Lovasz gives another bound (Theorem 5.3.2) in terms of exponential which seems fairly close to previous one

$$f(n,k)\le 2^{n-1} \exp (\frac{(n-2k-2)^2}{4(1+k-n)}$$ Lovasz bound is the top one.

n = 50;
gallier[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lovasz[k_] := 2^(n - 1) Exp[(n - 2 k - 2)^2/(4 (1 + k - n))];
ListPlot[Transpose[{gallier[#], lovasz[#]} & /@ Range[0, n/2 - 1]], 
 PlotRange -> All, PlotMarkers -> Automatic]

Jean Gallier gives this bound (Proposition 4.16 in Ch.4 of "Discrete Math" preprint)

$$f(n,k) < 2^{n-1} \frac{{n \choose k+1}}{n \choose n/2}$$

where $f(N,k)=\sum_{i=0}^k {N\choose i}$, and $k\le n/2-1$ for even $n$

It seems to be worse than Michael's bound except for large values of k

Here's a plot of f(50,k) (blue circles), Michael Lugo's bound (brown diamonds) and Gallier's (magenta squares)

n = 50;
bisum[k_] := Total[Table[Binomial[n, x], {x, 0, k}]];
bibound[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lugobound[k_] := Binomial[n, k] (n - (k - 1))/(n - (2 k - 1));
ListPlot[Transpose[{bisum[#], bibound[#], lugobound[#]} & /@ 
   Range[0, n/2 - 1]], PlotRange -> All, PlotMarkers -> Automatic]

Jean Gallier gives this bound (Proposition 4.16 in Ch.4 of "Discrete Math" preprint)

$$f(n,k) < 2^{n-1} \frac{{n \choose k+1}}{n \choose n/2}$$

where $f(N,k)=\sum_{i=0}^k {N\choose i}$, and $k\le n/2-1$ for even $n$

It seems to be worse than Michael's bound except for large values of k

Here's a plot of f(50,k) (blue circles), Michael Lugo's bound (brown diamonds) and Gallier's (magenta squares)

n = 50;
bisum[k_] := Total[Table[Binomial[n, x], {x, 0, k}]];
bibound[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lugobound[k_] := Binomial[n, k] (n - (k - 1))/(n - (2 k - 1));
ListPlot[Transpose[{bisum[#], bibound[#], lugobound[#]} & /@ 
   Range[0, n/2 - 1]], PlotRange -> All, PlotMarkers -> Automatic]

Edit For proof, Jean Gallier refers to Lovasz who gives a proof for bound which seems quite on the surface, although numerically it's very close to his bound $$f(n,k)\le 2^{n-1} \exp (\frac{(n-2k-2)^2}{4(1+k-n)}$$ Lovasz bound is the top one.

n = 50;
gallier[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lovasz[k_] := 2^(n - 1) Exp[(n - 2 k - 2)^2/(4 (1 + k - n))];
ListPlot[Transpose[{gallier[#], lovasz[#]} & /@ Range[0, n/2 - 1]], 
 PlotRange -> All, PlotMarkers -> Automatic]