All Questions
Tagged with co.combinatorics inequalities
93 questions
2
votes
1
answer
208
views
Proving an exponential sum inequality for symmetric Hamming distance sequences in binary vectors
Background: Let $X = \{0,1\}^k$ represent the set of all binary vectors of length $k$. For two binary vectors $x, y \in X$, the Hamming distance $d_H(x, y)$ is defined as the number of positions where ...
- 349
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
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
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
11
votes
2
answers
425
views
Maximization of a cubic form over the $14$-dimensional sphere
For any integers $i$ and $j$ such as $1\le i<j\le6$, let $x_{ij}$ be a nonnegative real number.
Is it true that, given the condition
$$\sum_{1\le i<j\le6}x_{ij}^2=1,$$
the sum
$$\sum_{1\le i<...
- 128k
2
votes
1
answer
754
views
On a combinatorial inequality
Is it true that
\begin{gather}
\min\left(\lambda_{\min}(M_{12}), \lambda_{\min}(M_{13}), \lambda_{\min}(M_{14}), \lambda_{\min}(M_{15}), \lambda_{\min}(M_{23}), \\ \lambda_{\min}(M_{24}), \lambda_{\...
- 178
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
1
vote
0
answers
185
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
3
votes
1
answer
272
views
An inequality about factorial function
Let $d,s,k$ be integers such that $d<s+2$, $s=o(k)$. For sufficiently large integer $k$, is the following inequality right?
$$\frac{(k-2d+1)^{k+s-d}}{(k-d)!\cdot (k-2)_s} \ge 1$$
We write $(k)_s = ...
- 91
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
2
votes
1
answer
184
views
Estimating ${\left(\sum_{i=j}^k {x_i}\right)^2} \times \left\lvert\sum_{i=j}^k {a_i}\right\rvert$
Given two sets; $X = \{x_i : x_i \geq 0; i \in [\sqrt{n}]\}$ and $A = \{a_i : |a_i| \leq 1; i \in [\sqrt{n}]\}$ of size $n^{\frac{1}{2}}$ each, with the following properties
\begin{equation}\label{...
- 23
4
votes
1
answer
427
views
Inequality of inclusion-exclusion term
This question was initially posted on math.stackexchange.com but did not receive any answers for half a week.
While analyzing the properties of an algorithm I am working on (I'm a computer scientist), ...
- 45
6
votes
1
answer
372
views
Maximizing a sum minus its maximal summand
This is a followup to a question that appeared on m.SE:
Maximize $\displaystyle f(\pi)=\left(\sum_{i=1}^{n}{i\pi_i}\right)-\max_{1\le i\le n}{(i\pi_i)}$ over permutations $\pi\in S_n$.
The problem ...
- 1,190
3
votes
2
answers
459
views
Short sequence beats long sequence
I have encountered some comparison between two binomial sums. It was amusing how the one with "fewer" summands exceeds (in value) than the other which consists of many more terms. In fact, ...
- 43.2k
8
votes
1
answer
412
views
Big triples in a matrix
Consider an $n\times n$ real matrix $A=(a_{ij})$ with non negative entries. Assume that
- the sum of the three largest entries in each row is a constant $R$ (the same for all rows),
- the sum of the ...
- 5,103
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
3
votes
2
answers
255
views
Inequality for Gaussian polynomials III
Recall the constructions $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ with $[0]!_q:=1$ and the $q$-binomials (Gaussian polynomials)
$$\binom{n}k_q=\frac{[n]!_q}{[k]!_q[n-k]!_q}.$$
Given two ...
- 43.2k
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
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
9
votes
2
answers
354
views
Asymptotics of a quadratic recursion
Consider the sequence defined by
\begin{align}
c_0 &{}= 1 \\
c_n &{}= 2\,n\,c_{n-1}-\frac{1}{2}\sum_{m=1}^{n-1}c_m\,c_{n-m}.
\end{align}
How can you prove that it has the following asymptotics ...
5
votes
1
answer
258
views
Dimension reduction for non-negativity of elementary symmetric polynomials
Fix integers $1 \leq k \leq n$ and suppose $\mathbf{x} \in \mathbb{R}^n$ is such that $e_j(x_1,x_2,\ldots,x_n) \geq 0$ for all $1 \leq j \leq k$, where $e_j$ is the $j$-th elementary symmetric ...
- 6,351
23
votes
1
answer
1k
views
Symmetric polynomial inequality arising from the fixed-point measure of a random permutation
A somewhat strange elementary polynomial inequality came up recently in my work, and I wonder if anyone has seen other things that are reminiscent of what follows.
Given $n$ non-negative reals $a_1, ...
- 543
1
vote
1
answer
474
views
Compare AM and GM
\begin{gather*}
M_g=(x_1\times x_2\times\dotsb\times x_n)^{1/n} \\
M_a=\frac1 n\times (x_1+x_2+\dotsb+x_n).
\end{gather*}
Is it true that $$\lvert M_g-M_a\rvert \leq (\max(x_i) /\min(x_i)) \times(\max(...
- 4,074
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
15
votes
2
answers
788
views
Combinatorial inequality involving alternating signs
I would like to prove the following inequality. It arises from my study of random matrices.
I have verified the inequality for $q\in \{0.01,0.02, \ldots, 0.99\}$ and $1\le n\le 100$.
Let $n$ be any ...
- 155
4
votes
2
answers
304
views
High degree differences in bipartite graphs
Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us define the quantity:
$$\mathcal{I}_k(G) := \sum_{1\le i,j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v_i)-\...
user153000
1
vote
1
answer
207
views
Expectation of the sum of the squares of the cardinal of an inverse function
I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as:
$$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$
where $\oplus$ is the bitwise XOR.
...
- 167
9
votes
3
answers
446
views
Pairs of vertices with high degree difference
Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us also fix an integer $k> n/2$. What are we able to say about the following quantity:
$$\mathcal{I}_k(G) :=...
user153000
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},
$$
...
1
vote
0
answers
150
views
How should the first n natural numbers be arranged in a circle to minimize the sum of the products of adjacent pairs? [closed]
I was able to find (and prove) arrangements that would result in the sum of the products of adjacent pairs attain the maximum.
I am able to conjecture that the arrangement that would result in the ...
- 11
2
votes
1
answer
168
views
Approximation of a quadratic map by using a limited binary representation
We are given the sequence defined by the recurrence relation $a_{n+1}=a_n^2+1$ with $a_0=0$.
Let $h$ be a positive integer (it represents the maximum number of bits, up to a constant factor, that we ...
- 1,677
3
votes
1
answer
143
views
Combinatorial Euclidean geometry problem
Let $\mathcal{S}^d_{\epsilon}$ be the collection of all sets $S:=\{\mathbf{x}_1, \mathbf{x}_2, \ldots \mathbf{x}_{d+1}\}$ of $d+1$ points in a $d$-dimensional Euclidean space such that, for a given ...
- 1,677
12
votes
1
answer
525
views
An inequality about unit vector orthogonal to $(1,1,...,1)$
Does there exist a constant $\alpha>0$ such that the following holds?
$$\liminf_{n\to\infty}\inf_{x\in\mathbb{R}^n, \sum_{i=1}^nx_i^2=1, \sum_{i=1}^nx_i=0}\frac{\sum_{i<j, |i-j|\leq\frac{n}{4}}(...
- 1,495
2
votes
1
answer
404
views
Euclidean distance bound with geometric constraints
Let $S_n$ be a set of $n$ points belonging to $\mathcal{B}_d:=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{x}\|_2\le 1\}$, where $d\ll \log(n)$.
Let $s_n$ and $\ell_n$ be respectively defined as follows:
$$...
- 1,677
0
votes
1
answer
340
views
Expectation of the ratio of two discrete random variables with combinatorial constraints
We are given a set $S=\{1, 2, \ldots, n\}$ where $n\gg 1$, and for all indices $1\le i \le n$, $i$ is associated with a real value $\alpha_i\!\cdot\! v_i$, where $\alpha_i\in[0,1]$ and $v_i\in(0,1]$.
...
- 1,677
0
votes
1
answer
60
views
Bounding the ratio of the $\ell_1$-norms of two real-valued $n$-vectors as a linear combination of their $n$ element-wise ratios
Let $a_1, a_2, \ldots a_n$ and $b_1, b_2, \ldots b_n$ be two sequences of $n\gg 1$ real numbers such that, for all $1\le i\le n$, we have $0<a_i \le b_i\le 1$. Let the ratio $R$ defined as follows:
...
- 1,677
1
vote
1
answer
181
views
Optimization problem with definite integral inequality constraints
Question: How can we prove that there exists a real constant $c\ge 1$ such that the following inequality holds for all integers $d>1$ and all real numbers $r\in\left[1,\sqrt{d}\right]$?
$$\int_{-1}^...
- 1,677
10
votes
1
answer
205
views
Disjoint sets with twice ratio
Given are a positive integer $n$ and positive real numbers $a_1,\dots,a_n,b_1,\dots,b_n$. A subset $S\subseteq N=\{1,\dots,n\}$ is called $a$-good if $$\sum_{i\in S}a_i\geq \frac{1}{2}\left(\sum_{i\in ...
- 1,209
2
votes
1
answer
276
views
Combinatorial optimization problem on sums of differences between real numbers
We are given an increasing sequence $S$ of positive real numbers $x_1, x_2, \ldots, x_n$, such that $$x_{i+2}-x_{i+1} \ge c\,(x_{i+1}-x_i)$$ for all $i=1, 2, \ldots n-2$, where $c\ge 1$ is constant. ...
- 1,677
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 ...
3
votes
1
answer
229
views
Inequality for difference of consecutive atom probabilities for binomial distribution
Edit: This post was originally two questions, the first of which has been answered, but a reference would still be appreciated if existent. The second question has been removed and migrated to its ...
- 2,720
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
4
votes
1
answer
100
views
Combined identity perturbation
I found the interesting inequality when I study hypergraph 2-coloring
$$\sum_{i+j=k} \binom{r-1}{i}\binom{r-1}{j}(1-p)^i(1+p)^j \leq \binom{2r-2}{k}$$
$0\leq i, j < r$, $0\leq p \leq 1$. I want to ...
- 317
2
votes
3
answers
365
views
Is this number theoretic quantity bounded above?
I am considering a combinatorial argument which involves the following quantity. We use the prime counting function $\pi(n)$ and to save on exponents we set $h=\pi(n/2)$. The quantity as a function ...
- 13k
1
vote
2
answers
50
views
Cyclic inequality for 2 dimensional simplex elements
Let $p=(p_{1},p_{2},p_{3})\in\Delta$, with $\Delta:=\lbrace p\in(0,1)^{3}\ |\ p_{1}+p_{2}+p_{3}=1 \rbrace$. I aim to prove (not knowing whether it is true though) that
\begin{equation}
p_{1}^{p_{3}-p_{...
- 289
2
votes
1
answer
192
views
Every element of $A$ and $B$ differ in at least $k$ positions
Let $m,n$ be positive integers, $m,n>1$ and $X = \{(x_1,x_2, ..., x_m) \in \mathbb{Z}^m :1 \le x_i \le n, \forall 1 \le i \le m\}$.
$A$ and $B$ are two disjoint subsets of $X$, such that if $a \in ...
- 3,153
4
votes
1
answer
111
views
Upper bound for an expression for distributive lattices
Let $L$ be a finite distributive lattice with minimum $0$ and Maximum $1$ and join-irreducible elements $j_1,...,j_l$ and meet irreducible elements $m_1,...,m_l$.
Let $J_L:= \sum\limits_{i=1}^{l}{| [...
- 26.5k
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
0
votes
1
answer
181
views
Bounding information of expression
Cross posted to theory exchange - https://cstheory.stackexchange.com/questions/45610/bounding-information-of-expression
Suppose $u_1,\ldots,u_n$ are uniformly iid in $\{0,1\}$.
Let $x_1,\ldots,x_n$ ...
- 515
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