Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

DOI10.1016/j.ejc.2013.06.003zbMath1296.05096arXiv1201.0209OpenAlexW2105222637MaRDI QIDQ2509737

Bernard Lidický, Hong Liu, Ping Hu, József Balogh

Publication date: 29 July 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Razborov's flag algebra

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Related Items (25)

Finitely forcible graph limits are universal ⋮ Rainbow triangles in three-colored graphs ⋮ Extremal numbers for cycles in a hypercube ⋮ Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle ⋮ Pairing strategies for the maker-breaker game on the hypercube with subcubes as winning sets ⋮ Minimum Number of Monotone Subsequences of Length 4 in Permutations ⋮ An upper bound on the size of diamond-free families of sets ⋮ Saturated Subgraphs of the Hypercube ⋮ Saturation in the Hypercube and Bootstrap Percolation ⋮ Finitely forcible graphons with an almost arbitrary structure ⋮ The \(Q_2\)-free process in the hypercube ⋮ Diamond-free subsets in the linear lattices ⋮ Turán problems on non-uniform hypergraphs ⋮ Finitely forcible graphons and permutons ⋮ Semantic limits of dense combinatorial objects ⋮ On a covering problem in the hypercube ⋮ On even-cycle-free subgraphs of the doubled Johnson graphs ⋮ Extremal even-cycle-free subgraphs of the complete transposition graphs ⋮ Decomposing Graphs into Edges and Triangles ⋮ Minimum number of edges that occur in odd cycles ⋮ Weak regularity and finitely forcible graph limits ⋮ Compactness and finite forcibility of graphons ⋮ Inducibility of directed paths ⋮ Generalized Turán densities in the hypercube ⋮ Abelian groups yield many large families for the diamond problem

Uses Software

• CSDP

Cites Work

• Unnamed Item
• Unnamed Item
• A new lower bound based on Gromov's method of selecting heavily covered points
• Highly symmetric subgraphs of hypercubes
• On the maximum number of five-cycles in a triangle-free graph
• \(Q _{2}\)-free families in the Boolean lattice
• An extremal theorem in the hypercube
• Bounding the size of square-free subgraphs of the hypercube
• On diamond-free subposets of the Boolean lattice
• On the number of pentagons in triangle-free graphs
• Three layer \(Q _{2}\)-free families in the Boolean lattice
• A note on short cycles in a hypercube
• Hypergraphs Do Jump
• Hexagon-free subgraphs of hypercubes
• A Ramsey-type result for the hypercube
• On 14-Cycle-Free Subgraphs of the Hypercube
• Subgraphs of a hypercube containing no small even cycles
• On the maximum number of edges in a c₄‐free subgraph of q_n
• CSDP, A C library for semidefinite programming
• Flag algebras
• On even-cycle-free subgraphs of the hypercube
• Counting flags in triangle-free digraphs

This page was built for publication: Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube