User dave pritchard - MathOverflow

Answer by Dave Pritchard for k-uniform k-partite hypergraph matching in polynomial time

2012-04-06T04:19:56Z

I'm assuming that by matching number, you mean the maximum number of pairwise disjoint edges. There are a few viewpoints you might want to try. One is that the maximum matching is the same as the maximum independent set of the dual hypergraph. (Hypergraphs have weak independent sets where no edge is completely contained, and strong independent sets where you pick no two points from any edge; here I mean strong.) Moreover, the independent sets of a hypergraph are the same as the independent sets of the 1-skeleton (where every hyperedge is replaced by a clique). So possibly, there are classes of graphs for which independent set is polynomial-time solvable, which have an interpretation as coming from 3-partite 3-uniform hypergraphs. Bounded treewidth is one concrete example to try.

One class of hypergraphs where matching is in P, is for interval hypergraphs. But, the class of 3-partite 3-uniform interval hypergraphs is very limited. Here's one more general class that is poly-time solvable: the set of 3-partite 3-uniform hypergraphs where each of the 3 vertex parts have labels ${1, 2, ..., n/3},$ and where for every edge the labels of its three vertices are within a constant distance of each other. You can show using dynamic programming that the matching problem is solvable here in polynomial time. On the other hand, that's not really making essential use of the 3-partite or 3-uniformness.

If you're looking for leads I would suggest "Hypergraphs," Part VIII of Schrijver's Combinatorial Optimization book. It discusses what properties of hypergraphs are sufficient to give poly-time solutions to basic quantities such as the matching number.

Answer by Dave Pritchard for Proofs without words

2010-05-15T22:32:52Z

Means inequalities:

The image was sent to me by James M. Lawrence, grazie! See also page 53 of "Proofs without words: exercises in visual thinking, Volume 2" for a very different layout of the same 4 inequalities.

Another one exists involving the sum $$1^3 + 2^3 + \cdots + n^3:$$

The second image is due to Brian Sears

Domination in Nice Lattices

2011-02-22T13:28:37Z

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.

Call a lattice nice if it is of the form $\mathbb{Z}$-span({$v_1, v_2, \dotsc, v_m$}), where all $v_i$ are nice. (Note: the $v_i$ are not necessarily linearly independent so $m$ could be larger than the dimension; although WOLOG $m \le \tbinom{n}{2}$.)

Is the following decision problem in P?

INPUT: a nice lattice and a vector $x \in \mathbb{Z}^n$
QUESTION: does the lattice contain a $y$ such that $y_i \ge x_i$ for all $i=1, \dotsc, n$?

Motivation and background:

in general lattices, the problem is NP-complete (via the unbounded knapsack problem)
if this problem lies in P, one can solve an interesting more general problem

A possibly interesting partial result would be to demonstrate any useful structure for nice lattices!

(I posted a flow formulation of the problem on cstheory)

Hypergraph Chromatic Number vs Degree, Clique-Size

2010-11-29T11:16:01Z

For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be the maximum number of hyperedges containing any vertex. Let $\omega$ be the maximum size of a clique, meaning a vertex set such that for every pair of vertices in the clique, some edge contains both.

Question: is there $\epsilon>0$ so that $\chi \le \Delta \omega / (1+\epsilon)$ in all hypergraphs?

Motive: let $R$ be the maximum edge size. A simple greedy algorithm for colouring can be used to establish that $\chi \le 1 + \Delta(R-1)$, and this bound cannot be improved in general. Note $\chi \ge \omega \ge R$; so I am essentially asking if $\omega$ approximates $\chi$ more closely than $R$.

Answer by Dave Pritchard for Truthful multi-unit auctions that guarantee selling all items

2011-01-21T12:31:39Z

The answer is No. There exists a truthful auction for $k=2$ items and 3 players meeting the standard assumptions (non-negative payments, and payments must not exceed bids) which always has revenue at least two times the minimum bid, but where the winners do not correspond to the top two bids.

For clarity in contrast to the subscripts in the question, I'll denote indices for players using superscripts.

Here is the auction.

If $b^1=b^2$, then players 1 and 2 win.

Otherwise, the two players with the top two bids win, breaking ties arbitrarily.

Charge both winners $\mathrm{min}\{b^1, b^2, b^3\}$.

Clearly, the payments are non-negative, the prices never exceed the bids, and for a bid $b^1=b^2=x, b^3=y$ with $x < y$ we have that player 3 loses, despite having the unique highest bid.

