Abstract The t -color Ramsey problem for hypergraph matchings was settled by the well-known result of Alon, Frankl and Lovasz (answering a conjecture of Erdős). This result was the last step in a chain of special cases most notably Lovasz’s solution to Kneser’s problem. We proposed an extension of the Erdős problem: for given 1 ≤ s ≤ t , what is the maximum number of vertices that can be covered by a matching having at most s colors in every t -coloring of the edges of the complete graph K n (or hypergraph K n r ). We revisit the first unknown case, r = 2 , s = 2 , t = 4 , where we conjectured that in every 4-coloring of K n there is a bicolored matching covering at least ⌊ 3 n ∕ 4 ⌋ vertices. We prove that this is true asymptotically by applying a recent twist of a standard application of the Regularity method: instead of lifting a (bicolored) matching of the reduced graph to regular cluster pairs, we lift a (bicolored) basic 2-matching, a subgraph whose connected components are edges and odd cycles. To find the bicolored basic 2-matching with at least ⌊ 3 n ∕ 4 ⌋ vertices in every 4-coloring of K n we use Tutte’s minimax formula.