Turán numbers for K_s,t-free graphs: topological obstructions and algebraic constructions

DOI10.1007/S11856-012-0184-ZMaRDI QIDQ375770zbMATH OpenOpenAlexFDO

Authors Pavle V. M. Blagojević, Boris Bukh, Roman Karasev

Publication date 31 October 2013

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.5254

zbMATH Keywords

hypersurface in \(\mathbb R^s\times\mathbb R^s\)

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: We show that every hypersurface in $R^{s}imes{R}^s$ contains a large grid, i.e., the set of the form $SimesT$, with $S,Tsubset{R}^s$. We use this to deduce that the known constructions of extremal $K_{2,2}$-free and $K_{3,3}$-free graphs cannot be generalized to a similar construction of $K_{s,s}$-free graphs for any $sgeq4$. We also give new constructions of extremal $K_{s,t}$-free graphs for large $t$.

Recommendations

• Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions
• The number of \(K_{s,t}\)-free graphs
• Turán number of bipartite graphs with no \(K_{t,t}\)
• Some extremal results on hypergraph Turán problems
• Norm-graphs and bipartite Turán numbers

Cites work

• 2𝑘-regular maps on smooth manifolds
• An Upper Bound on Zarankiewicz' Problem
• An ideal-valued cohomological index theory with applications to Borsuk—Ulam and Bourgin—Yang theorems
• Asymptotic improvements to the lower bound of certain bipartite Turán numbers
• Cycles of even length in graphs
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Minimal Regular Graphs of Girths Eight and Twelve
• New asymptotics for bipartite Turán numbers
• Norm-graphs and bipartite Turán numbers
• Norm-graphs: Variations and applications
• Number of Points of Varieties in Finite Fields
• On Graphs that do not Contain a Thomsen Graph
• On the structure of linear graphs
• Subspace evasive sets
• The homology of iterated loop spaces

Cited in

(15)

• Graphs with few paths of prescribed length between any two vertices
• Random algebraic construction of extremal graphs
• On Turán exponents of bipartite graphs
• Implicit representation conjecture for semi-algebraic graphs
• Turán numbers of theta graphs
• Some extremal results on hypergraph Turán problems
• The number of \(C_{2\ell}\)-free graphs
• Extremal graphs without exponentially small bicliques
• A note on projective norm graphs
• Hypergraphs with Few Berge Paths of Fixed Length between Vertices
• Some extremal results on complete degenerate hypergraphs
• Some tight lower bounds for Turán problems via constructions of multi-hypergraphs
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• A polynomial resultant approach to algebraic constructions of extremal graphs
• Some remarks on the Zarankiewicz problem

This page was built for publication: Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q375770)