User yaroslav bulatov - MathOverflow

Invariants that might determine graph up to isomorphism

2011-01-15T02:11:26Z

Are there any graph invariants which have a reasonable chance of capturing the graph up to isomorphism? In other words, some candidates for a function $f$ such that f(G)=f(H) iff G and H are isomorphic.

For instance, in the case of trees, weighted graph polynomial (U-polynomial) of Welsh/Noble 1999 is a candidate because no counter-example has been found. Are there such candidates for general graphs?

Clarification: I'm interested in examples of functions which capture some graph invariant, are practical to compute, and are not yet proven to assign the same value to a pair of non-isomorphic graphs

Sanov's Theorem and Chernoff bound

2010-08-15T02:18:07Z

Sanov's Theorem (p.292, Thomas/Cover "Elements of Information Theory" (1991)) says that probability of a hypothesis $E$ according to distribution $Q$ is bounded above by

$$(n+1)^k \exp (-n D(P^* \|Q) )$$ where $D$ is KL-divergence, $k$ is the size of sample space and $P^*$ is an element of $E$ closest to $Q$ according $D(\cdot\|Q)$.

This bound is quite loose for small $n$ because when $k=2$ and $E$ is simply connected, Chernoff's bound tells us that the probability is at most the following

$$\exp (-n D(P^* \|Q) )$$

Is there a natural restriction of $E$ that makes the bound above generalize to $k>2$? Alternatively, is there a natural restriction of $E$ and a modification of Sanov's theorem that gives it a similar level of tightness to Chernoff's bound for small n?

Lovasz theta function integrality

2011-03-04T10:28:44Z

Is anything known about Lovasz Theta Function taking integral value in non-perfect graphs? In particular, does integral value of Lovasz theta always coincide with the size of largest independent set?

For instance, graph below is non-perfect, and its Lovasz theta function gives the independence number.

Its true for a few other non-perfect graphs I tried, here's a Mathematica package I used to compute it

Maximal clique intersection graphs

2011-02-10T08:10:06Z

Consider graph $T$ where nodes correspond to maximal cliques of some graph $G$ and two nodes can be connected if corresponding cliques intersect. Clique tree is an example when $T$ is required to be a tree and $G$ is chordal. I'm interested in graphs $T$ when tree/chordal requirements are relaxed, do they come up anywhere?

Motivation: I come across these graphs when looking at approximate decompositions of Ising model entropy, searching for "maximal clique intersection graphs" only gives me literature related to clique trees/chordal graphs

Breaking frustrated loops in list coloring problem

2011-01-09T22:53:44Z

Suppose we have a graph with $n$ vertices and $n$ lists of colors such that no vertex coloring of the graph using colors from given lists is a proper list coloring. We can characterize the obstacle to proper list coloring in terms of frustrated cycles -- simple cycles such that every list coloring of the induced subgraph is improper.

Given graph and set of color lists I'd like to delete a small number of vertices to break a large number of frustrated cycles.

Is anything known about this problem, especially from algorithmic point of view?

How many non-equivalent sections of a regular 7-simplex?

2010-09-20T20:17:23Z

Suppose we have a regular 7-simplex in $\mathbb{R}^8$ defined by vertices <1,0,0,...,0>, <0,1,0,..,0>,...,<0,...,0,1>. A section is a 3-dimensional linear subspace of $\mathbb{R}^8$ that contains simplex centroid and three other points, each of which is a centroid of a non-empty set of simplex vertices. Two sections are equivalent if they are identical spaces under permutation of coordinates. In other words, when some permutation of coordinates is the bijection between two spaces. How many non-equivalent sections are there? Is there an efficient way to enumerate them?

Motivation: visualizing symmetric priors over distributions over 8 outcomes

Update 12/09 I tried an automatic search and got 49 sections, same as Peter Shor below. Here they are. Note that grouping is a bit different since I group sections with or without unexpected centroids together.

