[HTML][HTML] Kővári-Sós-Turán theorem for hereditary families
The celebrated Kővári-Sós-Turán theorem states that any n-vertex graph containing no copy
of the complete bipartite graph K s, s has at most O s (n 2− 1/s) edges. In the past two …
of the complete bipartite graph K s, s has at most O s (n 2− 1/s) edges. In the past two …
Zarankiewicz's problem for semilinear hypergraphs
A bipartite graph with is semilinear if for some and the edge relation E consists of the pairs of
points satisfying a fixed Boolean combination of s linear equalities and inequalities in …
points satisfying a fixed Boolean combination of s linear equalities and inequalities in …
A survey of degree-boundedness
X Du, R McCarty - arXiv preprint arXiv:2403.05737, 2024 - arxiv.org
If a graph has no large balanced bicliques, but has large minimum degree, then what can
we say about its induced subgraphs? This question motivates the study of degree …
we say about its induced subgraphs? This question motivates the study of degree …
A survey of Zarankiewicz problem in geometry
S Smorodinsky - arXiv preprint arXiv:2410.03702, 2024 - arxiv.org
One of the central topics in extremal graph theory is the study of the function $ ex (n, H) $,
which represents the maximum number of edges a graph with $ n $ vertices can have while …
which represents the maximum number of edges a graph with $ n $ vertices can have while …
On the number of incidences when avoiding an induced biclique in geometric settings
TM Chan, S Har-Peled - Discrete & Computational Geometry, 2024 - Springer
Given a set of points P and a set of regions O, an incidence is a pair (p, o)∈ P× O such that
p∈ o. We obtain a number of new results on a classical question in combinatorial geometry …
p∈ o. We obtain a number of new results on a classical question in combinatorial geometry …
Box and segment intersection graphs with large girth and chromatic number
J Davies - arXiv preprint arXiv:2011.14174, 2020 - arxiv.org
Box and Segment Intersection Graphs with Large Girth and Chromatic Number Page 1
Advances IN Combinatorics, 2021:7, 9 pp. www.advancesincombinatorics.com Box and …
Advances IN Combinatorics, 2021:7, 9 pp. www.advancesincombinatorics.com Box and …
Coloring lines and Delaunay graphs with respect to boxes
I Tomon - Random Structures & Algorithms, 2024 - Wiley Online Library
The goal of this paper is to show the existence (using probabilistic tools) of configurations of
lines, boxes, and points with certain interesting combinatorial properties.(i) First, we …
lines, boxes, and points with certain interesting combinatorial properties.(i) First, we …
Local properties of graphs with large chromatic number
J Davies - 2022 - uwspace.uwaterloo.ca
This thesis deals with problems concerning the local properties of graphs with large
chromatic number in hereditary classes of graphs. We construct intersection graphs of axis …
chromatic number in hereditary classes of graphs. We construct intersection graphs of axis …
K\H {o} v\'ari-S\'os-Tur\'an theorem for hereditary families
The celebrated K\H {o} v\'ari-S\'os-Tur\'an theorem states that any $ n $-vertex graph
containing no copy of the complete bipartite graph $ K_ {s, s} $ has at most $ O_s (n^{2-1/s}) …
containing no copy of the complete bipartite graph $ K_ {s, s} $ has at most $ O_s (n^{2-1/s}) …
Zarankiewicz's problem via -t-nets
C Keller, S Smorodinsky - arXiv preprint arXiv:2311.13662, 2023 - arxiv.org
The classical Zarankiewicz's problem asks for the maximum number of edges in a bipartite
graph on $ n $ vertices which does not contain the complete bipartite graph $ K_ {t, t} $. In …
graph on $ n $ vertices which does not contain the complete bipartite graph $ K_ {t, t} $. In …