Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
From MaRDI portal
Publication:2509737
Abstract: In this paper we modify slightly Razborov's flag algebra machinery to be suitable for the hypercube. We use this modified method to show that the maximum number of edges of a 4-cycle-free subgraph of the n-dimensional hypercube is at most 0.6068 times the number of its edges. We also improve the upper bound on the number of edges for 6-cycle-free subgraphs of the n-dimensional hypercube from the square root of 2 - 1 to 0.3755 times the number of its edges. Additionally, we show that if the n-dimensional hypercube is considered as a poset, then the maximum vertex density of three middle layers in an induced subgraph without 4-cycles is at most 2.15121 times n choose n/2.
Recommendations
Cites work
- \(Q _{2}\)-free families in the Boolean lattice
- A new lower bound based on Gromov's method of selecting heavily covered points
- A note on short cycles in a hypercube
- A Ramsey-type result for the hypercube
- An extremal theorem in the hypercube
- Bounding the size of square-free subgraphs of the hypercube
- CSDP, A C library for semidefinite programming
- Flag algebras
- Hexagon-free subgraphs of hypercubes
- Highly symmetric subgraphs of hypercubes
- scientific article; zbMATH DE number 3869331 (Why is no real title available?)
- scientific article; zbMATH DE number 4164941 (Why is no real title available?)
- Hypergraphs do jump
- On 14-Cycle-Free Subgraphs of the Hypercube
- On diamond-free subposets of the Boolean lattice
- On even-cycle-free subgraphs of the hypercube
- On the maximum number of edges in a c4‐free subgraph of qn
- On the maximum number of five-cycles in a triangle-free graph
- On the number of pentagons in triangle-free graphs
- Subgraphs of a hypercube containing no small even cycles
- Three layer \(Q _{2}\)-free families in the Boolean lattice
Cited in
(37)- Finitely forcible graph limits are universal
- An upper bound on the size of diamond-free families of sets
- Generalized Turán densities in the hypercube
- The \(Q_2\)-free process in the hypercube
- On even-cycle-free subgraphs of the doubled Johnson graphs
- Extremal even-cycle-free subgraphs of the complete transposition graphs
- Minimum number of edges that occur in odd cycles
- Compactness and finite forcibility of graphons
- Abelian groups yield many large families for the diamond problem
- Rainbow triangles in three-colored graphs
- scientific article; zbMATH DE number 4029610 (Why is no real title available?)
- Subgraphs of a hypercube containing no small even cycles
- Weak regularity and finitely forcible graph limits
- Diamond-free subsets in the linear lattices
- Turán problems on non-uniform hypergraphs
- Finitely forcible graphons and permutons
- On a covering problem in the hypercube
- On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs
- Finitely forcible graphons with an almost arbitrary structure
- Semantic limits of dense combinatorial objects
- Decomposing graphs into edges and triangles
- Minimum Number of Monotone Subsequences of Length 4 in Permutations
- Saturated subgraphs of the hypercube
- Saturation in the hypercube and bootstrap percolation
- On even-cycle-free subgraphs of the hypercube
- On even-cycle-free subgraphs of the hypercube
- Extremal numbers for cycles in a hypercube
- Pairing strategies for the maker-breaker game on the hypercube with subcubes as winning sets
- A class of graphs of zero Turán density in a hypercube
- On graphs embeddable in a layer of a hypercube and their extremal numbers
- The Rado multiplicity problem in vector spaces over finite fields
- The dimension of the region of feasible tournament profiles
- \(C_{10}\) has positive Turán density in the hypercube
- The dimension of the feasible region of pattern densities
- The four-color Ramsey multiplicity of triangles
- Inducibility of directed paths
- Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
This page was built for publication: Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509737)