To show it is truthful, we need to show that for each player $i$, and each pair of bids $b^{-i}$ by her opponents, the set $\{b^i \mid i \textrm{ wins for bids } (b^i, b^{-i})\}$ is up-closed.

$i=3$ and in $b^{-3}$, $b^1=b^2$: there are no $b^i$ for which $i$ wins in $(b^i, b^{-i})$
$i=3$ and in $b^{-3}$, $b^1\neq b^2$: $i$ wins in $(b^i, b^{-i})$ when $b^i > \min(b^{-i})$ and loses when $b^i < \min(b^{-i})$
$i=1$ and in $b^{-1}$, $b^2 > b^3$: $i$ wins in $(b^i, b^{-i})$ when $b^i > b^3$, and loses when $b^i < b^3$
$i=1$ and in $b^{-1}$, $b^2 = b^3$: $i$ wins in $(b^i, b^{-i})$ when $b^i \ge b^2$, and loses when $b^i < b^2$
$i=1$ and in $b^{-1}$, $b^2 < b^3$: $i$ wins in $(b^i, b^{-i})$ when $b^i \ge b^2$, and loses when $b^i < b^2$
The case $i=2$ is symmetric to $i=1$. So, we are done.

Note that it seems some sort of "weird tie-breaking" is necessary: I think one can show that in every profile with distinct bids, the top two bids necessarily win.

Answer by Dave Pritchard for Coloring edges on a graph s.t. the set of edges for any two vertices have no more than 'k' colors in common

2010-12-17T15:59:37Z

