ARTICLE
TITLE

A Generalization of Erdos' Matching Conjecture

SUMMARY

Let H=(V,E)\mathcal{H}=(V,\mathcal{E}) be an rr-uniform hypergraph on nn vertices and fix a positive integer kk such that 1=k=r1\le k\le r. A kk-matching of H\mathcal{H} is a collection of edges M?E\mathcal{M}\subset \mathcal{E} such that every subset of VV whose cardinality equals kk is contained in at most one element of M\mathcal{M}. The kk-matching number of H\mathcal{H} is the maximum cardinality of a kk-matching. A well-known problem, posed by Erdos, asks for the maximum number of edges in an rr-uniform hypergraph under constraints on its 11-matching number. In this article we investigate the more general problem of determining the maximum number of edges in an rr-uniform hypergraph on nn vertices subject to the constraint that its kk-matching number is strictly less than aa. The problem can also be seen as a generalization of the well-known kk-intersection problem. We propose candidate hypergraphs for the solution of this problem, and show that the extremal hypergraph is among this candidate set when n\ge 4r\binom{r}{k}^2\cdot an\ge 4r\binom{r}{k}^2\cdot a.

 Articles related

Benjamin Gunby, Maxwell Fishelson    

A classic result of Marcus and Tardos (previously known as the Stanley-Wilf conjecture) bounds from above the number of nn-permutations (s?Sn\sigma \in S_n) that do not contain a specific sub-permutation. In particular, it states that for any fixed permu... see more


Eliza Jackowska, Joanna Polcyn, Andrzej Rucinski    

In this paper we confirm a special, remaining case of a conjecture of Füredi, Jiang, and Seiver, and determine an exact formula for the Turán number ex3(n;P33)\mathrm{ex}_3(n; P_3^3) of the 3-uniform linear path P33P^3_3 of length 3, valid for ... see more


Zoltán Füredi, Alexandr Kostochka, Ruth Luo    

We consider two extremal problems for set systems without long Berge cycles. First we give Dirac-type minimum degree conditions that force long Berge cycles. Next we give an upper bound for the number of hyperedges in a hypergraph with bounded circumfere... see more


Stanislaw Radziszowski    

We present data which, to the best of our knowledge, includes all known nontrivial values and bounds for specific graph, hypergraph and multicolor Ramsey numbers, where the avoided graphs are complete or complete without one edge. Many results pertaining... see more


Csilla Bujtás, Michael Henning, Zsolt Tuza, Anders Yeo    

In 2012, the first three authors established a relationship between the transversal number and the domination number of uniform hypergraphs. In this paper, we establish a relationship between the total transversal number and the total domination number o... see more