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
4 votes
1 answer
975 views

What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?

Fix integers $V$ and $E_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct ...
blt's user avatar
  • 1,233
4 votes
1 answer
886 views

Existence of triangle-free graphs for regular graphs of degree at most n/2

It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to half the number of vertices (...
Gizem's user avatar
  • 43
1 vote
2 answers
386 views

Lower bound for the size of a family of sets

Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property: $$A_1 \cap B_k = \emptyset, 1 \le k \le m$$ Let $\mathcal{F} = \{A_1 \...
Fabius Wiesner's user avatar