Originators: Andrzej Czygrinow, Brendan Nagle, Dhruv Mubayi, Yi Zhao (presented by Oleg Pikhurko - REGS 2010)
Definitions: Here we restrict our attention to 3-uniform hypergraphs, called 3-graphs. The co-degree c(x,y) of distinct vertices x and y in a 3-graph G is the number of edges that contain both. Let the minimum co-degree δ2(G) be the minimum of c(x,y) over distinct x,y∈V(G). The co-degree Turan number co-ex(n,F) is the maximum of δ2(G) over all F-free 3-graphs G with n vertices.
Background: We refer the reader to Mubayi and Zhao [MZ] who initiated a systematic study of this function and posed a number of interesting questions. The co-degree Turan number of the Fano plane was determined by Mubayi [M] (asymptotically) and Keevash [K] (exactly).
Conjecture 1: (Nagle [N]): For the unique 3-graph F having four vertices and three edges, co-ex(n,F)=(1/4+o(1))n.
Comments: The following construction yields the lower bound. Let T be a random tournament on n vertices. Let a triple of vertices form an edge in G if it spans a directed 3-cycle in T. The expected number of triples containing any fixed pair of vertices is (n-2)/4; Chernoff's bound implies that almost surely each co-degree is (1/4+o(1))n. Also, G does not contain a copy of F.
Addendum: Emil Vaughan reports a solution of Conjecture 1 using flag algebras and a lot of computation [FPV].
Conjecture 2: (Nagle [N], Czygrinow and Nagle [CN]): For the complete 3-graph K43 with four vertices, co-ex(n,K43)=(1/2+o(1))n.
Comments: Again the lower bound follows by taking a random tournament T on {1,...,n}, this time making a triple {i,j,k} in which i is the least element into an edge of G if i has one successor and one predecessor in {j,k}.
Question 3: (Mubayi and Zhao [MZ]): Can one find at least one 3-graph F such that, for n approaching infinity, the limits of co-ex(n,F)/n and ex(n,F)/Binomial(n,3) are equal and positive? Here ex(n,F) is the maximum size of an F-free 3-graph on n vertices; both limits are known to exist.
Comments: For 2k-uniform hypergraphs the answer is yes, see the discussion on Page 1120 in [MZ].
References:
(Thanks to Emil Vaughan for the original reference [N].)
[CN] Andrzej Czygrinow and Brendan Nagle, A note on co-degree
problem for hypergraphs, Bulletin of ICA 32 (2001) 63-69.
[FPV] Victor Falgas-Ravry, Oleg Pikhurko, and Emil Vaughan, draft.
[K] Peter Keevash, A hypergraph regularity method for generalized
Turan problems, Random Struct Alg 34 (2009) 123-164.
[M] Dhruv Mubayi, The co-degree density of the Fano plane,
JCTB 95 (2005), 333-337.
[MZ] Dhruv Mubayi and Yi Zhao, Co-degree density of
hypergraphs, JCTA 144 (2007) 1118-1132.
[N] Brendan Nagle, Turán related problems for hypergraphs,
Congr. Numer. 136 (1999), 119-127.