Search

A digraph G immerses a digraph H if there is an injection f: V(H) → V(G) and a collection of pairwise edge-disjoint directed paths Puv, for uv ∈ E(H), such that Puv starts at f(u) and ends at f(v). We prove that every Eulerian digraph with minimum out-degree t immerses a complete digraph on Ω(t) vertices, thus answering a question of DeVos, McDonald, Mohar and Scheide. [ABSTRACT FROM AUTHOR]

A well-known conjecture of Frankl and Füredi from 1989 states that an initial segment of the colexicographic order has the largest Lagrangian of any r-uniform hypergraph with m hyperedges. We show that this is true when r = 3. We also give a new proof of a related conjecture of Nikiforov for large t and a counterexample to an old conjecture of Ahlswede and Katona. [ABSTRACT FROM AUTHOR]

Let x 1 , ... , x n ∈ R d be unit vectors such that among any three there is an orthogonal pair. How large can n be as a function of d, and how large can the length of x 1 + ⋯ + x n be? The answers to these two celebrated questions, asked by Erdős and Lovász, are closely related to orthonormal representations of triangle-free graphs, in particular to their Lovász ϑ -function and minimum semidefinite rank. In this paper, we study these parameters for general H-free graphs. In particular, we show that for certain bipartite graphs H, there is a connection between the Turán number of H and the maximum of ϑ (G ¯) over all H-free graphs G. [ABSTRACT FROM AUTHOR]

The problem of finding dense induced bipartite subgraphs in H-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. In this paper, we obtain several results in this direction. First we prove that any H-free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least cH log d/log log d, thus nearly confirming one and proving another conjecture of Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdœs, Janson, Łuczak and Spencer. [ABSTRACT FROM AUTHOR]

For a positive integer k, we say that a graph is k-existentially complete if for every 0 ⩽ a ⩽ k, and every tuple of distinct vertices x1, ..., xa, y1, ..., yk−a, there exists a vertex z that is joined to all of the vertices x1, ..., xa and to none of the vertices y1, ..., yk−a. While it is easy to show that the binomial random graph Gn,1/2 satisfies this property (with high probability) for k = (1 − o(1)) log2n, little is known about the "triangle-free" version of this problem: does there exist a finite triangle-free graph G with a similar "extension property"? This question was first raised by Cherlin in 1993 and remains open even in the case k = 4. We show that there are no k-existentially complete triangle-free graphs on n vertices with k > 8 log n log log n , for n sufficiently large. [ABSTRACT FROM AUTHOR]