Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFractionally balanced hypergraphs and rainbow KKM theorems
352
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A $d$-partite hypergraph is called fractionally balanced if there exists a non-negative function on its edge set that has constant degrees in each vertex side. Using a topological version of Halls theorem we prove lower bounds on the matching number of such hypergraphs. These, in turn, yield results on mulitple-cake division problems and rainbow matchings in families of $d$-intervals.
rate research
Read More
An oriented hypergraph is an oriented incidence structure that allows for the generalization of graph theoretic concepts to integer matrices through its locally signed graphic substructure. The locally graphic behaviors are formalized in the subobject classifier of incidence hypergraphs. Moreover, the injective envelope is calculated and shown to contain the class of uniform hypergraphs -- providing a combinatorial framework for the entries of incidence matrices. A multivariable all-minors characteristic polynomial is obtained for both the determinant and permanent of the oriented hypergraphic Laplacian and adjacency matrices arising from any integer incidence matrix. The coefficients of each polynomial are shown to be submonic maps from the same family into the injective envelope limited by the subobject classifier. These results provide a unifying theorem for oriented hypergraphic matrix-tree-type and Sachs-coefficient-type theorems. Finally, by specializing to bidirected graphs, the trivial subclasses for the degree-$k$ monomials of the Laplacian are shown to be in one-to-one correspondence with $k$-arborescences.
A graph $G$ whose edges are coloured (not necessarily properly) contains a full rainbow matching if there is a matching $M$ that contains exactly one edge of each colour. We refute several conjectures on matchings in hypergraphs and full rainbow matchings in graphs, made by Aharoni and Berger and others.
In arXiv:1709.07504 Aguiar and Ardila give a Hopf monoid structure on hypergraphs as well as a general construction of polynomial invariants on Hopf monoids. Using these results, we define in this paper a new polynomial invariant on hypergraphs. We give a combinatorial interpretation of this invariant on negative integers which leads to a reciprocity theorem on hypergraphs. Finally, we use this invariant to recover well-known invariants on other combinatorial objects (graphs, simplicial complexes, building sets etc) as well as the associated reciprocity theorems.
Drisko proved that $2n-1$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n$. For general graphs it is conjectured that $2n$ matchings suffice for this purpose (and that $2n-1$ matchings suffice when $n$ is even). The known graphs showing sharpness of this conjecture for $n$ even are called badges. We improve the previously best known bound from $3n-2$ to $3n-3$, using a new line of proof that involves analysis of the appearance of badges. We also prove a cooperative generalization: for $t>0$ and $n geq 3$, any $3n-4+t$ sets of edges, the union of every $t$ of which contains a matching of size $n$, have a rainbow matching of size $n$.
In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers $n$ and $k$, the expression $aw([n],k)$ denotes the smallest number of colors with which the integers ${1,ldots,n}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. We establish that $aw([n],3)=Theta(log n)$ and $aw([n],k)=n^{1-o(1)}$ for $kgeq 4$. For positive integers $n$ and $k$, the expression $aw(Z_n,k)$ denotes the smallest number of colors with which elements of the cyclic group of order $n$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. In this setting, arithmetic progressions can wrap around, and $aw(Z_n,3)$ behaves quite differently from $aw([n],3)$, depending on the divisibility of $n$. As shown in [Jungic et al., textit{Combin. Probab. Comput.}, 2003], $aw(Z_{2^m},3) = 3$ for any positive integer $m$. We establish that $aw(Z_n,3)$ can be computed from knowledge of $aw(Z_p,3)$ for all of the prime factors $p$ of $n$. However, for $kgeq 4$, the behavior is similar to the previous case, that is, $aw(Z_n,k)=n^{1-o(1)}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
