15
votes
Accepted
Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)
Before giving a very short Cauchy-Schwarz inequality proof for the 3-edge path (can be done in a similar fashion for any tree), let me comment on the authorship of the inequality in question.
In 1959, ...
14
votes
Accepted
Spanning trees: the last darn $1/4$
Consider connected $G$ with $n$ vertices of degree $\ge 3$ and exactly one vertex $v$ of degree 1. Take an extra copy $G'$ of $G$ with $v'$ being its vertex of degree 1.
Now identify $v$ and $v'$ to ...
- 36.9k
12
votes
Accepted
Graph in which no cycle has two crossing chords
Thomassen and Toft [JCTB 31(2):199-224, 1981] showed that any graph with minimum degree at least 3 contains a cycle with two crossing chords from neighbouring vertices on the cycle. The $2n-3$ upper ...
- 1,222
11
votes
Accepted
The maximum number of edges in an even-cycle-free graph with $n$ vertices
The answer is $\lfloor \frac{3}{2}(n-1)\rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. ...
- 30.9k
11
votes
Accepted
Bounds for number of edges of a graph, given girth and number of vertices
The bound you quote is actually a little inefficient, because it is harder to find a cycle of fixed length $t$ than to find a cycle of length at most $t$. I recommend that you look at Section 4.1 of ...
- 806
9
votes
Accepted
Average and max. hitting time to a specific vertex
Notation: Let $G=(V,E)$ be an undirected simple graph of $n$ nodes. If $\tau_x$ is the (random) time it takes the walk to reach the node $x$,
then write $H(v,x)=E_v(\tau_x)$. Denote $H_{\max}(x):=\...
- 13.8k
8
votes
Accepted
Smallest triangle-free graph with chromatic number 5
22 vertices, there are 80 of them.
Jensen and Royle, Small graphs with chromatic number 5 : a computer search
Journal of Graph Theory, 1995.
- 11.7k
8
votes
Population of P people, where each person knows K others, how many people mutually know each other
For $x\geq 2$, and $m$ odd, there is a regular digraph of order $P=(x-1)m$ and of out-valency $K=(x-2)m+\frac{m-1}{2}=\frac{(2x-3)m}{2}-\frac{1}{2}$ with no cliques of size $x$: start with the ...
- 3,151
7
votes
The maximal number of copies of a graph $T$ in an $H$-free graph
This was an answer to a previous version of the question, when $H$ was not claimed to be a tree.
It is well-known that a maximal number of edges in a $C_4$-free graph is $\Theta(n^{3/2})$ (since ...
- 22k
7
votes
Accepted
Length minimizing graphs between a finite set of points
This is the so-called Steiner Tree Problem.
- 95.2k
7
votes
Graph metric approximating Euclidean metric
Pick some small $\epsilon>0$, take the dilated integer lattice $\epsilon^2\cdot\mathbb{Z}^2$ to be our vertex set, and draw an edge between two vertices if their Euclidean distance is between $\...
- 7,465
7
votes
Snake algorithm that minimizes straight lines
This problem is a special case of the quadratic traveling salesman problem in which the cost for traversing three consecutive nodes that have no turn is $1$ and the cost is $0$ otherwise. Because ...
- 5,019
6
votes
Determine or estimate the number of maximal triangle-free graphs on $n$ vertices
This question was recently solved by Balogh & Petrickova. Douglas Zare's bound is tight (apart from the $o(1)$ term). See http://arxiv.org/abs/1409.8123
6
votes
Accepted
A proper definition of connectivity for hypergraphs
Think of the hypergraph as a simplicial complex $\Delta$, with the facets being the hyperedges. Consider property (*) as:
1) The $i$-skeleton of $\Delta$ is full for $0\leq i\leq k-2$ and
2) $\...
- 30.2k
6
votes
Accepted
Existence of connected component with large boundary?
If all degrees are at least 3, there exists a spanning tree with at least $n/4+2$ leaves (D. J. Kleitman and D. B. West, Spanning trees with many leaves, SIAM J. Disc. Math. 4(1991), 99-106), the ...
- 98.3k
6
votes
Accepted
Independence number of $C_4$-free graphs
If we denote $m=\alpha(G)+1$, then our graph does not contain $C_4$ and its complement does not contain $K_m$, thus $n<R(C_4,K_m)$ (and viceversa, if $n<R(C_4,K_m)$, there exists a graph on $n$ ...
- 98.3k
6
votes
Accepted
Graph combinatorial optimization problem
The answer is $k=n-2$. To see this, first note that $k \geq n-2$, since the complete graph on $n$ vertices minus an edge has the desired property for $k=n-3$. For the other inequality suppose that $...
- 30.9k
5
votes
Accepted
Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$
According to Wikipedia, a $k$-core of a graph $G$ is a maximal connected subgraph $K$ of $G$ such that every vertex of $K$ has degree at least $k$. Apart from the "connected" part of the definition, ...
- 761
5
votes
Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)
Let me add a possibly shortest proof of the inequality you asked, although not by Cauchy-Schwarz. Following Sasha's notation, let $g(x)=\int f(x,y) dy$. Then by Holder's inequality,
\begin{align*}
\...
- 65
5
votes
Accepted
Kovari-Sos-Turan theorem
The appropriate search term is "supersaturation". I think Theorem 11.1 in
Furedi, Z., Simonovits, M. (2013). The history of degenerate (bipartite) extremal graph problems. In Erdos Centennial (pp. ...
- 2,936
5
votes
Accepted
Counting the forests obtainable by removing subtrees from binary trees
It is convenient to consider the vertex set of $B_h$ as a partially ordered set with its natural genealogic order, with minimum element its root. Any subtree $T'$ as described in your procedure (also ...
- 55.1k
5
votes
Lovasz local lemma for the edge model
This is not a full answer by any means, by likely a bit longer than a comment. The local lemma as it is usually stated doesn't apply nicely to $G(n,m)$ (as you note) due to the fact that the ...
- 740
5
votes
Accepted
Density of bipartite $d$-degenerate graph
Theorem. A $d$-degenerate $n$-vertex bipartite graph has at most $\lceil \frac{n}{2} \rceil \lfloor \frac{n}{2} \rfloor$ edges if $n < 2d$ and at most $d(n-d)$ edges if $n \geq 2d$. Moreover, both ...
- 30.9k
5
votes
Accepted
Minimum size of regular graph with no short cycles
The problem of determining the smallest regular graphs with degree $k$ and girth $g$ is normally known as the cage problem.
It has a large literature which is nicely summarised in the Dynamic Cage ...
- 11.7k
5
votes
Ramsey-Turán density function is well defined
New Answer: It indeed follows from vertex-multiplication. If you replace each vertex with a stable set of size $k$, then $\alpha(G)/n$ will not change, while $n^r$ and the number of edges both grow by ...
- 18.6k
5
votes
Accepted
Graphs without short cycles and with linear number of edges
Threshold is $\log n$.
If the graph has at least, say, $2n$ edges, it has a cycle of length at most, say, $2\log_2 n$ (proof: remove vertices of degree at most 2 while it is possible. After each step,...
- 98.3k
5
votes
Accepted
Cover a graph with small size complete graphs
Here is an example showing that the clique size $\sqrt{m/n}$ does not suffice.
Graphs on $n$ vertices without 4-cycles have less than $O(n^{3/2})$ edges, and there is a series of examples where this ...
- 6,207
5
votes
Accepted
Turán density of hypergraphs with very few edges
Seems, the answer is negative for $m=3$: consider $H = \{AB, BC, AC\}$ for disjoint $k$-element sets $A,B,C$. Then for $r=2k$ the is an $r$-graph $F$ which density is close to 0.5: consider only $r$-...
- 216
5
votes
Longest paths and cycles in Steiner triple systems
Im, Kim, Lee and Methuku have recently shown that one can find loose paths on $(1 - o(1))n$ vertices in any Steiner triple system on $n$ vertices. This is of course best possible up to the $o(1)$ term....
- 546
4
votes
Accepted
Maximal number of perfect matchings that pairwise form a Hamiltonian cycle
Assume that $n-1$ is an odd prime. Arrange the vertices as follows: $n-1$ of them lie on the circle and form a regular $(n-1)$-gon, and the $n$th vertex is the center. Now, each of the matchings ...
- 22k
Only top scored, non community-wiki answers of a minimum length are eligible