Random algebraic construction of extremal graphs
By Boris Bukh. 2014
65 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/befe27b32b3549dd173ed3a8d9c03deb57da5d51
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Geometry and Topology
Citations in the corpus
- Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles (2020, background): “4], proved by a variant of Bukh’s random algebraic method [3], states that if H contains a cycle, then there exists r such that fr(n,H) = O(n).”
- Rational exponents in extremal graph theory (2015, background): “ning no copy of Ks,t with t = (s−1)! +1. Alternative proofs showing that ex(n,Ks,t) = Ωs(n2−1/s) when t is significantly larger than s were later found by Blagojevi´c, Bukh and Karasev [2] and by Bukh [4]. In both cases, the basic idea behind the construction is to take a random polynomial f : Fs q× ”
- A survey on spectral conditions for some extremal graph problems (2021, methodology): “In 2021, Bukh made a further improvement [32] by applying the random algebraic construction again.”
- Graphs with few paths of prescribed length between any two vertices (2014, methodology): “Very recently, Bukh [6] found a simple, elegant method for showing that the Kővári–Sós–Turán bound is tight for t sufficiently large in terms of s, fusing the algebraic techniques used in all previous constructions with an application of the probabilistic method.”
- The number of $C_{2l}$-free graphs (2013, background): “ section we will prove Conjecture 1.6 for the complete bipartite graph H = Ks,t, under the assumption that ex(n,Ks,t) = Ω(n2−1/s), which is known to be the case when t = t(s) is sufficiently large (see [1, 10, 14, 40]). The bound is generally believed to hold for every 2 6 s 6 t, and was conjectured a”