Skip to main content

All Questions

Filter by
Sorted by
Tagged with
23 votes
3 answers
3k views

Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality? Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has $$ \int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) \,...
Yufei Zhao's user avatar
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}}(...
neverevernever's user avatar
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) :=...
user avatar
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)-\...
user avatar
3 votes
1 answer
222 views

Intuition for inequality involving permutation and Hamming Cube

Let $C^n=\{0,1\}^n$ be a metric space (Hamming Cube). The distance on $C^n$ is defined by $$ d(\varepsilon,\varepsilon'):=|\{j:\varepsilon_j\ne\varepsilon'_j\}|, $$ $\varepsilon=(\varepsilon_1,\...
BigbearZzz's user avatar
  • 1,245
1 vote
1 answer
66 views

Inequality about the minimum vertex degree in $k$-uniform hypergraphs

Let $H=(V,E)$ be a $k$-uniform hypergraph with $n$ vertices, that is, $V:=V(H)$ is a $n$-element finite set of vertices and $E:=E(H)\subset\binom{V}{k}$ is a family of $k$-element subsets of $V$. ...
Frank Z.K. Li's user avatar
1 vote
0 answers
182 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$ ...
Yuhang Bai's user avatar
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 ...
David's user avatar
  • 11
0 votes
1 answer
397 views

Forbidden Tripartite Graphs

I was looking at extremal graph theory. I have understood the proofs of upper bounds for the Zarankiewicz problem which basically states: What can you say about the edges of a graph with $n$ vertices ...
Halbort's user avatar
  • 1,129