All Questions
9 questions
1
vote
0
answers
180
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
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
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
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
12
votes
1
answer
524
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
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$.
...
- 139
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,\...
- 1,245
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 ...
- 1,129
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) \,...
- 986