4
votes
3answers
276 views

Lower bound for sum of square root of the degrees of a connected graph

By Cauchy-Schwartz and the handshake lemma, it is easy to see that $\left( \sum_{i=1}^n \sqrt d_i \right)^2 \leq n \sum_{i=1}^n d_i =2mn$, with equality iff the graph is regular (constant degree). ...
0
votes
0answers
67 views

Approximate closed-form solution for a recurrence

Find an (approximate) closed-form solution for $S(m, b)$. $$S(m,b)=\sum_{i=0}^{\lfloor (e-1)/2\rfloor}{e \choose i}S(m-1, b-i) \quad + \sum_{i=\lfloor (e-1)/2\rfloor+1}^{\min(b,e)}{e\choose ...
4
votes
1answer
373 views

Hilbert Matrix and Approximation Theory

I was reading about the Hilbert matrix and Cauchy determinants: \[ \det \left[ \frac{1}{i+j-1} \right]_{i,j} \] By guessing where this determinant is $0$ or $\infty$ we can guess the right formula. ...
3
votes
2answers
357 views

battleship permutation

Consider the following one-dimensional version of the game battleships. There is a battleship somewhere on $\mathbb N$, i.e., a interval $N,\ldots,N+k$. Your task is to find whether this battleship ...
0
votes
0answers
385 views

Decomposing max-convolution of sum of functions ?

Hello. $R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100. $R$ is a linear combination of $F_1, F_2, F_3$. Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$ where ...
7
votes
2answers
204 views

Well-balanced covering of transpositions in $n$ elements

Let me denote $X_n$ the set of transpositions in $n$ elements. Equivalently, $X_n$ is the set of doubletons in $[1,n]\times[1,n]$. The cardinality of $X_n$ is $N=\frac{n(n-1)}{2}$. If $f:{\mathbb ...
10
votes
0answers
480 views

Once differentiable, piecewise degree three polynomials on triangulated planar domains

Here is an easily described, but very difficult, problem that I (and a number of other people) really would like to see solved during our life times. The basic problem is to compute the dimension of ...
5
votes
6answers
2k views

Fast evaluation of polynomials

Hello everybody ! I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
5
votes
4answers
904 views

Determining a recurrence relation

I would like to solve the general problem of determining a linear recurrence relation that fits a given integer sequence of length $n$, or stating that none exists (with fewer than $n/2-k$ ...
0
votes
0answers
273 views

Estimating a multinomial sum

I have the following sum \begin{equation} \sum_{r_1=q+1}^{\tau}\dots\sum_{r_\lambda=q+1}^{\tau}{\tau\choose r_1,\dots,r_\lambda,\tau-r_1-\dots -r_\lambda} (\Lambda-\lambda)^{\tau-r_1-\dots-r_\lambda} ...
2
votes
4answers
184 views

How to compare finite point sets in normed spaces?

I want to define a "distance" between two subsets $A, B$ of a normed space $(V, \|\cdot\|)$ both with (at most) $n$ elements. A straightforward way for me to do this would be to define $$ d(A, B) := ...
1
vote
1answer
298 views

Distribution on permutations derived from probability of pairwise orderings

A followup question to Probability estimates for pairwise majority votes - I think it doesn't actually give an answer in any terribly precise sense, but it would give something I'd be happy to use in ...
1
vote
2answers
1k views

Algorithmic aspects of maximizing a convex function over a convex set

Motivation The problem I am facing can be considered a variant of the standard set packing problem. However; instead of being given a list of sets, I am given a function $\nu : 2^N \rightarrow ...