Search

Given two graphs H and F , the maximum possible number of copies of H in an F -free graph on n vertices is denoted by e x (n , H , F). We investigate the function e x (n , H , k F) , where k F denotes k vertex disjoint copies of a fixed graph F. Our results include cases when F is a complete graph, cycle or a complete bipartite graph. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an entropy inequality of Shearer. [ABSTRACT FROM AUTHOR]

We are given a set A of buyers, a set B of houses, and for each buyer a preference list, i.e., an ordering of the houses. A house allocation is an injective mapping τ from A to B , and τ is strictly better than another house allocation τ ′ ≠ τ if for every buyer i , τ ′ (i) does not come before τ (i) in the preference list of i. A house allocation is Pareto optimal if there is no strictly better house allocation. Let s (τ) be the image of τ i.e., the set of houses sold in the house allocation τ. We are interested in the largest possible cardinality f (m) of the family of sets s (τ) for Pareto optimal mappings τ taken over all sets of preference lists of m buyers and all sets of houses. This maximum exists since in a Pareto optimal mapping with m buyers, each buyer will always be assigned one of their top m choices. We improve the earlier upper bound on f (m) given by Asinowski et al. (2016), by making a connection between this problem and some problems in extremal set theory. [ABSTRACT FROM AUTHOR]

Given a graph F , a hypergraph is a Berge- F if it can be obtained by expanding each edge in F to a hyperedge containing it. A hypergraph H is Berge- F -saturated if H does not contain a subhypergraph that is a Berge- F , but for any edge e ∈ E (H ¯) , H + e does. The k -uniform saturation number of Berge- F is the minimum number of edges in a k -uniform Berge- F -saturated hypergraph on n vertices. For k = 2 this definition coincides with the classical definition of saturation for graphs. In this paper we study the saturation numbers for Berge triangles, paths, cycles, stars and matchings in k -uniform hypergraphs. [ABSTRACT FROM AUTHOR]

A classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theorem holds for posets, where lines are defined using the natural betweenness relation in posets. More precisely, we obtain a bound on the number of lines depending on the height of the poset. The extremal configurations are also determined. Finally, we introduce a new notion of lines in graphs and show that our result for posets can be extended to this setting. [ABSTRACT FROM AUTHOR]