Füredi, Zoltan, Mubayi, Dhruv and Pikhurko, Oleg (2008) Quadruple systems with independent neighborhoods. Journal of Combinatorial Theory, Series A, Vol.115 (No.8). pp. 1552-1560. doi:10.1016/j.jcta.2008.01.008 ISSN 0097-3165.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

A 4-graph is odd if its vertex set can be partitioned into two sets so that every edge intersects both parts in an odd number of points. Let
View the MathML source
denote the maximum number of edges in an n-vertex odd 4-graph. Let n be sufficiently large, and let G be an n-vertex 4-graph such that for every triple xyz of vertices, the neighborhood View the MathML source is independent. We prove that the number of edges of G is at most b(n). Equality holds only if G is odd with the maximum number of edges. We also prove that there is ε>0 such that if the 4-graph G has minimum degree at least View the MathML source, then G is 2-colorable.

Our results can be considered as a generalization of Mantel's theorem about triangle-free graphs, and we pose a conjecture about k-graphs for larger k as well.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Journal or Publication Title:	Journal of Combinatorial Theory, Series A
Publisher:	Academic Press
ISSN:	0097-3165
Official Date:	November 2008
Dates:	Date Event November 2008 Published
Volume:	Vol.115
Number:	No.8
Number of Pages:	9
Page Range:	pp. 1552-1560
DOI:	10.1016/j.jcta.2008.01.008
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	Hungarian National Science Foundation, National Science Foundation, NSF
Grant number:	OTKA 062321, 060427, NFS DMS 0600303, DMS-0400812, DMS-0457512

Request changes or add full text files to a record

Repository staff actions (login required)

View Item