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 ...

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 ...

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$. ...

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 ...

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):=\...

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.

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 ...

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 ...

7
votes

Accepted

### Length minimizing graphs between a finite set of points

This is the so-called Steiner Tree Problem.

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
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 ...

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) $\...

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 ...

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$ ...

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 $...

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, ...

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*}
\...

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. ...

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 ...

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 ...

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 ...

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 ...

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 ...

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,...

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 ...

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$-...

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....

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 ...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

extremal-graph-theory × 225graph-theory × 184

co.combinatorics × 135

extremal-combinatorics × 34

graph-colorings × 22

reference-request × 20

combinatorial-optimization × 13

ramsey-theory × 13

spectral-graph-theory × 8

random-graphs × 8

algorithms × 7

hypergraph × 7

bipartite-graphs × 6

matching-theory × 5

extremal-set-theory × 5

pr.probability × 4

trees × 4

matrices × 3

open-problems × 3

hamiltonian-graphs × 3

expander-graphs × 3

cycles × 3

spanning-tree × 3

nt.number-theory × 2

gr.group-theory × 2