All Questions
Tagged with extremal-graph-theory co.combinatorics
10 questions
19
votes
4
answers
1k
views
Minimal graphs with a prescribed number of spanning trees
As it's long ago since Erdős died and MathOverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem that I ...
- 3,463
16
votes
1
answer
596
views
Spanning trees: the last darn $1/4$
Let $\Gamma$ be a connected graph. By (Kleitman-West, 1991),
if every vertex of $\Gamma$ has degree $\geq 3$, then $\Gamma$ has a spanning
tree with $\geq n/4+2$ leaves, where $n$ is the number of ...
- 20.2k
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
13
votes
0
answers
741
views
Is there a weak strong regularity lemma?
A famous strengthening of Szemerédi's regularity lemma, due to Alon, Fischer, Krivelevich and Szegedy, allows one to partition a graph into a bounded number of pieces in such a way that not only are ...
- 29k
6
votes
3
answers
443
views
Number of trees with the same matching number
Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.
I have been trying to compute the value of $\...
- 201
4
votes
1
answer
976
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 ...
- 1,233
4
votes
1
answer
887
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 (...
- 43
3
votes
1
answer
158
views
Sharp upper bound of the number of edges for graphs of thickness two
A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
- 1,075
1
vote
2
answers
391
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 \...
- 700
0
votes
1
answer
118
views
Matching book embedding of Cartesian products of graphs
In the book embedding of a graph $G$ , each vertex of $G$ is placed on the spine and each edge is placed in the pages without crossing each other edge. If vertices have degree at most one in each ...
- 767