20 votes

Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

although short proofs with a tricky application of the Cauchy–Schwarz inequality are known. Erm... What's the point of using such high-tech as Cauchy-Schwarz on an elementary algebra problem? WLOG $\...
user avatar
  • 52k
15 votes

Are all almost regular graphs obvious?

Here is an expansion of joro's answer. Claim. $K_{n, n+1}$ is obvious if and only if $n+1$ is even. Proof. If $n+1$ is even, we can add a perfect matching on the vertices on the right to obtain a $...
user avatar
  • 28.7k
14 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 ...
user avatar
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 ...
user avatar
12 votes

Embedding of planar graphs

The recent paper below (and its references) may help. They mention that every planar graph with max degree $4$ (except for the octahedron) admits a $2$-bend embedding. Deciding whether a graph can ...
user avatar
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 ...
user avatar
  • 1,092
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$. ...
user avatar
  • 28.7k
10 votes

Extremal examples for a folklore lemma on subgraphs of large minimum degree

If $G$ and $H$ are both extremal graphs (possibly for different values of $d$) then their Cartesian product is another extremal graph for the sum of the degrees. So the grid example is just a ...
user avatar
9 votes
Accepted

What is the correct statement of this Erdös-Gallai-Tuza problem generalizing Turan's triangle theorem?

I hope I am not violating any kind of MathOverflow etiquette by responding to a question 2 years after it has been asked, but your question is answered in the following preprint of mine that just hit ...
user avatar
9 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 ...
user avatar
8 votes
Accepted

Smallest Connected Graph for Given Degree Sequence

A theorem of Hakimi says that any pair of degree-equivalent graphs can be obtained one from the other by a sequence of "elementary $2$-switchings" (probably known under many other names), which ...
user avatar
8 votes
Accepted

Determine or estimate the number of maximal triangle-free graphs on $n$ vertices

By Theorem 1 in the paper of Erdős, Kleitman, and Rothschild, the number of triangle-free graphs on $n$ vertices is $2^{n^2(1/4 +o(1)) }$. The number of bipartite graphs with a fixed pair of parts of ...
user avatar
  • 27.1k
8 votes
Accepted

Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

If you divide the vertex set into 3 parts, A, B and C, with respective sizes $an$, $bn$ and $cn$, and add all the edges except the ones connecting two vertices inside A and a vertex from A and C, then ...
user avatar
  • 17.1k
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.
user avatar
  • 10.8k
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 ...
user avatar
  • 2,711
7 votes

Are all almost regular graphs obvious?

Don't think just deleting edges from almost regular graph will result in a regular graph of the same order. Take $K_{2,3}$. By exhaustive search deleting edges couldn't find a regular graph on $5$ ...
user avatar
  • 23.3k
7 votes
Accepted

On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Lucia's answer given in the linked question from the comment gives an upper bound (i.e., no pair should appear twice as a subset of $A_i$). But of course, the real question starts from here: When can ...
user avatar
7 votes

Removal of non-isomorphic edges results in the same graph

This is essentially a comment on user2097's excellent answer. One consequence of that answer was the construction of a graph with four non-isomorphic edges whose removals result in isomorphic graphs. ...
user avatar
7 votes
Accepted

Embedding of planar graphs

Bends are necessary, we have studied this problem in this paper: http://arxiv.org/abs/1009.1315.
user avatar
  • 17.1k
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 ...
user avatar
7 votes
Accepted

Length minimizing graphs between a finite set of points

This is the so-called Steiner Tree Problem.
user avatar
  • 93.7k
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 $\...
user avatar
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 ...
user avatar
  • 3,630
6 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*} \...
user avatar
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) $\...
user avatar
  • 29.6k
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 ...
user avatar
  • 86.7k
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 $...
user avatar
  • 28.7k
5 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
user avatar
5 votes

Removal of non-isomorphic edges results in the same graph

Not an answer, just an extended comment. For $n \leq 10$ such graph does not exists. I am currently checking $n = 11.$ Are there any structural properties that such a graph has, other than it is ...
user avatar
  • 3,343

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