arXiv Analytics

Sign in

arXiv:1710.04633 [math.CO]AbstractReferencesReviewsResources

A generalization of Erdős' matching conjecture

Christos Pelekis, Israel Rocha

Published 2017-10-12Version 1

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$.

Related articles: Most relevant | Search more
arXiv:1311.6291 [math.CO] (Published 2013-11-25, updated 2015-11-12)
A generalization of weight polynomials to matroids
arXiv:1406.4022 [math.CO] (Published 2014-06-16, updated 2015-06-26)
Some $q$-congruences for homogeneous and quasi-homogeneous multiple $q$-harmonic sums
arXiv:1310.0851 [math.CO] (Published 2013-10-02, updated 2014-04-04)
A generalization of Aztec diamond theorem, part I