New bounds on even cycle creating Hamiltonian paths using expander graphs

DOI10.1007/S00493-020-4204-ZMaRDI QIDQ2220967zbMATH OpenOpenAlexFDO

Authors Gergely Harcods, Daniel Soltész

Publication date 25 January 2021

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.04601

zbMATH Keywords

expander graphsHamiltonian paths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Extremal combinatorics (05D99) Expander graphs (05C48)

Abstract: We say that two graphs on the same vertex set are $G$-creating if their union (the union of their edges) contains $G$ as a subgraph. Let $H_n(G)$ be the maximum number of pairwise $G$-creating Hamiltonian paths of $K_n$. Cohen, Fachini and K"orner proved [n^{frac{1}{2}n-o(n)}leq H_n(C_4) leq n^{frac{3}{4}n+o(n)}.] In this paper we close the superexponential gap between their lower and upper bounds by proving [n^{frac{1}{2}n-frac{1}{2}frac{n}{log{n}}-O(1)}leq H_n(C_4) leq n^{frac{1}{2}n+oleft(frac{n}{log{n}} ight)}.] We also improve the previously established upper bounds on $H_n(C_{2k})$ for $k>3$, and we present a small improvement on the lower bound of F"uredi, Kantor, Monti and Sinaimeri on the maximum number of so-called pairwise reversing permutations. One of our main tools is a theorem of Krivelevich, which roughly states that (certain kinds of) good expanders contain many Hamiltonian paths.

Recommendations

• Even cycle creating paths
• Families of locally separated Hamilton paths
• On covering expander graphs by Hamilton cycles
• Hamilton cycles in highly connected and expanding graphs
• scientific article; zbMATH DE number 4130411

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• A mean value estimate for real character sums
• A new series of dense graphs of high girth
• An Upper Bound on Zarankiewicz' Problem
• Degree-doubling graph families
• Even cycle creating paths
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Families of graph-different Hamilton paths
• Families of locally separated Hamilton paths
• Graph-Different Permutations
• Incidences and the spectra of graphs
• Intersecting families of permutations
• Intersecting families of sets and permutations: a survey
• Matrices
• Maximum size of reverse-free sets of permutations
• ON THE DIFFERENCE BETWEEN CONSECUTIVE PRIMES
• On Additive Combinatorics of Permutations of \mathbb{Z}_n
• On Graphs that do not Contain a Thomsen Graph
• On \(k\)-neighbor separated permutations
• On reverse-free codes and permutations
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• On the maximum number of permutations with given maximal or minimal distance
• On the number of Hamilton cycles in pseudo-random graphs
• On types of growth for graph-different permutations
• Pairwise colliding permutations and the capacity of infinite graphs
• Path separation by short cycles
• Ramanujan graphs
• The difference between consecutive primes. II
• Triangle-different Hamiltonian paths

Cited in

(3)

• Improved upper bounds on even-cycle creating Hamilton paths
• Families of locally separated Hamilton paths
• Even cycle creating paths

This page was built for publication: New bounds on even cycle creating Hamiltonian paths using expander graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220967)