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

DOI10.1007/S11856-012-0184-ZzbMATH Open1275.05031arXiv1108.5254OpenAlexW3098862080MaRDI QIDQ375770FDOQ375770

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)

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

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

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

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)

Cites Work

• Number of Points of Varieties in Finite Fields
• On the structure of linear graphs
• Norm-graphs and bipartite Turán numbers
• On Graphs that do not Contain a Thomsen Graph
• Cycles of even length in graphs
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• The homology of iterated loop spaces
• Norm-graphs: Variations and applications
• New asymptotics for bipartite Turán numbers
• Minimal Regular Graphs of Girths Eight and Twelve
• 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
• 2𝑘-regular maps on smooth manifolds
• Subspace evasive sets

Cited In (15)

• Graphs with few paths of prescribed length between any two vertices
• On Turán exponents of bipartite graphs
• Random algebraic construction of extremal graphs
• Turán numbers of theta graphs
• Implicit representation conjecture for semi-algebraic 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 polynomial resultant approach to algebraic constructions of extremal graphs
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• 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)