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

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

2011-12-31

arxiv.org/abs/1201.0209v1

Mathematics

Combinatorics

12 pages, 6 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-672304