On Graph-Lagrangians and clique numbers of 3-uniform hypergraphs

The paper explores the connection of Graph-Lagrangians and its maximum cliques for 3-uniform hypergraphs.Motzkin and Straus showed that the Graph-Lagrangian of a graph is the Graph-Lagrangian of its maximum cliques.This connection provided a new proof of Turán classical result on the Turán density of complete graphs.Since then,Graph-Lagrangian has become a useful tool in extremal problems for hypergraphs.Peng and Zhao attempted to explore the relationship between the Graph-Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range.They showed that if G is a 3-uniform graph with m edges containing a clique of order t-1,then λ(G)=λ([t-1]~((3))) provided (t-13)≤m≤(t-13)+_(t-22).They also conjectured:If G is an r-uniform graph with m edges not containing a clique of order t-1,then λ(G)λ([t-1]~((r))) provided (t-1r)≤ m ≤(t-1r)+(t-2r-1).It has been shown that to verify this conjecture for 3-uniform graphs,it is sufficient to verify the conjecture for left-compressed 3-uniform graphs with m=t-13+t-22.Regarding this conjecture,we show: If G is a left-compressed 3-uniform graph on the vertex set [t] with m edges and |[t-1]~((3))\E(G)|=p,then λ(G)λ([t-1]~((3))) provided m=(t-13)+(t-22) and t≥17p/2+11.     

Mantel's theorem for random hypergraphs

A classical result in extremal graph theory is Mantel's Theorem, which states that every maximum triangle‐free subgraph of K_n is bipartite. A sparse version of Mantel's Theorem is that, for sufficiently large p, every maximum triangle‐free subgraph of G(n, p) is w.h.p. bipartite. Recently, DeMarco and Kahn proved this for for some constant K, and apart from the value of the constant this bound is best possible. We study an extremal problem of this type in random hypergraphs. Denote by F₅, which is sometimes called the generalized triangle, the 3‐uniform hypergraph with vertex set and edge set . One of the first results in extremal hypergraph theory is by Frankl and Füredi, who proved that the maximum 3‐uniform hypergraph on n vertices containing no copy of F₅ is tripartite for n > 3000. A natural question is for what p is every maximum F₅‐free subhypergraph of w.h.p. tripartite. We show this holds for for some constant K and does not hold for . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 641–654, 2016     

Co-degree density of hypergraphs

For an r-graph H, let C(H)=minSd(S), where the minimum is taken over all (r−1)-sets of vertices of H, and d(S) is the number of vertices v such that S∪{v} is an edge of H. Given a family F of r-graphs, the co-degree Turán number is the maximum of C(H) among all r-graphs H which contain no member of F as a subhypergraph. Define the co-degree density of a family F to be

     

Triangles in C 5-free graphs and hypergraphs of girth six

We introduce a new approach and prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $$\left(1+o\left(1\right)\right)\frac{1}{3\sqrt{2}}{n}^{3∕2}.$$ We show a connection to $r$-uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced-$C_4$-free and $C_5$-free graph.     

On Sparse Parity Check Matrices

We consider the extremal problem to determine the maximal number of columns of a 0-1 matrix with rows and at most ones in each column such that each columns are linearly independent modulo . For fixed integers and , we shall prove the probabilistic lower bound = ; for a power of , we prove the upper bound which matches the lower bound for infinitely many values of . We give some explicit constructions.     

On splittable colorings of graphs and hypergraphs

The notion of a split coloring of a complete graph was introduced by Erd?s and Gyárfás [ 7 ] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)‐split coloring problem of [ 7 ] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002     

On the maximum size of connected hypergraphs without a path of given length

In this note we asymptotically determine the maximum number of hyperedges possible in an $r$-uniform, connected $n$-vertex hypergraph without a Berge path of length $k$, as $n$ and $k$ tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.     

An analytic approach to stability