If the input number $k$ is very large (say as large as the next-to-maximum degree) then condition (2) has no effect, and this becomes the same as $N$-edge-colouring of a graph, which is NP-complete. (Have you read about this problem? It's NP-complete even for 3-regular graphs and $N=3$.) So if I understand correctly it does not seem that there is any hope of exactly solving this problem with an efficient algorithm. There are lots of results about finding an edge-colouring with approximately the minimum number of colours, classical ones include Vizing's theorem.

My brain can't parse the phrase "...bounds on the size of vertex edge sets..." but maybe in the last question you mean, is the problem easy if $k$ is small enough? In the case of 3-regular graphs with $N=3$, it makes it easier but for a trivial reason: no colouring meeting (1) and (2) is possible for any such graph if $k<3$, since any colouring meeting (1) would have to have all 3 colours appearing adjacent to every vertex.

Answer by Dave Pritchard for On the number of antichains of a poset

2010-12-15T16:54:16Z

To me, if the goal is upper-bounding the number of antichains in the original poset, doing an "embedding" seems more complex than necessary. Can't you use just use Dilworth's theorem and then appeal to the fact that any antichain contains at most one element of each chain?
It looks to me that the formula you give for the number of antichains in your "rectangle" is wrong, for example, choosing one element from each of the chains, gives at least $a^d$ different antichains, and this doesn't even count all of them.

Answer by Dave Pritchard for Online Library of Unlabeled Connected Graphs on n Vertices

2010-11-17T19:01:30Z

You can use the geng tool that comes as part of nauty here, or grab a list of graphs on up to 10 vertices here (it also has some special classes). It's unlikely you will be able to fit a file of all 50502031367952 graphs on 13 vertices on your computer!

Answer by Dave Pritchard for An edge partitioning problem on cubic graphs

2010-11-02T20:56:41Z

Thank you for the clarifications (the original post did not say each part should have size 3, maybe you can add that). ~~I will take a stab, but it is not very clever so possibly I missed something.~~

Note,

for a given triple of edges, its subgraph has $\ge 3$ nodes with equality iff it is a triangle

thus for a given partition into $|E|/3$ triples, the sum of this over all parts is $\ge |E|$ with equality iff every triple forms a triangle.

However, it is known, due to Holyer 1981, that it's NP-complete to determine whether a graph can be edge-partitioned into triangles. So I think your problem is also NP-complete on these instances (taking $t=|E|$).

RE: your comment, thanks, I forgot it is cubic!

Answer by Dave Pritchard for union of matroid intersection

2010-10-11T14:09:00Z

The concept of "strongly base orderable" matroids seems to fit the bill, see for example

http://lemon.cs.elte.hu/egres/open/Base_orderable_matroid

In particular, partition matroids are strongly base orderable and a "union of intersections" theorem was proven by Davies and McDiarmid.

Cliques of hyperedges

2010-10-05T10:27:22Z

Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two categories:

A star: there is a vertex such that every edge of $C$ contains it
A triangle: there are three vertices such that every edge of $C$ goes between two of them

What kind of patterns persist for hypergraphs of rank $\le r$? (It has a vertex set, and "hyper"edges which are arbitrary sets of size at most $r$. Again an edge-clique is a family of pairwise intersecting edges.)

I believe one can show the following structure theorem: for every clique $C$, there is a set $S$ of at most $f(r)$ vertices, such that every pair of edges $C$ meet at at least one vertex in $S$. But the bound I have on $f(r)$ is something like doubly exponential. What is the best possible?

Note that $f(r) \ge \Omega(r^2)$ by considering projective planes.

Cross-post asking for a good algorithm to find a max-clique: http://cstheory.stackexchange.com/questions/1846/max-clique-in-line-graph-of-hypergraph

Answer: I have found there was a series of results on this function $f$, and that this set $S$ is often called a kernel. The best current bounds on $f$ are due to Tuza (Tuza, Z. (1985) Critical hypergraphs and intersecting set-pair systems. J. Combin. Theory Ser. B 39 134–145.); in short $f(r) = \Theta(4^r/\sqrt{r})$.

Answer by Dave Pritchard for Bounds on strong vertex colourings of regular hypergraphs?

2010-09-23T10:10:24Z

There is a wide variety of hypergraphs for which $k(\omega-1)+1$ is tight or nearly-tight. I also think this is an interesting question, and was looking in to it recently.

First, a $(v, x, 2)$-Steiner system is a partition of the edges of $K_v$ into disjoint $x$-cliques (i.e., each of the $\tbinom{v}{2}$ edges appears in exactly one of the cliques). Whenever $v \ge x^2$, it is known that a $(v', x', 2)$-Steiner system exists where $v' \approx v, x'\approx x$ up to a factor of 2. Then build a hypergraph whose hyperedges are the $x$-cliques. This hypergraph has strong chromatic number $v$ but this actually equals the trivial upper bound of (max degree)(max edge size-1)+1.

Second, for arbitrary max-degree $k>1$ and even edge size $\omega$ there is an elementary example I saw in Agnarsson et al. Take a clique of size $k+1$ and blow up every vertex into a group of $\omega/2$ vertices -- so for every two groups, there is a hyperedge containing them. The strong chromatic number is $(k+1)\omega/2$ which is about half the trivial upper bound.

Eventually I became interested in the following: while the max edge size is a trivial lower bound on the strong chromatic number, the largest clique (set of vertices such that all pairs are contained in a mutual edge) is a larger lower bound (although it's not findable in polynomial time). Can we get good bounds parameterized by the max clique size and the max degree?

How much must deleting a spanning tree reduce edge-connectivity?

2010-09-05T09:27:33Z

Suppose you have a 100-edge connected graph (e.g. an infrastructure network). You want to delete the edges of a spanning tree, any spanning tree you choose (e.g. to sell a connected subnetwork). What is the most edge-connectivity you can guarantee in the remaining graph?

Formally: let $r(k)$ be $$\min_{G: k \textrm{ edge-connected}} ~~ \max_{T} ~~ \textrm{edge-connectivity}(G \backslash E(T))$$ where $T$ ranges over spanning trees of $G$, then what is $r(k)$?

I feel that in general, starting from a $k$-edge-connected graph, one should be able to leave edge-connectivity $k-o(k)$. However, the only useful bound I see so far is that "Every $2t$-edge-connected graph has $t$ spanning trees" implies $r(k) \ge \lfloor k/2 \rfloor - 1$. This is far from tight with respect to the best upper bound I can prove, $r(k) \le k-3$.

Answer by Dave Pritchard for Symmetry of the integer gap

2010-09-03T09:11:52Z

Here is an example showing this is impossible, I think. The integrality gap for "independent set" can be up to $n/2$ on a graph with $n$ vertices. But its dual is the naive LP relaxation of edge cover on the same graph; you can show a constant integrality gap upper bound for this by standard methods (and Ojas Parekh proves in his thesis that the best possible bound is 4/3).

This example behaves similarly if you care about the approximability, I have worked on a paper which motivated my example above.

Answer by Dave Pritchard for Proving that a binary matrix is totally unimodular

2010-09-03T09:00:18Z

Here are some common ways of proving a matrix is TU.

The incidence matrix of a bipartite graph and network flow LPs are TU; these are standard examples usually taught in every book on TU.
The consecutive-ones property: if it is (or can be permuted into) a 0-1 matrix in which for every row, the 1s appear consecutively, then it is TU. (The same holds for columns since the transpose of a TU matrix is also TU.)
Every "network matrix," defined as follows, is TU (and they are a fundamental building block of the set of all TU matrices, according to Seymour's theorem). The rows correspond to a tree $T = (V, R)$ each of whose arcs have an orientation (i.e. it is not necessary that exist a root vertex $r$ such that the tree is "rooted into $r$" or "out of $r$").The columns correspond to another set $C$ of arcs on the same vertex set $V$. To compute the entry at row $R$ and column $C = st$, look at the $s$-to-$t$ path $P$ in $T$, then the entry is:
Ghouila-Houri showed a matrix is TU iff for every subset $R$ of rows, there is an assignment $s : R \to \pm 1$ of signs to rows so that the signed sum $\sum_{r \in R} s(r)r$ (which is a row vector the same width as the matrix) has all its entries in $\{0, \pm1\}$.

There are other if-and-only-if conditions like Ghouila-Houri too (see Schrijver 1998) but the 4 conditions I gave above have been the most practical for me.

Finding Two Rainbow Spanning Trees

2010-05-24T21:00:03Z

Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.

Is the following problem NP-complete? Determine whether there are two edge-disjoint spanning trees, such that in each individual tree, no colour appears twice.

I am curious because the variant "determine whether there are two edge-disjoint spanning trees, such that in the union of the trees, no colour appears twice" is solvable in polynomial time, for example using matroid theory.

Answer by Dave Pritchard for Funky congruences

2010-05-22T19:55:05Z

Here is an alternative approach, by reducing the problem to 2-SAT. It makes me ask: what if there were three values $(a_i^0, a_i^1, a_i^2)$ for each $i$ (and $b_i$'s in {0, 1, 2})? It analogously can be reduced to some type of 2-SAT with ternary-valued variables. I don't know immediately whether either of these more general problems is NP-complete.

We need the following Theorem: Suppose we have a collection of modular constraints on $m$, of the form $\{m \equiv v_i \; (\mod{c_i})\}_{i=1\ldots n}$. Then there is no $m$ meeting all constraints iff there are two particular constraints $1 \le j < k \le n$ so that no $m$ simultaneously satisfies those two constraints.

The proof is given later below. But, assuming the theorem, we just need to determine whether $b$ exists such that all pairs of two constraints $m \equiv a_j^{b_j} \; (\mod{c_j}), m \equiv a_k^{b_k} \; (\mod{c_k})$ are pairwise satisfiable. This can be done with 2-SAT: it is easy to check which pairs of $b^j, b^k$ allow a mutual solution (see Wadim's note in his first 2 lines), then for each pair $(j, k)$ we get up to 4 constraints depending on which pairs of values for $b_j, b_k$ can hold at the same time. For example if $a_j^0 = 5, c_j^0 = 20, a_k^0 = 6, c_k^0 = 42$, we see $b_j=0, b_k=0$ cannot both hold, since $m$ would have to be both even and odd. Thus we add the clause $(b^j = 1$ OR $b^k = 1)$ to our 2-SAT instance. Repeating this gives $O(n^2)$ clauses, then we run a linear-time 2-SAT algorithm to see if $b$ exists meeting all clauses, and are done.

Proof: $\Leftarrow$ is clear, so it suffices to prove the contrapositive of $\Rightarrow$. Thus, assume we can satisfy any given two constraints; we'll constrct an $m$ that satisfies all constraints.

We focus on one prime $p$ at a time. Let $p^t$ be the maximum power of $p$ dividing any $b_i$, and let $\ell$ (which depends on $p$) be the maximizer, so $p^t | b_\ell$. The $m$ we hope to construct must satsify $m \equiv b_\ell \; (\mod{p^t})$, call this a crazy constraint. We get one crazy constraint for each prime dividing $c_1c_2\cdots c_n$. Moreover, for any $m$ that satisfies this crazy constraint, using Wadim's note twice, we deduce that $m \equiv v_i \; (\mod{\gcd(p^t, c_i)})$ for each $i$. But $\gcd(p^t, c_i)$ is just the highest power of $p$ dividing $c_i$. Thus by CRT, an $m$ which satisfies all crazy constraints (i.e. for all $p$), satisfies $m \equiv v_i \; (\mod{c_i})$, and hence all $n$ of the "input" constraints. But the crazy constraints are for relatively prime moduli, hence they all simultanouesly hold for some $m$, and we are done.

Answer by Dave Pritchard for Texts on the General History of Contemporary Combinatorics

2010-05-20T02:21:31Z

Schrijver's "Combinatorial Optimization" 3-book set/CD has smidgeons of history (they are self-evident from section titles in the table of contents)... for example it is pretty bad-ass in terms of thoroughness for the history of matroids. It may be too old or too computational for your target but may be ok.

Does this approach for the Poincare conjecture work?

2010-05-06T13:42:20Z

Several months ago a paper was posted at http://arxiv.org/abs/1001.4164 called "Another way of answering Henri Poincare's fundamental question." The author gave a talk on it today at my institution. If it's correct, it is a major breakthrough in terms of proof length (~10 pages). However, it is very outside my specialty. There's apparently been very little feedback, but the author is ok with public discussion. Therefore, can anyone say whether they have read the paper? Whether it is correct, missing details, clearly flawed, or what have you?

Answer by Dave Pritchard for Weighted Regular Graphs

2010-05-06T12:43:21Z

Here's an observation about a relation between regular and weighted-regular graphs, when loops are disallowed.

From any weighted-regular graph with (wolog by the polyhedral characterization) integral weights, replace each vertex v with weight(v) clones. The new graph has |V| equal to the original weight sum. For each edge uv in the old graph, connect every clone of u to every clone of v in the new graph (so there is a complete bipartite $K_{weight(u), weight(v)}$ between the clones of u and v). Then this is a regular graph.

Conversely, you can reverse this, so you should be able to define a one-to-many type of "quotient" (to reverse the above construction) which takes any regular graph to a weighted-regular graph, and is surjective (generates all loopless weighted-regular graphs).

Answer by Dave Pritchard for What are the Applications of Hypergraphs

2010-03-09T10:15:56Z

Hypergraphs have been very useful algorithmically for the following "Steiner tree problem:" given a graph (V, E) with a specified "required/terminal" vertex subset R of V and a cost for each edge, find a minimum-cost set of edges which connects all the terminals (and includes whatever subset of V \ R you like). Any minimal solution is a tree all of whose leaves are terminals (a so-called Steiner tree).

Hypergraphs are useful because there is a "full component decomposition" of any Steiner tree into subtrees; the problem of reconstructing a min-cost Steiner tree from the set of all possible full components is the same as the min-cost spanning connected hypergraph problem (a.k.a. min hyper-spanning tree problem) for a hypergraph whose vertex set is R. That's the approach used by many modern algorithms for the Steiner tree problem (whether they are integer-program based exact algorithms that are actually implemented, or non-implemented approximation algorithms with good provable approximation guarantees).

I like this application since one must view the hypergraph as "like a graph" (want it to be connected and acyclic) and not like a set system. This approach was used implicitly starting around 1990 by Zelikovsky and brought out more explicitly around 1997 by (I think) Warme and Prömel & Steger. A very cute paper using this approach is coming out at STOC 2010 by Byrka et al. As an $\epsilon$-shameless self-reference, there is more information in my thesis which then delves into linear programming relaxations for this approach.

Comment by Dave Pritchard

2012-04-29T15:46:12Z

The family I had in mind is the following: number the vertices 1, 2, 3, 4, 5, ... (3-partiteness and 3-uniformity are not actually needed so I will drop that) and assume that for each two vertices i, j in a common hyperedge, |i-j| <= C for a fixed constant C. Then you can compute a max matching in exp(C)*poly(n) time. The dynamic program table has an entry [k, S] for every 1<=k<=n and subset S of k+1..k+C, meaning "what's the maximum matching in the induced subhypergraph on vertex set {1, 2, .., k} union S?" It's a lot like typical DP on bounded-treewidth graphs (and generalizes to trees too).

Comment by Dave Pritchard

2012-04-05T05:21:37Z

I don't understand what you mean by "picking any non-zero x_S also gives the same approximation factor." and I also don't understand your main question, which is probably related?

Comment by Dave Pritchard

2011-10-27T16:30:47Z

Matroids and linking systems is similar to the material in Schrijver's thesis as well as some papers he wrote around the same time with "linking system" in the title. The papers are not a bad substitute, but the book has longer discussion generally of high quality.

Comment by Dave Pritchard

2011-02-24T11:47:35Z

Yes, your comments are valid. Tony, more generally than what you state, the problem becomes poly-time solvable if all of the nonzero entries form a chain under division (e.g., all 1s, 2s, 6s, 30s...)

Comment by Dave Pritchard

2011-02-17T09:47:01Z

I am curious about the same question, but maybe in a simpler example like ABCADEA vs ADEABCA.

Comment by Dave Pritchard

2011-02-07T19:20:52Z

I believe the best known bound is given by Tuza (Tuza, Z. (1985) Critical hypergraphs and intersecting set-pair systems. J. Combin. Theory Ser. B 39 134–145), at a coarse level it is $N(k)=\Theta(4^k/\sqrt{k})$

Comment by Dave Pritchard

2011-01-24T19:10:19Z

That's great! That totally answers the original question as far as I can see, assuming $\Delta, R \ge 2$ (and I notice now my conjecture was false for $\Delta = 1$), since for bounded $\Delta(R-1)$ we must have that $\Delta$ and $R$ are bounded, in which case $\Delta(R-1)+1$ is indeed at most $\Delta\omega/(1+\epsilon)$.

Comment by Dave Pritchard

2011-01-19T18:18:09Z

Looks nice, but did you mean $R \times P \cup P \times R$ at the end? I wonder if it would be useful to push that idea further and get things like $R \times P \times P \cup P \times R \times P \cup P \times P \times R$ (maybe possible or not, maybe useful or not, I haven't thought yet)

Comment by Dave Pritchard

2010-12-17T16:43:24Z

Ok, thanks! BTW the term is typically called "the degree of a vertex," connectivity already has a different standard meaning. It doesn't seem obvious to me whether or not this problem is NP-hard when $k=1$, so it is a good and interesting clarification.

Comment by Dave Pritchard

2010-12-16T09:15:06Z

I thought some more about the $f(n, n)$ problem and got as far as the following. A natural approach is to build a rainbow matching as large as possible (maybe using "augmenting paths") while exposing the colour of one edge at a time. I think this easily gives a rainbow matching of size $n - O(\sqrt{n})$ (w/o augmenting paths). But the last bits are very difficult; even in the unlikely scenario that the first $n-1$ edges we look at form a rainbow matching, I can't figure out any exposure argument to get a rainbow matching of size $n$.

Comment by Dave Pritchard

2010-12-13T16:23:04Z

For what it's worth, your definition is fairly complex and not super-closely related to anything I have seen before, so it would be surprising if these notions have been studied, in my opinion. If there is any chance it exists, you could try looking in the literature on multi-way cuts or multicuts.

Comment by Dave Pritchard

2010-12-13T11:12:38Z

Thanks for the clarification; I missed earlier, but see now, that without the $\omega(n)$ term, the probability of a bad set of coupons is a fixed positive number depending on $k$ but not $n$, so it's really needed. The calculation is great too.

Comment by Dave Pritchard

2010-12-13T11:10:25Z

Note that the "each vertex has one edge of each color" is not part of the original problem, so the "relevant Latin square question" is not a re-statement of what was discussed earlier. (But, of course similar methods could in principle apply, and they are indeed very much related.)

Comment by Dave Pritchard

2010-12-12T11:07:02Z

The second question, whether $f(n, n)$ exists, is quite interesting! (I.e., whether $K_{n, n}$ with a random $n$-colouring a.a.s has a rainbow perfect matching.) It looks to me that the expected number of rainbow perfect matchings is $(n!)^2/n^n$ which is huge; nonetheless the first thing I tried to prove that 1 exists a.a.s, the second moment method, doesn't seem to help.

Comment by Dave Pritchard

2010-12-12T10:34:49Z

I left & deleted a comment due to confusion about reading the problem statement. It was a little confusing for me but I eventually understood you are picking a $f(k, n)$-edge subgraph of $K_{n, n}$ uniformly at random, and then assigning each edge one of $k$ colours uniformly at random; you want to compute $f$ so there is a $k$-edge rainbow matching w.h.p. Finally, you are considering only the asymptotics of $n \to \infty$, since otherwise "w.h.p" makes no sense.