%I #21 Jul 23 2015 13:48:31
%S 1,3,9,24,56,132
%N Maximal number of edges in a C_4 free subgraph of the n-cube.
%C This is related to the famous conjecture of Erdős (see Erdős link).
%D M. R. Emamy, K. P. Guan and I. J. Dejter, On fault tolerance in a 5-cube. Preprint.
%D H. Harborth and H. Nienborg, Maximum number of edges in a six-cube without four-cycles, Bulletin of the ICA 12 (1994) 55-60
%H P. Brass, H. Harborth and H. Nienborg, <a href="http://dx.doi.org/10.1002/jgt.3190190104">On the maximum number of edges in a c4-free subgraph of qn</a>, J. Graph Theory 19 (1995) 17-23
%H F. R. K. Chung, <a href="http://dx.doi.org/10.1002/jgt.3190160311">Subgraphs of a hypercube containing no small even cycles</a>, J. Graph Theory 16 (1992) 273-286
%H Paul Erdős <a href="http://www.math.ucsd.edu/~erdosproblems/erdos/newproblems/TuranInCube.html">Subgraphs of the cube without a 2k-cycle</a>
%H _Manfred Scheucher_ and _Paul Tabatabai_, <a href="/A245762/a245762.py.txt">Python Script</a>
%e a(2) = 3 since the 2-cube is the 4-cycle and one needs to remove a single edge to get rid of all 4-cycles.
%K nonn,more
%O 1,2
%A _Jernej Azarija_, Jul 31 2014
%E a(6) from _Manfred Scheucher_ and _Paul Tabatabai_, Jul 23 2015
|