Mathematics – Combinatorics
Scientific paper
2012-01-17
Mathematics
Combinatorics
9 pages, 3 figures. Additional files: 2 C++ source code files, and 5 data text files for proof verification
Scientific paper
In this paper we describe how to extend Razborov's flag algebra method from hypergraphs to hypercubes. We then use this method to significantly improve the upper bounds of edge and vertex Tur\'an density type results for hypercubes. In particular we improve Thomason and Wagner's result on the upper bound of the edge Tur\'an density of a 4-cycle free subcube to 0.60680 and Chung's result on forbidding 6-cycles to 0.37550. We also show that the upper bound of the vertex Tur\'an density of $\mathcal{Q}_3$ can be improved to 0.76900, and that the vertex Tur\'an density of $\mathcal{Q}_3$ with one vertex removed is precisely 2/3. The results in this paper originally appeared in the author's PhD thesis in March 2011. J\'ozsef Balogh, Ping Hu, Bernard Lidick\'y, and Hong Liu independently rediscovered and verified the edge Tur\'an hypercube results in December 2011, see their paper "Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube" (arXiv:1201.0209v1).
No associations
LandOfFree
Turán densities of hypercubes 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 Turán densities of hypercubes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turán densities of hypercubes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-98064