Search for: All records

Abstract A fundamental problem in Ramsey theory is to determine the growth rate in terms of $$n$$ of the Ramsey number $$r(H, K_{n}^{(3)})$$ of a fixed $$3$$-uniform hypergraph $$H$$ versus the complete $$3$$-uniform hypergraph with $$n$$ vertices. We study this problem, proving two main results. First, we show that for a broad class of $$H$$, including links of odd cycles and tight cycles of length not divisible by three, $$r(H, K_{n}^{(3)}) \ge 2^{\Omega _{H}(n \log n)}$$. This significantly generalizes and simplifies an earlier construction of Fox and He which handled the case of links of odd cycles and is sharp both in this case and for all but finitely many tight cycles of length not divisible by three. Second, disproving a folklore conjecture in the area, we show that there exists a linear hypergraph $$H$$ for which $$r(H, K_{n}^{(3)})$$ is superpolynomial in $$n$$. This provides the first example of a separation between $$r(H,K_{n}^{(3)})$$ and $$r(H,K_{n,n,n}^{(3)})$$, since the latter is known to be polynomial in $$n$$ when $$H$$ is linear. 

Abstract A finite point set in$$\mathbb{R}^d$$is in general position if no$$d + 1$$points lie on a common hyperplane. Let$$\alpha _d(N)$$be the largest integer such that any set of$$N$$points in$$\mathbb{R}^d$$, with no$$d + 2$$members on a common hyperplane, contains a subset of size$$\alpha _d(N)$$in general position. Using the method of hypergraph containers, Balogh and Solymosi showed that$$\alpha _2(N) \lt N^{5/6 + o(1)}$$. In this paper, we also use the container method to obtain new upper bounds for$$\alpha _d(N)$$when$$d \geq 3$$. More precisely, we show that if$$d$$is odd, then$$\alpha _d(N) \lt N^{\frac {1}{2} + \frac {1}{2d} + o(1)}$$, and if$$d$$is even, we have$$\alpha _d(N) \lt N^{\frac {1}{2} + \frac {1}{d-1} + o(1)}$$. We also study the classical problem of determining$$a(d,k,n)$$, the maximum number of points selected from the grid$$[n]^d$$such that no$$k + 2$$members lie on a$$k$$-flat, and improve the previously best known bound for$$a(d,k,n)$$, due to Lefmann in 2008, by a polynomial factor when$$k$$= 2 or 3 (mod 4). 

Abstract: Let C_{s,t} be the complete bipartite geometric graph, with s and t vertices on two distinct parallel lines respectively, and all s t straight-line edges drawn between them. In this paper, we show that every complete bipartite simple topological graph, with parts of size 2(k-1)⁴ + 1 and 2^{k^{5k}}, contains a topological subgraph weakly isomorphic to C_{k,k}. As a corollary, every n-vertex simple topological graph not containing a plane path of length k has at most O_k(n^{2 - 8/k⁴}) edges. When k = 3, we obtain a stronger bound by showing that every n-vertex simple topological graph not containing a plane path of length 3 has at most O(n^{4/3}) edges. We also prove that x-monotone simple topological graphs not containing a plane path of length 3 have at most a linear number of edges. 

A natural open problem in Ramsey theory is to determine those $3$ -graphs $H$ for which the off-diagonal Ramsey number $r(H,K_n^{\left(3\right)})$ grows polynomially with $n$ . We make substantial progress on this question by showing that if $H$ is tightly connected or has at most two tight components, then $r(H,K_n^{\left(3\right)})$ grows polynomially if and only if $H$ is contained in an iterated blowup of an edge. 

For fixed d ≥ 3, we construct subsets of the d-dimensional lattice cube [n]^d of size n^{3/(d + 1) - o(1)} with no d+2 points on a sphere or a hyperplane. This improves the previously best known bound of Ω(n^{1/(d-1)}) due to Thiele from 1995. 

A graph is said to contain K_k (a clique of size k) as a weak immersion if it has k vertices, pairwise connected by edge-disjoint paths. In 1989, Lescure and Meyniel made the following conjecture related to Hadwiger’s conjecture: Every graph of chromatic number k contains K_k as a weak immersion. We prove this conjecture for graphs with at most 1.4(k-1) vertices. As an application, we make some progress on Albertson’s conjecture on crossing numbers of graphs, according to which every graph G with chromatic number k satisfies cr(G) ≥ cr(K_k). In particular, we show that the conjecture is true for all graphs of chromatic number k, provided that they have at most 1.4(k-1) vertices and k is sufficiently large.