# Tag Info

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

• 7,465

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

### 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
Accepted

• 30.9k
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

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

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

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

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