No empty vertices:

One empty vertex:

Two empty vertices:

Three empty vertices:

Four empty vertices:

old stuff Here's an illustration of solving this problem for 2-sections of a 3-simplex in 4 dimensions. There seems to be only 2 non-equivalent 2-sections (triangle and square). This solves the problem of visualizing entropy (contour lines) of distributions over 4 outcomes, and I'd like extend it to 8 outcomes.

Second order Taylor expansion to solve system of equations

2010-10-02T21:37:20Z

Suppose you need to solve $f(\mathbf{x})=\mathbf{0}$ where $f:\mathbb{R}^n \to \mathbb{R}^m$, $m,n>1$. Newton's method relies on first order Taylor expansion of f. Where can I find details of analogous method using second order Taylor expansion? I found at least a dozen numerical analysis books which mention this method, but give no details or applications

Do singular values of a point set determine its shape?

2010-12-21T19:47:06Z

Suppose I have $k$ points in $d$ dimensions. Let A be a $k\times d$ matrix with $i$th row giving the coordinates of $i$th point. Do singular values of this matrix have an interpretation as some kind of geometric invariant?

I tried a set of convex point sets formed by centroids of vertices of 8 dimensional 7-simplex, and there were 49 distinct singular value sets, which is the same as the number of such point sets not equivalent under coordinate permutation, obtained by Peter Shor in earlier post, I'm wondering if it's a coincidence

Why are low order Fourier coefficients more important for real-life probability?

2010-11-30T19:02:41Z

Suppose have a probability distribution over space of $n$ binary variables. We can view logarithm of the density as a function $f$ from $\{-1,1\}^n$ to $\mathbb{R}$. Fourier expansion of the $f$ can be viewed as expansion of $f$ in terms of square free monomials.

Given a sample from this density, we'd like to find Fourier coefficients that approximate true density. For real-life densities, fit is usually done by adjusting a small number of low order coefficients to fit the sample and fixing the rest to 0. Why does it work better than adjusting high-order coefficients?

This was inspired by Gil Kalai's question on CSTheory.

Originally I thought it's because real life distributions have high entropy, but it seems that restricting entropy, or any symmetric function of the density is not enough to break symmetry between different coefficients.

Here is a plot of all Fourier coefficients (0th order one dropped) realizable by empirical densities of 20 samples of 2-variable density. Z-axis, corresponds to $x_1 x_2$ term, $x,y$ axes are $x_1$ and $x_2$ terms.

"sum over labelings" representations of graph polynomials

2010-11-20T03:33:00Z

It seems that there's a general way to go from "recursive" definition of a graph polynomials to "subset expansion" formulas.

Furthermore, polynomials with subset expansion formulas often have a representation as a sum over all possible vertex labelings of some "local interactions" model.

For instance, generating function for Eulerian subgraphs becomes Ising model partition function, generating function of independent sets becomes partition function of the hard-core model and Potts model has both "sum over labelings" and "sum over subgraphs" representation.

Are there other interesting examples of graph polynomials with "sum over labelings" representation?
When is it possible to get this representation of a graph polynomial? More specifically, to represent it as a sum over labelings of some quantity that is a product of functions each depending only on the variables corresponding to some edge of the graph. IE, if a graph has edges (1,2),(2,3) the term being summed over has to factor into f(x1,x2)*g(x2,x3)

Motivation: there's a general algorithm to efficiently compute "sum over labelings" for functions decomposing over graph or hyper-graph of bounded tree-width, and it's interesting to see which graph polynomials I can use it for

Numeric equality testing?

2010-11-17T03:37:09Z

Suppose we have two closed-form expressions with $k$ unknowns which are hard to test for equality but easy to evaluate numerically over $\mathbb{R}^k$. One could then approach the problem of equality testing by checking equality numerically at several points. The interesting questions are then -- for which kinds of expressions can you do it, how to pick sampling points and how many points are needed.

