Search for: All records

Abstract We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively, states that all connected vertex‐transitive graphs contain a Hamiltonian path, and that all sufficiently large such graphs even contain a Hamiltonian cycle. The third conjecture, due to Smith from 1984, states that for in every ‐connected graph any two longest cycles intersect in at least vertices. In this paper, we prove a new lemma about the intersection of longest cycles in a graph, which can be used to improve the best known bounds toward all the aforementioned conjectures: First, we show that every connected vertex‐transitive graph on vertices contains a cycle (and hence path) of length at least , improving on from DeVos [arXiv:2302:04255, 2023]. Second, we show that in every ‐connected graph with , any two longest cycles meet in at least vertices, improving on from Chen, Faudree, and Gould [J. Combin. Theory, Ser. B,72(1998) no. 1, 143–149]. Our proof combines combinatorial arguments, computer search, and linear programming. 

ABSTRACT For $$B \subseteq \mathbb F_q^m$$, the nth affine extremal number of B is the maximum cardinality of a set $$A \subseteq \mathbb F_q^n$$ with no subset, which is affinely isomorphic to B. Furstenberg and Katznelson proved that for any $$B \subseteq \mathbb F_q^m$$, the nth affine extremal number of B is $o(q^n)$ as $$n \to \infty$$. By counting affine homomorphisms between subsets of $$\mathbb F_q^n$$, we derive new bounds and give new proofs of some previously known bounds for certain affine extremal numbers. At the same time, we establish corresponding supersaturation results. We connect these bounds to certain Ramsey-type numbers in vector spaces over finite fields. For $$s,t \geq 1$$, let $$R_q(s,t)$$ denote the minimum n such that in every red–blue coloring of the one-dimensional subspaces of $$\mathbb F_q^n$$, there is either a red s-dimensional subspace or a blue t-dimensional subspace of $$\mathbb F_q^n$$. The existence of these numbers is a special case of a well-known theorem of Graham, Leeb and Rothschild. We improve the best-known upper bounds on $$R_2(2,t)$$, $$R_3(2,t)$$, $$R_2(t,t)$$ and $$R_3(t,t)$$.