All Questions
Tagged with co.combinatorics inequalities
28 questions with no upvoted or accepted answers
11
votes
0
answers
387
views
Inequality for symmetric polynomial functions of log concave variables
Let $(x_i)_{i \ge 1}$ be a log-concave (resp. log-convex) sequence of non-negative real variables. In other words, for $i \ge 2$, we have $x_i^2 \ge x_{i-1}x_{i+1}$ (resp. $x_i^2 \le x_{i-1}x_{i+1}$).
...
- 505
11
votes
0
answers
291
views
$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan
There are $n$ positive real numbers. We partition these numbers into $m$ parts, the size of each part is the sum the numbers in this part. Maximum size of the parts is called a makespan of a partition....
- 399
9
votes
0
answers
365
views
How to count integer lattice points close to a subspace of $\mathbb R^n$?
Consider $m$ linearly independent vectors in $n$-dimensional Euclidean space, $v_1,...,v_m \in \mathbb R^n$ where $1\leq m<n$, and let $U := {\rm span}(v_1,...,v_m)$ denote the $m$-dimensional ...
- 686
8
votes
1
answer
531
views
How large can the dimension of a 'Span of powers of a finite field basis' be?
Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
- 89
6
votes
0
answers
171
views
An inequality involving integer partitions
For integers $n\ge k\ge0$, let $p(n,k)$ denote the number of ways to write $n$ as a sum of $k$ positive integers (repetition allowed). For example, $p(6,3)=3$ since
$$6=1+1+4=1+2+3=2+2+2.$$
QUESTION. ...
- 15.6k
6
votes
0
answers
381
views
An inequality related to the numbers of faces of polytopes with d+2 facets
I would like to prove an inequality related to the number of $k$-faces of two $d$-polytopes with $d+2$ facets; see (1) below.
Let $r>0$, $s>0$, $t\ge 0$, and $d\ge 2$ be such that $d=r+s+t$. We ...
6
votes
0
answers
132
views
Q-analogue of an inequality
Pick integers $b\geq a \geq 0$ and $k\geq j\geq 0$.
It is not super-difficult to prove the inequality
$$
\binom{kb}{ka}^j \geq \binom{jb}{ja}^k.
$$
This is actually quite a nice inequality that was ...
- 15.8k
6
votes
0
answers
630
views
Counting permutation matrices in 0,1,2 matrices
Let $M$ be a matrix with entries equal to 0, 1 or 2, such that all of the row and column sums are equal to $c$.
The Van der Waerden bound gives (roughly) the following bound on the permanent of $M$:
...
- 1,633
5
votes
0
answers
183
views
On the polynomials $\sum_{k=0}^n\binom{n+k}k^m q^k$
A sequence of polynomials
$$P_0(q),\ P_1(q),\ P_2(q),\ \ldots$$
with real coefficients is called $q$-log-convex if for each $n=1,2,3,\ldots$ every coefficient of the polynomial $P_{n+1}(q)P_{n-1}(q)-...
- 15.6k
5
votes
0
answers
167
views
Bounding elementary symmetric polynomials away from zero
Let $2 \leq m \leq n$ be integers and let $\mathbf{x} \in \mathbb{R}^n$ (importantly, I am not assuming that the entries of $\mathbf{x}$ are non-negative). The elementary symmetric polynomials are ...
- 6,351
5
votes
0
answers
295
views
inequality in a shape of inclusion exclusion formula
I have two inequalities to show, both of which describe some probabilities. First I know how to handle, and it follows from applying arithmetic-harmonic mean inequality:
consider 9 numbers $a_1,a_2,...
- 341
3
votes
0
answers
214
views
A family of polynomials related to integer partitions
For a positive integer $n$, let $p(n)$ be the number of partitions of $n$.
For $1\le k\le n$, let $p(n,k)$ denote the number of partitions of $n$ having exactly $k$ terms; in other words, $p(n,k)$ is ...
- 15.6k
3
votes
0
answers
190
views
Stirling number, Delannoy number, and binomial coefficients in a sum
I want to compute/prove that the following sum is positive:
$$ \sum_{i = 0}^n \left[\frac{D(n - i, i)}{d} \sum_{j = m}^d s(d, j) \binom{j}{m} (d - i)^{j - m}\right] > 0
$$
where $s(d, j)$ is the ...
- 51
3
votes
0
answers
203
views
A connection between the Bell numbers and Bell polynomial
Let $B(n,x) = \sum_{k=0}^n {n\brace k}x^k$ be the Bell polynomials and $B_n = B(n,1)$ be the Bell numbers.
I recently proved a nice relation between the two:
$$
B(n,x)^{1/n}/x \ge B_{n/x}^{x/n},
$$
...
3
votes
0
answers
155
views
Frobenius inner product of a zero line-sum matrix and a doubly stochastic matrix
Let $A$, $B$ be two $n\times n$ real matrices.
Let $A$ be a zero line-sum matrix where each row sum and each column sum equals zero, i.e., $$\sum_{i=1}^{n}a_{ij}=\sum_{j=1}^{n}a_{ij}=0 $$ (it seems ...
- 71
2
votes
0
answers
80
views
Inequality on polynomials
Recall $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ and the Gaussian polynomial $\binom{a}{b}_q=\frac{[a]!_q}{[b]!_q[a-b]!_q}$ with $[0]!_q:=1$.
Given two polynomials $U(q)=\sum_k\alpha_kq^...
- 43.2k
2
votes
0
answers
155
views
Deodhar's inequality: when the equality holds?
Let $(W,S)$ be a Coxeter system, $T=\bigcup_{w\in W}wSw^{-1}$ and $\ell$ be the length function.
It is well-known that one have the following Deodhar's inequality:
Let $x\le y\le w$. Then
$|\{r\...
- 1,875
2
votes
1
answer
189
views
Tighter lower bound of the lower triangular sum of an arbitrary Latin square
In this math.stackexchange.com question I seek a tighter bound than the one I presented in there in the question. Rob Pratt puts forth a conjecture in his answer motivated by the dual problem of the ...
- 2,239
2
votes
0
answers
58
views
Bounds for $\sum_{t=1}^Tn_t(s_t)^{-\alpha}\mu(s_t)$ where $n_t(s) = \sum_{1 \le t' \le t} 1_{\{s_{t'}=s\}}$ for $s \in [k]$ and $\mu \in \Delta_k$
Disclaimer: I'm not certain this is the right venue for this post, but I'll give it a try...
So trying prove some bounds in my ongoing work in theoretical reinforcement learning, I encountered the ...
- 6,853
2
votes
0
answers
125
views
Can this sum be majorized?
Suppose that, we have some real numbers $r_1,r_2,\dots,r_m \in [0,1]$; and we study a sum,
$$
S_1= \sum_{i=1}^m \binom{m}{i}(-1)^{i-1}f(r_i),
$$
for $f:[0,1]\to[0,1]$ a concave bijection. Now, take ...
2
votes
0
answers
204
views
Non-uniform Ray-Chaudhuri-Wilson (generalized Fisher's inequality)
A $t$-design on $v$ points with block size and index $\lambda$ is a collection $\mathcal{B}$ of subsets of a set $V$ with $v$ elements satisfying the following properties:
(a) every $B\in\mathcal{B}$ ...
- 20.2k
1
vote
0
answers
184
views
+50
A question relates to edge chromatic-polynomial
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
The edge chromatic polynomial $ech(G, k)$ gives the number of proper edge coloring of the $G$ with $k$ ...
- 91
1
vote
0
answers
105
views
Does this inequality follow from doubly log-concave?
On a sequence $(a_k)_{k\geq0}$ of positive integers, define the operator $\mathcal{L}a_k=a_k^2-a_{k-1}a_{k+1}$. Then, $(a_k)_k$ is called log-concave if $\mathcal{L}a_k\geq0$ for all $k\geq0$.
One may ...
- 43.2k
1
vote
0
answers
86
views
Lower bound the ratio of the combinatorial quantities
Suppose $p < q$, $s = p^{d}$ for some fixed $d \in (0,1)$, let $p$ goes to infinity, define the following quantity,
\begin{aligned}
\quad f(j) = \sum_{i = 0}^{\min(j,s)}{s \choose i}{p-s \choose i}{...
- 515
1
vote
0
answers
399
views
Bounding a sum of binomial coefficients in terms of 'the next one'
I need to bound a sum of a portion of binomial coefficients in terms of "the next one", and understand what is the best which can be said in this sense.
Given a real number $t \geq 2$, call $P(t)$ ...
- 731
0
votes
0
answers
131
views
Estimating when does a certain binomial sum exceed an upper bound
Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers
$$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$
For example $f_{n,0} = 1,f_{...
- 3,463
0
votes
0
answers
103
views
An upperbound related to inductively reducing a set by adding the two least elements
I hope this is not too trivial to be asked here, but here it goes anyway. This is just out of curiosity (regarding a problem with graphs but I have "reduced" it to the problem below:)
Let $S_0={\{a_1,...
- 443
-1
votes
1
answer
76
views
Transforming random variables for having good property?
For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that
\begin{align}
\Omega&\triangleq \{(x,y): A(x,y)=1\},\\
\Lambda&\triangleq \{x: B(x)=1\}.
\end{...
- 287