Search Results

If $n$ is a power of two (i.e. if $n=2^m$), you can do quite a bit better-- you can take $|T'|=O(\log(n))$. Interpret the elements of $S$ as $m$-bit binary strings. Let $U_i^0$ be the set of element …

Let $A=a_0+a_1x+a_2x^2\cdots+a_nx^n$, $B=b_0+b_1x+\cdots+b_mx^m$, and $C=AB=c_0+\cdots+c_{n+m}x^{n+m}$, where arithmetic occurs over $\mathbb{F}_2$. Then your problem is exactly equivalent to recover …

Consider graphs on $n$ nodes. I am trying to find a graph $G$ that contains all $n$-node trees as sub-graphs but contains as few edges as possible. The complete graph $K_n$ suffices, but can we get …

Let $F(N,M)$ be the set of 3-SAT formula with $N$ variables and $M$ clauses. For a given formula $f\in F(N,M)$, we can ask for the set $s_f$ of truth assignments that satisfy $f$. (If $f$ is unsatis …

The comment from "reuns" is the real answer-- the sequence is periodic for all $M$. For prime $M$, we can slightly improve the implied bound as follows. We track the pair: $$\left(j, \sum_{k=1}^{n}(a …

I think the OP is re-inventing Fisher's Exact Test, so perhaps an examination of that may be clarifying. FWIW, questions like this might be better suited to CrossValidated, which is a StackOverflow si …

This may not be exactly what you had in mind, but in the context of displaying information on web pages, there is a need for a canonical labelling of graph isomorphism classes. The proposed web standa …

This is a little numerical experiment, not an answer, but it provides a hypothesis for the shape of a solution. We (computationally) confirmed that matrices with this form have a discrepancy of $(n-2) …

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product $$ p=b_1 b_2 \cdots b_n$$ where each $b_i\in A$. Clearly $n-1$ multiplications suffice to compute $p$; can …

In his book, "The Strange Logic of Random Graphs", Joel Spencer describes the "Dance Marathon" problem: Imagine $n$ couples at a Dance Marathon. Each dance each couple remains standing with independ …

This is a very interesting problem, although I'm not sure if it's a mathematical problem exactly (as opposed to one of algorithmic modeling). That said, here are some two suggestions. Suggestion #1: …

This is more of a comment, but: Depending on exactly how we define the family of sparse matrices, it may not be possible to recover a unique solution. In the example in the original post, the covari …

A small change to Tony Huynh's proof gives a reasonably efficient algorithm for Q2. Label the nodes as 1 through $k$. Select $2k$ distinct primes, listed as $p_1,...,p_k$ and $q_1,...,q_k$. Let $s_ …

Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle …

This isn't an answer; I'm just sharing plots from a few numerical experiments. Each time we repeat the above process for $N$ steps, we generate a (potentially) different multiset (i.e., a different s …