Random algebraic construction of extremal graphs

2014/09/12 by Boris Bukh, Bukh, Boris · 4 citations
Mathematics · #05C35 #05D99 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05D99

paper · pdf · doi:10.48550/arxiv.1409.3856

8 pages

arxiv created 2015/07/23 · arxiv updated 2015/07/24

Abstract

In this expository paper, we present a motivated construction of large graphs not containing a given complete bipartite subgraph. The key insight is that the algebraic constructions yield very non-smooth probability distributions.

Cited by

• Tight bounds towards Zarankiewicz problem in hypergraph
• Induced rational exponents and bipartite subgraphs in K_{s, s}-free graphs
• Rational Exponents for General Graphs
• Combinatorial theorems relative to sparse sets

Related

• The history of degenerate (bipartite) extremal graph problems
• How to get the random graph with non-uniform probabilities?
• Large-scale structures in random graphs
• Learning Very Large Graphs with Unknown Vertex Distributions
• Random Algebraic Graphs and Their Convergence to Erdos-Renyi