![](/files/happy5.png)
Aharoni, Ron
Strong matchings and covers ★★★
Author(s): Aharoni
Let be a hypergraph. A strongly maximal matching is a matching
so that
for every matching
. A strongly minimal cover is a (vertex) cover
so that
for every cover
.
Conjecture If
is a (possibly infinite) hypergraph in which all edges have size
for some integer
, then
has a strongly maximal matching and a strongly minimal cover.
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ \le k $](/files/tex/26d614fff037e5976f481eab5b4e36c487e120ac.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
Keywords: cover; infinite graph; matching
Aharoni-Berger conjecture ★★★
Conjecture If
are matroids on
and
for every partition
of
, then there exists
with
which is independent in every
.
![$ M_1,\ldots,M_k $](/files/tex/368dea3f4a89576f8e4eebf3241a6ef062e5b5d9.png)
![$ E $](/files/tex/aedbef97f3db174b677f00be580a095e7fefa310.png)
![$ \sum_{i=1}^k rk_{M_i}(X_i) \ge \ell (k-1) $](/files/tex/d896134dc1e4119543db8e0baaebe50b9bb34085.png)
![$ \{X_1,\ldots,X_k\} $](/files/tex/af99ea0d6ceb5907ffb549d85a7c7e711c6b91c7.png)
![$ E $](/files/tex/aedbef97f3db174b677f00be580a095e7fefa310.png)
![$ X \subseteq E $](/files/tex/3b78a133c1f7e4ab67c2c7c5a7fbba992d13e9dc.png)
![$ |X| = \ell $](/files/tex/6ed3addf64c5678ff6cd1add3575f29c9a04af48.png)
![$ M_i $](/files/tex/71c6239abfbaf80e551a379622380b245aaae23a.png)
Keywords: independent set; matroid; partition
Strong colorability ★★★
Author(s): Aharoni; Alon; Haxell
Let be a positive integer. We say that a graph
is strongly
-colorable if for every partition of the vertices to sets of size at most
there is a proper
-coloring of
in which the vertices in each set of the partition have distinct colors.
Conjecture If
is the maximal degree of a graph
, then
is strongly
-colorable.
![$ \Delta $](/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ 2 \Delta $](/files/tex/853908c29bc170f3b27832e4df3751c7626ff012.png)
Keywords: strong coloring
![Syndicate content Syndicate content](/misc/feed.png)