# Tagged Questions

**4**

votes

**3**answers

296 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

**0**answers

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

**1**answer

399 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

**2**answers

362 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

**0**answers

402 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

**2**answers

205 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

**0**answers

483 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

**6**answers

3k 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

**4**answers

930 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

**0**answers

275 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

**4**answers

185 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

**1**answer

302 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

**2**answers

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 ...