All Questions
2,253 questions
1
vote
0
answers
177
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
132
views
How to maximize the variance of a subset of integers?
$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
- 1,372
1
vote
0
answers
78
views
+100
Inequalities for norm of centered Gaussian and uncentered Gaussian
Let $g$ denote a standard Gaussian vector in $\mathbb{R}^n$, and $\|\cdot\|$ a norm.
Let $x \in \mathbb{R}^n$ and define
$$
F(x) = \mathbb{E}[\|x + g\| - \|g\|].
$$
I am wondering if it is possible to ...
- 380
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 ...
CommunityBot
- 1
4
votes
0
answers
55
views
Positivity of elementary symmetric polynomials under linear fractional transformations
The general question
For $1\leq k\leq n$, let $$e_k(a_1,\dots,a_n):=\sum_{j_1<\dots<j_k}a_{j_1}\cdots a_{j_k}$$ be the $k$-th elementary symmetric polynomial.
Let $a_1,\dots,a_n<1$ and $e_1(...
1
vote
0
answers
29
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
0
votes
1
answer
121
views
Inequality for commuting hermitian operators
Let $p_1$ and $p_2$ be a complete system of orthogonal projections on $R^n$, $n\geq 2$ (i.e., $p^2_i=p_i=p^*_i$ and $p_1+p_2=\bf{1}$) and $S_1,S_2$ be two commuting hermitian operators on $R^n$ (i.e., ...
- 109k
2
votes
1
answer
877
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
CommunityBot
- 1
0
votes
0
answers
37
views
Bounding the error of a truncated moment problem
Let $\{x_{i}\}_{i=1}^{\infty}$ be a non-increasing sequence of non-negative real numbers, and let $\{y_{j}\}_{j=1}^{B}$ be a non-increasing sequence of non-negative real numbers, where $B$ is a finite ...
- 433
2
votes
0
answers
101
views
An inequality related to Problem 10210 AMM 1992 No. 3
Problem. Let $A$ be a $N \times N$ real matrix whose $(i,j)$ entry is $a_{ij} \ge 0, \forall i, j$. Let $1$ denote $N\times 1$ all-ones vector. Prove that
$$N^2 1^\top A^\top A A^\top 1 \ge (1^\top A ...
- 1,053
4
votes
4
answers
473
views
A certain inequality involving square roots of polynomials
I want to prove the inequality
$$\begin{aligned}
&\sqrt{(x - 1)^2 + y^2}\Big[y^2(9x - 6) - 9x^2 + 9x^3\Big]+ y^2(16x^2 - 16x + 7)\\
&- \sqrt{x^2 + y^2}\Big[9x + y^2(9x - 3) + \sqrt{(x - 1)^2 + ...
- 785
4
votes
1
answer
388
views
Proofs of inequalities used by Erdos-Renyi in their Random Graphs Paper 1
Please refer to this, it is Erdos-Renyi 1959 paper 1 on Random Graphs. I am currently working on this, but I am stuck on the fifth page, where they use two estimates. More specifically, here's the ...
CommunityBot
- 1
1
vote
1
answer
149
views
Existence of element $(x_0,y)$ in a set of common zeros for all $(x_0,y)$ satisfying system of inequalities
Let $f_1,f_2,\cdots,f_n,g_1,g_2\cdots,g_m\in \mathbb{R}[x,y]$, then define the affine variety and semi-affine variety as follows:
$V(f_1,f_2,\cdots,f_n):=\{(x,y)\in\mathbb{C}^2: f_1(x,y)=f_2(x,y)=\...
CommunityBot
- 1
0
votes
1
answer
92
views
Does point process ordering ever imply conditional intensity ordering?
Let $N$ and $N'$ be regular/non-explosive point processes on $[0,\infty)$. I will take the view that these are collections of random arrival times: $N=(t_n)_{n\in\mathbb N}$ and $N'=(t_n')_{n\in\...
CommunityBot
- 1
0
votes
2
answers
531
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
CommunityBot
- 1
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
1
vote
0
answers
100
views
Prove or disprove that $|(1/\zeta)^{(n)}(x)| \leq \frac{n!}{(x-\frac{1}{2})}$ for all real $x>1$
$|(1/\zeta)^{(n)}(x)| \leq \frac{n!}{(x-\frac{1}{2})}$ for all real $x>1$.
I had this conjecture for a long time. I tried various methods and techniques but they all failed. It might also be wrong ...
- 178
5
votes
2
answers
353
views
Can one show that $(-1)^{n-1} {(1/\zeta)}^{(n)}(x) >0$ for all real $x>1$?
Is it true that $(-1)^{n-1} {(1/\zeta)}^{(n)}(x) >0$ for all real $x>1$ ?
Or in other words can you show that the higher order derivatives of the reciprocal of the Riemann zeta function ...
- 22.5k
4
votes
1
answer
477
views
Prove the following trigonometric inequality
Prove that $$f(x, y) \equiv \arccos\left(\frac{x-y}{K}\right) - \arccos\left(\frac{x-y}{K}+y\right) - \frac{y}{x}\arccos(1-y^2) \ge 0$$
with the constraints:
$K\ge 2$ is an integer,
$g(x, y) = (K-1)...
CommunityBot
- 1
2
votes
1
answer
322
views
Is it possible to find an upper bound and a lower bound for $(f(\xi)-f(\tilde{\xi}))^T(\frac{\partial f}{\partial \xi}(\bar{\xi}))(\xi-\tilde{\xi})$?
For a system engineering problem I have to solve the problem below, but since I am not a mathematician, I am not sure if I have enough knowledge to solve it.
Problem definition: Let $f(\xi) \in \...
CommunityBot
- 1
5
votes
1
answer
323
views
An inequality that may be of isoperimetric nature
I am trying to prove the following inequality: let $f,g:S^1\to R$ (here $S^1$ is the unit circle parametrized by arc-length) be differentiable and have zero mean. Then
$$
4\pi \int f(t) g(t)\, dt \le \...
- 109k
1
vote
3
answers
160
views
Upper Bound for $\mathbb{E}\left[\max_{j \in \mathcal{N}} h_{j}\right]$
Assume $\{h_j\}_{j\in \mathcal{N}}$ are independent Gamma random variables, each with potentially different distributions and parameters. I am looking for an upper bound for $\mathbb{E}\left[\max_{j \...
- 2,183
3
votes
1
answer
594
views
Another functional inequality
Is there some general solution to the functional inequality:
$$ f(xy) \leq y f(x) + x f(y)$$
Where $x,y\in[0,1]$?
I can find many particular solutions but I just wonder if there is a more general ...
CommunityBot
- 1
1
vote
1
answer
63
views
Need bound for absolute value of complex-valued special functions (Taylor coefficients of Faddeeva's w(z))
To guarantee accuracy for code [1] that computes Faddeeva's w(z) [2] using Taylor expansions around different centers, I would need upper bounds for the absolute values $|w_n(z)|$ of the coefficients
$...
- 128k
21
votes
7
answers
2k
views
Identities and inequalities in analysis and probability
Usually, at the heart of a good limit theorem in probability theory is at least one good inequality – because, in applications, a topological neighborhood is usually defined by inequalities. Of course,...
- 109k
0
votes
1
answer
71
views
Upper bound on higher order derivatives of $\frac{1}{v(t)}$
Suppose that $ v(t) >l>0$ and
$$
\vert v^{(k)}(t) \vert \leq c \frac{k!}{r^k}.
$$
Can we give an upper bound for
$$
(\frac{1}{v(t)})^{(k)}
$$
?
Attempt:
We first compute the first fourth order ...
- 128k
5
votes
0
answers
204
views
A proof for an $L^p$-$L^p$ inequality
This is a transfer of the question
https://math.stackexchange.com/questions/4996853/an-lp-lp-inequality
Let $a\in (0,1)$ and $1<p<\infty$ and use $L^{p}$ to denote the space $L^{p}([0,\infty))$ ...
CommunityBot
- 1
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
- 109k
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 ...
CommunityBot
- 1
3
votes
0
answers
90
views
Tighter Freedman's inequality for a special martingale difference sequence
Let $X_{1}, \ldots, X_{T} \in \{0, 1\}$ be a sequence of Boolean random variables with
$$
\mathbb{E}[X_{t} | X_{1}, \dots, X_{t - 1}] = p_{t}.
$$
Consider the sequence $Y_{t} := X_{t} - p_{t}$ (which ...
- 63.9k
-1
votes
0
answers
132
views
Trig conjecture about square roots and Arcsin
Let $r(a,b)$ be a rational number depending on positive integers $a,b$ and $r(a,b)$ being nonnegative. For every $b$ there is an $a$ such that $r(a,b)$ is not $0$.
Let $C(b)$ be a squarefree positive ...
- 769
0
votes
2
answers
364
views
Can one show $\left|\frac{2(\zeta'(x))^2-\zeta''(x)\zeta(x)}{\zeta^3(x)}\right|\leq \frac{2}{(x-\frac{1}{2})^2}$ for $x\in\mathbb{R}\cap [1,\infty)$?
I have found that $\left|\frac{2(\zeta'(x))^2-\zeta''(x)\zeta(x)}{\zeta^3(x)}\right|\leq \frac{2}{(x-\frac{1}{2})^2}$ for all real $x$ such that $x>1$ seems to be true. I have plotted the ...
- 128k
3
votes
1
answer
309
views
Extremizing sequence consists of two elements
Let $\mathcal A_{s}$ be the set of sequences $X=(x_m)_{m \in I}$ where $I=\{1,2,...,n\}$ with $n \ge 2$ and possibly $n =\infty$ is an index set with $x_1=0$, $x_2=s>0$ and $x_m>x_{m-1}$ for $m,...
- 5,409
3
votes
0
answers
57
views
Maximizing a Gaussian quadratic form
Let $u$ denote a fixed unit vector in $\mathbb{R}^n$ and $g$ a standard Gaussian vector (in $\mathbb{R}^n$).
Consider the map
$$
f_n(X) = \mathbb{E} \langle (X^{-1} + gg^T)^{-1} u, u\rangle,
$$
...
- 380
2
votes
3
answers
183
views
Existence and sharpness of Bernstein-type bounds on the moment-generating function
Let $X$ be a centred random variable with variance $\sigma^2$, and whose moment-generating function exists in an open neighbourhood of the origin.
Say that $X$ satisfies a 'Bernstein-type' MGF bound ...
- 128k
6
votes
1
answer
568
views
Can one show that $|\zeta'(x) / \zeta^2(x)| \leq 1/(x-.5)$ for $x\in\mathbb{R}\cap [1,\infty)$?
I have found that $\left|\frac{\zeta'(x)}{\zeta^2(x)}\right|\leq \frac{1}{x-\frac{1}{2}}$ for all real $x$ such that $x>1$ seems to be true. I have plotted the inequality and got this inequality ...
- 105k
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
0
votes
0
answers
57
views
Class of covariance matrices invariant under permutations
I am reading a paper on covariance matrix estimation, and in this paper is introduced a class of covariance matrices:
\begin{equation}
U(q, c_0(p),M)=\{\Sigma: \sigma_{ii}\leq M,\quad \max_j\sum_{j=1}^...
- 1
2
votes
1
answer
288
views
How to estimate an integral by the variation and upper bound of the integrand?
Suppose that $f$ is a continuous function on $\mathbb{R}$. I want to estimate the definite integral
$$ I:= \int_{0}^a [f(x)-f(0)]dx $$
by the upper bound $M = \sup_{x\in[0,a]}|f(x)|$ and the variation ...
CommunityBot
- 1
1
vote
0
answers
155
views
How to solve this Aczel-like inequality?
Suppose $n$ is a positive integer, $x_i \geq 0$ and $\alpha >\beta >0$, is the following inequality true ?
$\left ( \frac{\left ( \sum_{i=1}^{n} x_{i}^{\alpha} \right )^2-\left ( n-1 \right )\...
- 128k
21
votes
3
answers
2k
views
Trigonometric inequality
For odd and coprime positive integers $p$ and $q$, the following inequality holds:
$$\sum_{m=1}^{p} \sum_{n=1}^{q} \frac{2}{\cos(\frac{2m\pi}{p})+\cos(\frac{2n\pi}{q})} \le pq(|p-q|+1)$$
Unfortunately,...
- 109k
1
vote
1
answer
180
views
Interpolation of scalars
For $a,b$ and $\alpha_i, \beta_i $ where $ i \in \{ 1,2 \} $, are non-negative real numbers, is it possible to find a constant $C$ such that
$$(\alpha_1 a + \beta_1 b) ^{(1-\theta)} (\alpha_2 a + \...
CommunityBot
- 1
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
CommunityBot
- 1
1
vote
1
answer
124
views
$d(x,y) = \min\{|x_1−y_1|+|x_2−y_2|, 1−|x_1−y_1|+|x_2−(1−y_2)|\}$ defines a metric on $[0,1)\times[0,1]$? [closed]
For $x,y \in [0,1)\times[0,1]$, let $d(x,y)$ be the minimum of $|x_1−y_1|+|x_2−y_2|$ and $1−|x_1−y_1|+|x_2−(1−y_2)|$. Prove or disprove that $d$ is a metric.
I was unable to find a counterexample to ...
- 109k
2
votes
0
answers
214
views
A conjectured generalization of Marcus's inequality
Note: I have edited the post below in order to include sharper (conjectured) inequalities, using $|H_1 \cap H_2|$.
Let $[n] = \{1, \dots, n\}$ and let $\sim$ be an equivalence relation on $[n]$. Then $...
- 5,215
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 63.9k
1
vote
1
answer
701
views
Hanson-Wright inequality (quadratic form concentration inequality) for bounded random vectors
Is there a concentration inequality for quadratic forms of bounded random vectors $X \in [-1, 1]^n$ with zero mean and given covariance matrix $\Sigma \in \mathbb{R}^{n \times n}$ but otherwise ...
CommunityBot
- 1
-2
votes
1
answer
141
views
Prove the function $g(x,y,t)\ge1$
I have the function
$$
g(x,y,t)=\frac{(8x^2y^2+f_+(x,y,t)-\cos(2t))(8x^2y^2(1+(x+y)^2)+(x+y)^2(f_-(x,y,t)-\cos(t))+4xy(x+y)\sin(2t))}{64x^4y^4(1+(x+y)^2)}
$$
with
$$
f_{\pm}(x,y,t) = 1+2x^2+2y^2\pm4xy\...
- 128k
4
votes
1
answer
800
views
Bound the operator norm of the Fréchet derivative of a Lipschitz function in this setting
I want to find a bound for the operator norm of the Fréchet derivative of a Lipschitz continuous function in the following setting:
Let
$E$ be a $\mathbb R$-Banach space;
$v:E\to[1,\infty)$ be ...
CommunityBot
- 1