pith. sign in

arxiv: 1305.6945 · v1 · pith:O5FRTMYEnew · submitted 2013-05-29 · 🧮 math.CO

Infinite Tur\'an problems for bipartite graphs

classification 🧮 math.CO
keywords infinitefreebipartitegraphgraphssqrtconsiderconstruct
0
0 comments X
read the original abstract

We consider an infinite version of the bipartite Tur\'{a}n problem. Let $G$ be an infinite graph with $V(G) = \mathbb{N}$ and let $G_n$ be the $n$-vertex subgraph of $G$ induced by the vertices $\{1,2, \dots, n \}$. We show that if $G$ is $K_{2,t+1}$-free then for infinitely many $n$, $e(G_n) \leq 0.471 \sqrt{t} n^{3/2}$. Using the $K_{2,t+1}$-free graphs constructed by F\"{u}redi, we construct an infinite $K_{2,t+1}$-free graph with $e(G_n) \geq 0.23 \sqrt{t}n^{3/2}$ for all $n \geq n_0$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.