Intereting Posts

Inequality involving the regularized gamma function
Is $\left|\,_4F_3\left(\frac{1}{5},\frac{2}{5},\frac{3}{5},\frac{4}{5};\frac{1}{2},\frac{3}{4},\frac{5}{4};\sqrt{\phi }\right)\right|$ a radical?
If $\mu$ is a probability measure on $\mathbb R$, is $t\mapsto\mu\{t\}$ differentiable almost everywhere?
Odd-Odd-Even-Even Sequence
Continuation of smooth functions on the bounded domain
inverse of diagonal plus sum of rank one matrices
Finding for every parameter $\lambda$ if matrix is diagonalizable
To what divisors $a$ of $n$ can Euler's Theorem multiplied by $a$ be generalized, i.e. when is $a^{\phi(n)+1}\equiv a \pmod n$?
Functional equation $f(xy)=f(x)+f(y)$ and continuity
Induction proof error
Understanding how the rules of probability apply to probability density functions
Equivalence relation on a proper class
Rudin: Problem Chp3.11 and need advice.
History of the Concept of a Ring
$\int_0^{\pi}{x \over{a^2\cos^2 x+b^2\sin^2 x}}dx$

Let $G=(V,E)$ be an undirected graph. I am using the usual convention that $n=|V|, m=|E|$. For $v \in V$, let $deg(v)$ be the degree of the vertex $v$.

I am trying to show that if we have $m > \frac{n^{3/2}}{2}$, it follows that $G$ has either a triangle $C_3$ or a square $C_4$. I found a neat way that almost works, but it is not tight enough…

Here is what I have done so far:

- Pigeonhole Principle to Prove a Hamiltonian Graph
- Prove that the maximum number of edges in a graph with no even cycles is floor(3(n-1)/2)
- maximum size of a $k$-intersecting antichain of $$
- Number of Derangements of the word BOTTLE
- What is the maximum point for which number of way to reach is given
- Bounds on the size of these intersecting set families

First of all (not concerning the solution but a related problem) it is a neat example of the Cauchy-Riemann inequality to show that every graph $G$ with more than $n^2/4$ edges contains a triangle $C_3$ (this is Mantel’s theorem).

Now I did this (basically I reproduce a proof given by Erdős):

I try to show if $G$ has no square $C_4$, then $m \leq \frac{n^{3/2}}{2}$. We can consider the amount $k$ of subgraphs of $G$ that look like $K_{1,2}$ (a “cherry”). Certainly if we (double) count those, considering a vertice in the center of the cherry, we get:

$$k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$

Now if we don’t allow squares a pair of vertices $\{v,w\}$ can be endpoints of only one cherry, otherwise we would have a cycle, therefore

$$\binom{n}{2} \geq k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$

Then due to convexity of $\binom{x}{2}$ and the Jensen Inequality one might conclude now that $m \leq \frac{1}{4} \cdot \left(\sqrt{n^2 (4 n-3)}+n\right) $. Sadly after all the work I see that asymtotically this is enough but the bound I want to show is still a big tighter:

I would be very glad if someone could give me an alternate proof that gives me the tight bounds or maybe refine what I did (I did not use the fact yet that $G$ is also triangle-free).

- Probability that an undirected graph has cycles
- In any finite graph with at least two vertices, there must be two vertices with the same degree
- Can any finite group be realized as the automorphism group of a directed acyclic graph?
- Is each edge interpreted like a $2$-cycle?
- Graph theory (Graph Connectivity)
- Prove that a strongly connected digraph has an irreducible adjacency matrix?
- Constructing self-complementary graphs
- Can a polygon with minimal perimeter self-intersect?
- Girth and monochromatic copy of trees
- Graph Theory book with lots of Named Graphs/ Graph Families

A proof can be found in:

Garnick, David K., Kwong, Y. H. Harris, Lazebnik, Felix,

Extremal graphs without three-cycles or four-cycles. J. Graph Theory 17 (1993), no. 5, 633–645.

- The error term in Taylor series and convolution.
- Integral $\int_0^1\frac{\ln x}{\left(1+x\right)\left(1+x^{-\left(2+\sqrt3\right)}\right)}dx$
- What is the condition for example $(number^c)^b=number^{cb}$ to be true?
- Help proving that a Banach space is reflexive
- What are the applications of finite calculus
- Do circles divide the plane into more regions than lines?
- Every finite field is a residue field of a number field
- Is the ideal $I = \{f\mid f (0) = 0\}$ in the ring $C $ of all continuous real valued functions on $$ a maximal ideal?
- How many numbers between $100$ and $900$ have sum of their digits equal to $15$?
- Prove that a perfect square is either a multiple of $4$ or of the form $4q+1$.
- Are calculus and real analysis the same thing?
- Basic fact in $L^p$ space
- Checking the maximality of a principal ideal in $R$
- How to write $\pi$ as a set in ZF?
- Why is it possible to conclude everything from a false statement?