Free, publicly-accessible full text available September 6, 2024
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
Free, publicly-accessible full text available September 6, 2024
-
Angelini, P. (Ed.)We show that every complete n-vertex simple topological graph contains a topological subgraph on at least (logn)1/4−o(1) vertices that is weakly isomorphic to the complete convex geometric graph or the complete twisted graph. This is the first improvement on the bound Ω(log1/8n) obtained in 2003 by Pach, Solymosi, and Tóth. We also show that every complete n-vertex simple topological graph contains a plane path of length at least (logn)1−o(1) .more » « less
-
Buchin, Kevin and (Ed.)Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if |F| ≥ c^k, then F contains an r-sunflower. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) ≤ d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function. We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.more » « less
Full Text Available