10
votes
0answers
158 views
Order matters when choosing sets
Warren Moors and Julia Novak in a paper entitled "Order matters when choosing sets" proved that if 1 < w < t < v are integers then
$${{{v}\choose {w}}\choose {t}} > {{{v …
4
votes
3answers
245 views
Do the base 3 digits of $2^n$ avoid the digit 2 infinitely often — what is the status of this problem?
I believe this question is due to Erdős and Graham, and I think it is still open: does the base 3 expansion of $2^n$ avoid the digit 2 for infinitely many $n$?
If we concaten …
2
votes
1answer
262 views
Mathematics of the 24 game
I assume everyone here knows the 24-game -- given 4 numbers, combine them using +,-,x,/ and parentheses to form 24. An obvious generalization is to give $n$ integers ${a_,...,a_n}$ …
10
votes
5answers
248 views
Lower bounds for chromatic number of a graph
I am trying to find a good lower bound for chromatic number of one family of graphs. I'm curious what are the known lower bounds for chromatic number. There are two obvious: $\chi( …
2
votes
1answer
100 views
Examples of Super-polynomial time algorithmic/induction proofs?
In combinatorics, one can sometimes get an algorithmic proof, which loosely has the following form:
-The proof moves through stages
-An invariant is shown to hold by induction fr …
1
vote
3answers
403 views
Families of subsets of $\{1,\dots,n\}$ with regular intersections
Let $2 \leq k \leq n - 2$.
I need to prove that any collection of sub-sets of [n] such that 2 different of them
have exactly k common elements, consists of at most $n$ sub-sets.
T …
7
votes
1answer
120 views
Is there an analogue of the Hive model for Littlewood-Richardson coefficients of types $B$, $C$ and $D$?
If $V_\lambda$, $V_\mu$ and $V_\nu$ are irreducible representations of $GL_n$, the Littlewood-Richardson coefficient $c_{\lambda\mu}^\nu$ denotes the multiplicity of $V_\nu$ in th …
4
votes
1answer
157 views
Subsets of sequences of natural numbers vs. strategies under ZFC
This question is related to a previous question of mine:
http://mathoverflow.net/questions/32966/determinacy-interchanging-the-roles-of-both-players
Given any set A of sequences …
1
vote
0answers
126 views
Combinations of multisets with finite multiplicities
The question may be of little interest to most people here on MathOverflow, but after browsing a pile of books in combinatorics, I had to ask it somewhere:
What are the most effic …
34
votes
7answers
3k views
The “sensitivity” of 2-colorings of the d-dimensional integer lattice
Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).
…
3
votes
1answer
139 views
Complexity of high-order differentiation
Let $g(x) = \exp(f(x))$. Assuming numerical (or symbolic) values of $f(x), f'(x), f''(x), \ldots, f^{(n)}(x)$ are known, is there a way to compute $g'(x), g''(x), \ldots g^{(n)}(x) …
4
votes
1answer
65 views
Degree sequences of multigraphs with bounded multiplicity
I got to thinking about this problem while sifting through the math puzzles for dinner thread. There's a fun puzzle by rgrig which asks the guests to prove that when they came to …
0
votes
2answers
502 views
Explicit formula for Euler zigzag numbers(Up/down numbers)
I have derived an explicit formula for the Euler zigzag numbers, the number of alternating permutations for n elements:
$$A_n = i^{n+1}\sum _{k=1}^{n+1} \sum _{j=0}^k {k\choose{j} …
7
votes
1answer
461 views
Association scheme on injective functions
This problem arises while studying the complexity of algorithms and I am quite unfamiliar with the subject.
Consider the set F of injective functions from {1..N} to {1..M}
we can …
2
votes
1answer
290 views
Looking for a probability distribution
Recently I discussed an experiment with a friend. Assume we start a random experiment. At first there is an array with size 100 000, all set to 0. We calculate at each round a rand …
