We derive a simple bijection between geometric plane perfect matchings on 2 points in convex position and triangulations on points in convex position. We then extend this bijection to monochromatic plane perfect matchings on periodically -colored vertices and -gonal tilings of convex point sets. These structures are related to a generalization of Temperley-Lieb algebras and our bijections provide explicit one-to-one relations between matchings and tilings. Moreover, for a given element of one class, the corresponding element of the other class can be computed in linear time.

We exhibit a 5-uniform hypergraph that has no polychromatic 3-coloring, but all its restricted subhypergraphs with edges of size at least 3 are 2-colorable. This disproves a bold conjecture of Keszegh and the author, and can be considered as the first step to understand polychromatic colorings of hereditary hypergraph families better since the seminal work of Berge. We also show that our method cannot give hypergraphs of arbitrary high uniformity, and mention some connections to panchromatic colorings.

A paired-dominating set of a graph is a dominating set with the additional requirement that the induced subgraph [] contains a perfect matching. We prove that the vertex set of every claw-free cubic graph can be partitioned into two paired-dominating sets.

A (USO) is an orientation of the -dimensional hypercube graph such that every non-empty face contains a unique sink. We consider the only known connected on USOs. This flip graph is based on the following theorem due to Schurr: given any -dimensional USO and any one dimension  , the set of edges connecting vertices along dimension can be decomposed into equivalence classes (so-called ), such that flipping the direction of any yields another USO if and only if is the union of some of these phases. In this paper we provide an algorithm to compute the phases of a given USO in time, significantly improving upon the previously known trivial algorithm. We also show that the phase containing a given edge can be flipped using only () space additional to the space required to store the USO. We contrast this by showing that given a boolean circuit of size () succinctly encoding an -dimensional USO, it is -complete to determine whether two given edges are in the same phase. Finally, we also prove some new results on the structure of phases.