{
"id": "1710.04633",
"version": "v1",
"published": "2017-10-12T17:36:47.000Z",
"updated": "2017-10-12T17:36:47.000Z",
"title": "A generalization of ErdÅ‘s' matching conjecture",
"authors": [
"Christos Pelekis",
"Israel Rocha"
],
"comment": "11 pages",
"categories": [
"math.CO"
],
"abstract": "Let $\\mathcal{H}=(V,\\mathcal{E})$ be an $r$-uniform hypergraph on $n$ vertices and fix a positive integer $k$ such that $1\\le k\\le r$. A $k$-\\emph{matching} of $\\mathcal{H}$ is a collection of edges $\\mathcal{M}\\subset \\mathcal{E}$ such that every subset of $V$ whose cardinality equals $k$ is contained in at most one element of $\\mathcal{M}$. The $k$-matching number of $\\mathcal{H}$ is the maximum cardinality of a $k$-matching. A well-known problem, posed by Erd\\H{o}s, asks for the maximum number of edges in an $r$-uniform hypergraph under constraints on its $1$-matching number. In this article we investigate the more general problem of determining the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices subject to the constraint that its $k$-matching number is strictly less than $a$. The problem can also be seen as a generalization of the, well-known, $k$-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 a$.",
"revisions": [
{
"version": "v1",
"updated": "2017-10-12T17:36:47.000Z"
}
],
"analyses": {
"keywords": [
"matching conjecture",
"uniform hypergraph",
"generalization",
"matching number",
"maximum number"
],
"note": {
"typesetting": "TeX",
"pages": 11,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}