Graph Theory » Infinite Graphs

Strong matchings and covers ★★★

Author(s): Aharoni

Let $ H $ be a hypergraph. A strongly maximal matching is a matching $ F \subseteq E(H) $ so that $ |F' \setminus F| \le |F \setminus F'| $ for every matching $ F' $. A strongly minimal cover is a (vertex) cover $ X \subseteq V(H) $ so that $ |X' \setminus X| \ge |X \setminus X'| $ for every cover $ X' $.

Conjecture   If $ H $ is a (possibly infinite) hypergraph in which all edges have size $ \le k $ for some integer $ k $, then $ H $ has a strongly maximal matching and a strongly minimal cover.

Keywords: cover; infinite graph; matching

Posted by mdevos
updated October 23rd, 2007
add new comment
Graph Theory » Infinite Graphs

Unfriendly partitions ★★★

Author(s): Cowan; Emerson

If $ G $ is a graph, we say that a partition of $ V(G) $ is unfriendly if every vertex has at least as many neighbors in the other classes as in its own.

Problem   Does every countably infinite graph have an unfriendly partition into two sets?

Keywords: coloring; infinite graph; partition

Posted by mdevos
updated October 22nd, 2007
add new comment
Group Theory

Hall-Paige conjecture ★★★

Author(s): Hall; Paige

A complete map for a (multiplicative) group $ G $ is a bijection $ \phi : G \rightarrow G $ so that the map $ x \rightarrow x \phi (x) $ is also a bijection.

Conjecture   If $ G $ is a finite group and the Sylow 2-subgroups of $ G $ are either trivial or non-cyclic, then $ G $ has a complete map.

Keywords: complete map; finite group; latin square

Posted by mdevos
updated October 21st, 2007
add new comment