The stability method is very useful for obtaining exact solutions of many extremal graph problems. Its key step is to establish the stability property which, roughly speaking, states that any two almost optimal graphs of the same order n can be made isomorphic by changing o(n²) edges.Here we show how the recently developed theory of graph limits can be used to give an analytic approach to stability. As an application, we present a new proof of the Erd?s-Simonovits stability theorem.Also, we investigate various properties of the edit distance. In particular, we show that the combinatorial and fractional versions are within a constant factor from each other, thus answering a question of Goldreich, Krivelevich, Newman, and Rozenberg.     

On the VC-dimension of uniform hypergraphs

Let be a k-uniform hypergraph on [n] where k−1 is a power of some prime p and n≥ n ₀(k). Our main result says that if , then there exists E ₀∊ such that {E∩ E ₀: E∊ } contains all subsets of E ₀. This improves a longstanding bound of due to Frankl and Pach [7].Research supported in part by NSF grants DMS-0400812 and an Alfred P. Sloan Research Fellowship.Research supported in part by NSA grant H98230-05-1-0079. Part of this research was done while working at University of Illinois at Chicago.     

Exact Bounds on the Sizes of Covering Codes

A code c is a covering code of X with radius r if every element of X is within Hamming distance r from at least one codeword from c. The minimum size of such a c is denoted by c _r(X). Answering a question of Hämäläinen et al. [10], we show further connections between Turán theory and constant weight covering codes. Our main tool is the theory of supersaturated hypergraphs. In particular, for n > n ₀(r) we give the exact minimum number of Hamming balls of radius r required to cover a Hamming ball of radius r + 2 in {0, 1}ⁿ. We prove that c _r(B _n(0, r + 2)) = _{1 i r + 1} ( ^{(n + i – 1) / (r + 1) 2}) + n / (r + 1) and that the centers of the covering balls B(x, r) can be obtained by taking all pairs in the parts of an (r + 1)-partition of the n-set and by taking the singletons in one of the parts.     

On even-cycle-free subgraphs of the hypercube

It is shown that the size of any C4k+2-free subgraph of the hypercube Qn, k?3, is o(e(Qn)).     

Squares of Hamiltonian cycles in 3‐uniform hypergraphs

We show that every 3‐uniform hypergraph H = (V,E) with |V(H)| = n and minimum pair degree at least (4/5 + o(1))n contains a squared Hamiltonian cycle. This may be regarded as a first step towards a hypergraph version of the Pósa‐Seymour conjecture.     

On the discrepancy of uniformly distributed roots of quadratic congruences

In this paper we consider the distribution of fractional parts {ν/p}, where p is a prime less than or equal to x and ν is the root in Z/pZ of a quadratic polynomial with negative discriminant. This set is known to be uniformly distributed as x→∞. Here we apply the Erd?s-Turán inequality to obtain an estimate for the discrepancy.     

Cross-intersecting sub-families of hereditary families

Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if for any i and j in {1,2,…,k} with i≠j, any set in Ai intersects any set in Aj. For a finite set X, let X² denote the power set of X (the family of all subsets of X). A family H is said to be hereditary if all subsets of any set in H are in H; so H is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family H≠{∅} of X² and any k?|X|+1, both the sum and the product of sizes of k cross-intersecting sub-families A₁,A₂,…,Ak (not necessarily distinct or non-empty) of H are maxima if A₁=A₂=?=Ak=S for some largest starSofH (a sub-family of H whose sets have a common element). We prove this for the case when H is compressed with respect to an element x of X, and for this purpose we establish new properties of the usual compression operation. As we will show, for the sum, the condition k?|X|+1 is sharp. However, for the product, we actually conjecture that the configuration A₁=A₂=?=Ak=S is optimal for any hereditary H and any k?2, and we prove this for a special case.     

Conjectures and theorems in the theory of entire functions

Motivated by the recent solution of Karlin's conjecture, properties of functions in the Laguerre–Pólya class are investigated. The main result of this paper establishes new moment inequalities for a class of entire functions represented by Fourier transforms. The paper concludes with several conjectures and open problems involving the Laguerre–Pólya class and the Riemann -function.