Google Scholar gives 0 hits for "numeric equality testing"

Has this kind of problem been studied before? What are the right keywords to search for?

finding set of tree decompositions to cover all pairs of vertices

2010-11-10T05:52:54Z

I first asked this on cstheory.SE but got no reply.

Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How do you efficiently compute $P(X_{i}=X_{j})$ for every pair $(i,j)$?

Fastest known method for counting $q$-proper colorings on grids uses tree decomposition. To extend it to this problem, one needs a set of tree decompositions so that every pair of vertices is contained in some bag. Is anything known about this problem?

Motivation: this is essentially two-point correlation function of Potts model, but also correlation function of self-avoiding walks and few other "all-pairs" problems face the same issue

Connective constant for self-avoiding walks on a skip-chain

2010-11-02T02:04:21Z

Suppose we have an undirected graph with integer valued nodes where $0<|i-j|\le 2$ implies nodes $i$ and $j$ are connected. Let $c_n$ be the number of self-avoiding walks on this graph of length $n$ starting at origin. Define the connective constant as

$$\mu = \lim_{n\to \infty} c_n^{\frac{1}{n}}$$

What is known about $\mu$? This quantity seems to be related to the transition temperature of an Ising model on such graph, has such model been studied?

Derivative of Tutte polynomial at -1

2010-10-24T08:25:34Z

Let Tutte polynomial on graph with edge-set $E$ be defined as follows

$$f(q,v)=\sum_{A\subseteq E} q^{\kappa(A)} v^{|A|}$$

Here the sum is over all subgraphs $A$, $\kappa(A)$ is the number of connected components in $A$, $|A|$ is number of edges in $A$.

Let $$g(q,v)=\frac{\partial}{\partial v} \log f(q,v)$$ $$h(q,v)=\frac{\partial}{\partial v} f(q,v)$$

Is anything known about $g(q,-1)$ or $h(q,-1)$?

(Edit 10/26: actually it's the multivariate Tutte polynomial restricted to all $v$'s being equal, relation to regular Tutte polynomial in Jeremy Martin's answer)

Update 10/24

$f(q,-1)$ is the number of proper $q$ colorings, $h(q,-1)$ is ???, $g(q,-1)$ is their ratio. Below are tables of values of $h(q,-1)$ for paths, cycles, complete graphs. Columns give graph size, $n=3..6$, rows give $q=2..8$

Mathematica code to generate this

Answer by Yaroslav Bulatov for hardness of identifying the number of local maxima for mixture of Gaussians

2010-10-24T16:29:04Z

This year's FOCS paper seems relevant.

"Settling the Polynomial Learnability of Mixtures of Gaussians"

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We give an algorithm for this problem that has a running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians.

Edit 10/25: Suresh has a nice summary of the two papers that appeared on this problem here http://geomblog.blogspot.com/2010/10/focs-day-1-clustering.html

For Ising models on finite graphs, is the gradient of Z (w/r/t coupling and field) easier to compute than Z?

2010-10-08T16:39:01Z

Suppose we have a graph $G$ with $n$ vertices, edgeset $E$, $\mathcal{X}=\{1,-1\}^n$. The partition function of the spin-1/2 Ising model on $G$ is

$$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$$

and its gradient with respect to the coupling and applied field is

$$\nabla Z(J,h)=\left ( \frac{\partial}{\partial J} Z, \frac{\partial}{\partial h} Z \right ).$$

We are interested in computing these quantities to some pre-determined finite precision. Computing $Z$ is hard in general, but easy in special cases, like when $|J|$ is small relative to average degree of the graph.

What can we say about relative hardness of computing $\nabla Z$?

Probability of observing outcome with low individual probability

2010-10-04T20:58:52Z

Suppose I throw k-sided dice n times and want to know the probability $p$ of observing a set of counts with individual probability higher than $x$.

Example, let k=2,n=2, fair dice. Possible sets of counts are (0,2),(1,1),(2,0). Individual probabilities of those counts are 1/4,1/2 and 1/4 respectively. Probability of getting outcome with individual probability above 0 is 1, above 1/4 is 1/2, above 1/2 is 0.

What is the relationship between $p$ and $x$? For k=3, line gives surprisingly good fit

This is a generalization of a related unanswered question

Douglas Zare suggests to think of counts as lattice sites of a random walk and use Central Limit theorem. This suggests that relationship is going to be quadratic for k=5, and indeed, parabola seems to give a decent upper bound in that case

n = 21;
types = Flatten[
   Permutations /@ (IntegerPartitions[n, {3}, Range[0, n]]/n), 1];
prob[p_, q_] := n! Times @@ MapThread[(#1)^(n #2)/(n #2)! &, {p, q}];
cum[p_, cutoff_] := 
  Total[Select[prob2[p, #] & /@ types, # >= cutoff &]];
p0 = RandomChoice[Select[types, FreeQ[#, 0] &]];
pvals = prob[p0, #] & /@ Union[types];
cvals = cum[p0, #] & /@ pvals;
data = Transpose[{pvals, cvals}];
Show[ListPlot[data, PlotRange -> All], 
 Plot @@ {Fit[data, {1, x}, x], {x, 0, Max[pvals]}, PlotStyle -> Red}]

Answer by Yaroslav Bulatov for Inverse formula for counting marginals

2010-09-28T21:15:25Z

The answer is yes, and this is known as Moebius inversion. See Section E.1, p.286 in Graphical models, exponential families, and variational inference.

Answer by Yaroslav Bulatov for Density function for a multivariate Bernoulli-like distribution

2010-09-26T17:35:30Z

You need to specify distribution over your random vector $\mathbf{X}$. If individual components are binary valued, and you only care about positive distributions, it can be written in the following form

$$P(\mathbf{x})=\exp(\theta_0+\theta_1 x_1 + \theta_2 x_2 + \ldots + \theta_{12} x_1 x_2 + \ldots +\theta_{1\ldots k}x_1 \cdots x_k)$$

Now the task is determining the distribution of $P(\mathbf{X}|X_1+\ldots+X_k=n)$, this distribution is related to hypergeometric distribution, described in Percy Diaconis "Algebraic algorithms for sampling from conditional distributions" (equations 1.1-1.4)

Answer by Yaroslav Bulatov for Surface of the cut of an ellipsoid / Marginal density of a multivariate normal over an affine space

2010-09-18T00:06:20Z

I had to do something similar recently and there's a neat trick for integrating Gaussian over linear subspace of $\mathbb{R}^n$ -- write it as an integral over whole $\mathbb{R}^n$ but substitute Dirac measure for regular. Here's overview, and discussion on math.overflow

Optimizing over matrices with spectral radius <1?

2010-09-16T17:58:02Z

Suppose $F(x)$ is a convex objective function on $n\times n$ matrices, and I need to numerically optimize $F$ with the condition that $x$ has spectral radius less than $1$. This might be too hard, so an approximation would be needed. Has this problem been studied before?

Motivation: Boltzmann machines are hard to evaluate when spectral radius of the weight matrix is large, especially if it's above $1$ so best fit to data subject to this constraint would give a useful model.

Example: Let $X=\{1,-1\}^d$ and $\hat{X}$ some list of $\{1,-1\}$ $d$-tuples. Find $$\max_A \sum_{x\in \hat{X}} \mathbf{x}'A\mathbf{x} - |\hat{X}|\log \sum_{x\in X} \exp(\mathbf{x}'A\mathbf{x})$$ Where $A$ is symmetric real-valued $d\times d$ matrix with spectral radius < 1. This needs to be done in time polynomial in $d$ and linear in $|\hat{X}|$. When spectral radius is <1, belief propagation gives a reasonably accurate way to approximate gradient of this objective in $O(|\hat{X}|d^2)$ time

Why doesn't Stein effect happen for multinomial distributions?

2010-09-16T22:20:03Z

(Medeen, et all, 1998)" show that Maximum Likelihood estimate is admissible for multinomial distribution under squared error. On other hand, James and Stein showed that arithmetic average is not an admissible estimator of Gaussian location parameter in 3 dimensions. But since maximum likelihood estimates of multinomial parameters are averages of observed counts, which become normally distributed for large sample sizes, why doesn't Stein effect happen here?

$\hat{p}$ is an inadmissible estimator of $\theta$ if there's an estimator that is no worse for every $\theta$ and better for at least one

coordinates of vertices of regular simplex

2010-09-14T18:38:30Z

For $d=3$, vertex coordinates of a regular simplex have a simple expression since vertices correspond to four vertices of a cube. Is there a simple expression for higher dimensions? In particular I'm interested in $d=2^n-1$, integer $n$.

Edit: by coordinates I mean points in $\mathbb{R}^d$. Every $d$-simplex has a simple expression for coordinates in $\mathbb{R}^{d+1}$, as Mariano shows below

Distribution of transformed multinomial variable?

2010-09-10T22:56:15Z

Suppose we have a uniform multinomial distribution over $2^d$ outcomes. Multinomial coefficients give distribution of vector valued variable $v$ where $v$ is the vector of observed counts.

Is there a combinatorial expression for the distribution of $D v$ where $D$ is a matrix obtained by $d$-fold Kronecker product of $A$, a $(-1,0,1)$ valued 2-by-2 matrix?

Three particular choices of $A$ I'm looking at are

$$A_1=\left(\begin{matrix}1&1\\1&-1\end{matrix}\right)$$ $$A_2=\left(\begin{matrix}1&1\\0&1\end{matrix}\right)$$ $$A_3=\left(\begin{matrix}1&0\\-1&1\end{matrix}\right)$$

Motivation: distribution of $Dv$ corresponds to distribution of feature vectors for three commonly feature bases for exponential families (Walsh, Amari's $\eta$ and Amari's $\theta$ bases respectively)

d = 3;
walsh = KroneckerProduct @@ Table[{{1, 1}, {1, -1}}, {d}];
amariEta = KroneckerProduct @@ Table[{{1, 1}, {0, 1}}, {d}];
amariTheta = KroneckerProduct @@ Table[{{1, 0}, {-1, 1}}, {d}];

Edit: all 3 matrices are invertible, so we just need to multiply by appropriate inverse to get back vector of counts and corresponding multinomial coefficient. Inverse of $D$ is just the Kronecker product of inverses of corresponding base matrices

$$A_1^{-1}=\left(\begin{matrix}1/2&1/2\\1/2&-1/2\end{matrix}\right)$$ $$A_2^{-1}=\left(\begin{matrix}1&-1\\0&1\end{matrix}\right)$$ $$A_3^{-1}=\left(\begin{matrix}1&0\\1&1\end{matrix}\right)$$

Answer by Yaroslav Bulatov for Convergence of a markov matrix

2010-09-09T18:48:08Z

For irreducible Markov chain, necessary condition for convergence is primitivity (ie, all entries of $P^k$ are positive for some k). In a reducible Markov chain, your Markov walker eventually settles into one of $k$ ergodic classes where states inside each class can all reach each other. Hence, reducible Markov chain can be thought of a collection of irreducible Markov chains on a partitioning of the state space, and the limit exists if and only if Markov chain on each of those classes is primitive.

Even if $\lim_{n \to \infty} P^k$ doesn't exist, Cesaro sum always does, ie $$\lim_{n\to \infty} \frac{I+P^1+P^2+\ldots P^n}{n}$$

Columns of this matrix (assuming column stochastic transition matrix) give fraction of time that Markov chain spends in each state eventually

Ch.8 of "Matrix Analysis & Applied Linear Algebra" by Carl Meyer gives more details on these conditions

How big is the sum of smallest multinomial coefficients?

2010-09-03T06:12:33Z

Given positive integers $n$ and $d$, let $S$ indicate the list of all $d$-tuples of non-negative integers $(c_1,\ldots,c_d)$ such that $c_1+\cdots+c_d=n$. Let $v_i$ be the value of the multinomial coefficient corresponding to $i$'th tuple in $S$, ie

$$v_i=\frac{n!}{c_1!\cdots c_d!}$$

What can we say about the sum of smallest coefficients, ie, the value of the following?

$$s(B)=\sum_{v_i < B} v_i$$

Motivation: upper bounds on multinomial tails would allow to give non-asymptotic error bounds for various learning algorithms

Update: 09/03 Here are all the relevant theoretical results I found so far. Let $B=\frac{n!}{c_1!\cdots c_d}$, $C=\max_i v_i$, $k=\min_i c_i$. Then for even n and $d=2$ the following are known to hold

$$s(B)<\frac{B}{C} 2^n$$ Proof under Lemma 3.8.2 of Lovasz et al "Discrete Mathematics" (2003)

$$s(B)\le 2^n \exp(-\frac{(n/d-k)^2}{n-k})$$ Proof under Theorem 5.3.2 of Lovasz et al "Discrete Mathematics" (2003)

$$s(B)\le 2B(\frac{n-(k-1)}{n-(2k-1)}-1)$$ Michael Lugo gives outline of proof in another MO post

$$s(B)<2(\exp(n \log n - \sum_i c_i \log c_i)-B)$$ Proof under Lemma 16.19 of Flum et al "Parameterized Complexity Theory" (2006)

To be practically useful for my application, these bounds need to be tight for tails, ie, for sums that are less than $d^n/10$. Here's a plot of logarithm of bound/exact ratio for such sums. X-axis is monotonically related to B.

You can see that Michael Lugo's bound is by far the most accurate in that range.

Out of curiosity, I "plugged in" bounds above for sums of higher dimensional coefficients.

Mathematica notebook.

Why are multinomial coefficients with same entropy equal? (usually)

2010-09-01T20:56:02Z

Suppose $p_1,\ldots,p_d$ and $q_1,\ldots,q_d$ are positive real numbers such that

$$p_1+\cdots+p_d=q_1+\cdots+q_d=n$$

and

$$p_1 \log p_1+\cdots+p_d\log p_d=q_1 \log q_1+\cdots+q_d \log q_d $$

Then the following seems to hold

$$\frac{n!}{p_1!\cdots p_d!}=\frac{n!}{q_1!\cdots q_d!}$$

why?

Edit: JBL correctly notices that it doesn't always hold. I just didn't go far enough. Still, it's surprising to me that it holds so frequently.

If we put a black disk at x,y if equality seems to hold (in machine precision) for x=n,y=d, and positive integer coefficients, it'll look like this

Red circle is JBL's example. Blue circle is n=18,d=3 which fails for (12,3,3) and (9,8,1).

docheck[n_, d_] := (
   coefs = IntegerPartitions[n, {d}, Range[1, n]];
   entropy[x_] := N[Total[# Log[#] & /@ x]];
   groupedCoefs = GatherBy[coefs, entropy];
   allEqual[list_] := And @@ (First[list] == # & /@ list);
   multinomials = Apply[Multinomial, groupedCoefs, {2}];
   And @@ (allEqual /@ multinomials)
   );
vals = Table[docheck[#, d] & /@ Range[1, 30], {d, 1, 20}];
Graphics[Table[Disk[{n, d}, If[vals[[d, n]], .45, .1]], {d, 1, Length[vals]}, {n, 1, 30}]]

Edit: Updated version that does exact checking and allows coefficients with 0 components. Still only one example of failure for d=3.

docheck[n_, d_] := (coefs = IntegerPartitions[n, {d}, Range[0, n]];
   entropy[x_] := Exp[Total[If[# == 0, 0, # Log[#]] & /@ x]];
   groupedCoefs = GatherBy[coefs, entropy];
   allEqual[list_] := And @@ (First[list] == # & /@ list);
   multinomials = Apply[Multinomial, groupedCoefs, {2}];
   And @@ (allEqual /@ multinomials));
maxn = 30; maxd = 20;
vals = Table[docheck[#, d] & /@ Range[1, maxn], {d, 1, maxd}];
Graphics[Table[Disk[{n, d}, If[vals[[d, n]], .45, .1]], {d, 1, Length[vals]}, {n, 1, maxn}]]

Answer by Yaroslav Bulatov for Why do statistical randomness tests seem so ad hoc?

2010-09-02T18:39:09Z

Kolmogorov complexity is a universal quantity for infinite strings. But since randomness tests are run on finite strings, particular choice of architecture or encoding will play a large role in how the strings will be ordered. A goal of good randomness test designer is to choose an encoding such that strings coming from known random sources (like random.org) are deemed more complex than strings coming from known non-random sources (like pseudo-random generators). Good tests incorporate knowledge of how typical non-random strings are generated, hence the apparent ad hockery.

Answer by Yaroslav Bulatov for Sum of 'the first k' binomial coefficients for fixed n

2010-08-31T21:37:56Z

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]

Bounding sum of multinomial coefficients by highest entropy one

2010-08-16T21:39:47Z

When does the following hold?

$\sum_{(i_1,\ldots,i_k)\in E} \frac{n!}{i_1! \ldots i_k!} \le \exp(n H^*)$

Where

$H^*=\max_{(i_1,\ldots,i_k)\in E} -(\frac{i_1}{n}\log \frac{i_1}{n}+\ldots +\frac{i_k}{n}\log \frac{i_k}{n})$ and E is some subset of {$ {( i_1,\ldots,i_k):i_1+\ldots+i_k=n }$}

Motivation: this is a generalization of Chernoff's bound to n tosses of fair k-sided dice where E represents the hypothesis we make about that sample. Another motivation is reconciling tight special-case Chernoff bound with looser but more general bound given by Sanov's theorem

Examples: when k=2, it can be proven to hold for sets of coefficients where first component of the coefficient is less than n/2 (ie here).

When k=3, it seems (empirically) to hold for sets of coefficients where sum of first two components is ≤n/2. For instance, for n=10, highest entropy term gives upper bound of (2/3)^3 *10^5 whereas exact sum is 12585. Since k=3 multinomial coefficients lie in a 2-simplex, the 21 multinomial coefficients in this set can be visualized below. Top vertex represents coefficient (0,0,10)

For higher k, we can look at similar sets, ie corners of the (k-1) simplex. I tried few values and it seems to hold for coefficients where sum of first k-1 components is below n/(k-1)

Here's how you'd check it in Mathematica

getit[n_, k_, c_] := (
   all = Select[Tuples[Range[0, n], k], Total[#] == n &];
   e = Select[all, Total[Most[#]] <= c &];
   hterm[x_] := If[0 < x < 1, x Log[x], 0];
   H[event_] := -Total[hterm /@ (event/n)];
   exact = Total[Multinomial @@@ e];
   upper = Exp[n Max[H /@ e]];
   exact < upper
);
(* Check bound for k=3, n=10, with i1+i2<=5 *)
getit[10, 3, 5]

Update 8/18 Leandro gives a bound on a single multinomial coefficient which gives Sanov's theorem if we consider that there's at most $(n+1)^k$ multinomial coefficients in any set E. It seems that to generalize the proof of the tighter binomial bound to, say, trinomial coefficients, one would need to prove the following inequality first

$$p_1 \log q_1 + p_2 \log q_2 + p_3 \log q_3 \ge q_1 \log q_1 + q_2 \log q_2 + q_3 \log q_3$$

Where p and q add up to 1. For each q, the set of p's for which the above bound holds also gives us the hypothesis for which we can give tight Chernoff-like bound. Empirically, this bound seems to hold for p's "bounded away" from the uniform distribution. Black circle below represents q, blue region is the set of distributions p where the bound above holds. My Mathematica notebook

Update 8/24: the bound holds for sets of coefficients of the form $i_1 a_1 + \ldots + i_n a_n \le C$ where $a_1\ldots a_n$ are arbitrary non-negative numbers, details in answer

Comment by Yaroslav Bulatov

2011-05-02T18:19:49Z

yes, just finite graphs

Comment by Yaroslav Bulatov

2011-04-27T05:31:05Z

Thanks for reference! I wonder why Shanon/Cover give the looser bound if polynomial term can be dropped

Comment by Yaroslav Bulatov

2011-03-09T21:39:42Z

you could use multi-information, see Bell's "co-information lattice" www.rni.org/bell/nara4.pdf

Comment by Yaroslav Bulatov

2011-03-04T22:25:54Z

I'm interested in clique graphs created by partial triangulations -- I add some chords and look at clique intersection graph where only maximal intersections form edges. The goal is to create such clique graphs where maximal intersections are almost graph separators (any cycle that goes through such set is long). I'm looking for heuristics that lets me find such triangulations while keeping maximum clique size as small as possible

Comment by Yaroslav Bulatov

2011-02-17T23:02:07Z

You could search for literature from "objective Bayesian" community, who focus on principled methods on choosing priors, esp survey papers from people like Wasserman, Berger, Bernardo, Dawid

Comment by Yaroslav Bulatov

2011-02-10T18:38:40Z

By click incidence do you mean connecting nodes whenever some clique contains them both?

Comment by Yaroslav Bulatov

2011-02-10T16:14:15Z

The former, I believe latter would be called "maximum clique"

Comment by Yaroslav Bulatov

2011-02-04T03:16:01Z

There's also the converse, P!=NP but there's algorithm that solves any real-life NP-hard instance in a blink. For instance, SAT is NP-hard, but all SAT instances that "come up in practice" are easy -- rjlipton.wordpress.com/2009/07/13/…

Comment by Yaroslav Bulatov

2011-01-16T08:34:30Z

You can count the number of subgraphs with $m$ edges and $n$ vertices in polynomial time on bounded tree width graphs.

Comment by Yaroslav Bulatov

2011-01-15T03:47:04Z

Useful link, thanks. It's different from this question because it asks for for functions which are known to distinguish graphs up to isomorphism, whereas I'm asking for ones which are not known to NOT distinguish graphs up to isomorphism, ie, the ones which could use a counter-example

Comment by Yaroslav Bulatov

2011-01-10T20:58:02Z

Maybe they are computationally special? Tree decomposition works because we can solve problem on trees, holographic reduction works because we can count perfect matchings on planar graphs

Comment by Yaroslav Bulatov

2011-01-10T19:09:20Z

I realize that breaking all frustrated cycles is probably too hard, so I need to find k nodes that break as many cycles as possible

Comment by Yaroslav Bulatov

2011-01-10T19:07:33Z

I unfortunately don't know any related literature, this is a theoretical example for a practical problem that arises when running a particular message passing algorithm on graph. Frustrated cycles cause convergence problems and I can delete a few nodes and correct for their removal. There's a bounded number of nodes I can afford to remove, so I want to break as many frustrated cycles as possible with that number.

Comment by Yaroslav Bulatov

2010-12-30T23:53:41Z

You get a tree if you connect the origin to every datapoint. Question doesn't really make sense to me

Comment by Yaroslav Bulatov

2010-12-22T04:53:44Z

BTW, I also got 49 sections with an automatic search. A nice surprise is that section corresponding to no empty vertices is a regular octahedron.