**4**

votes

**1**answer

221 views

### Euler-like identity for partition function

Following is the wonderful Euler's partition identity:
$$\prod_{i=1}^\infty (1 - x^i) = 1 + \sum_{k=1}^\infty (-1)^k \left (x^{(3k^2-k)/2} + x^{(3k^2+k)/2} \right )$$
I'm wondering if there is ...

**3**

votes

**0**answers

120 views

### Combinatorial result needed in machine learning? [closed]

Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do i show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the ...

**7**

votes

**1**answer

223 views

### Chromatic number of graph defined on the set of permutations

For $n\in\mathbb{N}$ let $S_n$ denote the set of permutations on the set $\{1,\ldots,n\}$. Set $$E_n = \big\{\{\pi_1, \pi_2\}: \pi_1,\pi_2\in S_n \land \exists k_1 < k_2 <\ldots <k_r\leq n: ...

**1**

vote

**0**answers

93 views

### First to note the relation between Stasheff polytopes (associahedra) and compositional inversion?

In my answer to MO-Q: Enumerative geometry and nonlinear waves, I outline the relation between the refined face polynomials of the Stasheff polytopes (associahedra) and the partition polynomials for ...

**3**

votes

**0**answers

45 views

### The Class of Strong Resolving Graphs of Hamiltonian Outerplanar Graphs

I'll start with a couple important definitions. I'm not sure how well-known any of them are.
Firstly, if $G$ is a graph, and $u, v \in V(G)$, say that $u$ is maximally distant from $v$, denoted $u\ ...

**7**

votes

**0**answers

195 views

### Theorems proved using combinatorial nullstellensatz that have no other known proof

Alon's (or Alon and Tarsi's?) combinatorial nullstellensatz is a powerful algebraic tool with many applications in combinatorics and number theory. See this, this, this and this mathoverflow question. ...

**4**

votes

**2**answers

144 views

### Can we find 3 disjoint directed Hamiltonian cycles in the cube?

Let $D$ be the digraph on $2^d$ vertices with $d2^d$ edges that we obtain by directing each edge of the $d$-dimensional hypercube in both directions.
Can we partition the edges of $D$ into $d$ ...

**0**

votes

**0**answers

83 views

### When does the normalized graph Laplacian have eigenvalue 1?

Let $G= (V,E)$ be a finite, undirected and unweighted graph with $V = \{v_1,\ldots, v_n\}$. Denote by $d_i$ the degree of $v_i$, i.e. the number of vertices that are adjacent to $v_i$. Let $A$ be the ...

**4**

votes

**1**answer

196 views

### Does the minor graph of graphs on $\mathbb{N}$ have an uncountable independent set?

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. We write $V(G) := V$.
If $S, T$ are disjoint subsets of $V(G)$ we say that ...

**1**

vote

**0**answers

54 views

### Proper edge colorings with no bi-colored 5-paths

Consider you want to properly edge color a graph such that it has no bi-colored cycle. Denote by $\alpha'(G)$ the least number of colors required to color the edges of $G$ in such a way.
It is well ...

**11**

votes

**0**answers

284 views

### Probability of many overlapping zero inner products on a circle

[Question edited and changed a little on June 14 2015]
Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...

**13**

votes

**1**answer

573 views

### A circulant coin weighing problem

We are given $n$ coins, some of which are "real" and weigh $1$ and some of which are "fake" and weigh $0$. We have one "spring scale" which can weigh any subset of the coins. A classic question asks ...

**6**

votes

**1**answer

112 views

### Infinite graphs with “similar” Hom-sets

Let $G,H$ be infinite simple undirected graphs with the property that for any graph $X$ we have $|\text{Hom}(X,G)| = |\text{Hom}(X,H)|$. Does this imply that $G$ is isomorphic to a subgraph of $H$, ...

**4**

votes

**0**answers

83 views

### Sparsifiers for 3-term arithmetic progressions

Let $G$ be a finite abelian group of odd order, let $D\subseteq G$, and $\epsilon \in (0,1)$.
For $S\subseteq G$ define
$$
\Lambda(S) = \frac{1}{|S||G|} \sum_{s\in S}\sum_{g\in G} ...

**7**

votes

**1**answer

167 views

### Iterated sumset inequalities in cancellative semigroups

This question is motivated by the following well-known theorems:
Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le ...

**0**

votes

**1**answer

148 views

### Moment maps and flat degenerations of toric varieties

We have a flat family of projective varieties with a torus $T$ action, over $\mathbb{A}^1$.
How do the moment map images of the fibers change when we pass from the generic fiber to the special fiber ...

**1**

vote

**1**answer

193 views

### Ask the name of a combinatorial theorem

It is a classical theorem. For given integer $n \ge 1$, among ${n\choose{n/2}} = 2^{(1-o(1)n)}$ strings in the cube $\{0, 1\}^n$ with weights $n/2$, i.e., $n/2$ indices are 1, there are at least ...

**9**

votes

**2**answers

352 views

### Sumsets and dilates: does $|A+\lambda A|<|A+A|$ ever hold?

The following problem is somehow hidden in this recently asked question, but I believe that it deserves to be asked explicitly.
Is it true that for any finite set $A$ of real numbers, and any real ...

**9**

votes

**1**answer

229 views

### One identity in Lie algebras

Let $L$ be a (non-restricted) Lie algebra over a field of prime characteristic $p,$ $UL$ be its universal enveloping algebra and $a_1,\dots, a_p \in L$ (the number of elements is equal to the ...

**7**

votes

**1**answer

116 views

### Does the Tutte polynomial of iterated cone graphs detect isomorphism?

Let $T_G(x,y)$ denote the Tutte polynomial of a graph. Of course we may have $T_G(x,y) = T_H(x,y)$ for $G$ and $H$ non-isomorphic graphs.
Now let $c(G)$ denote the cone graph of $G$, i.e., the graph ...

**0**

votes

**0**answers

55 views

### Finding a “special” non singular submatrix

Given a square integer matrix $A \in M_n(Z)$ and two subsets $I, J \subset \{ 1, \ldots, n\}$, we define $A_{I,J}$ as the sub-matrix of $A$ containing the rows (resp. columns) whose index is in $I$ ...

**1**

vote

**1**answer

60 views

### Graph classes which are not perfect but the stability number = clique cover numer?

I have a result for graphs whose stability number=clique cover number, which naturally includes the perfect graphs, but I'm curious about if there are other known and well-definable graph classes ...

**8**

votes

**3**answers

705 views

### Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?

This question arose from an answer to my recent question How many traces are there on Temperley-Lieb, Fuss-Catalan, Iwahori-Hecke, Birman-Wenzl-Murakami-Kauffman, ... algebras?
What I need from that ...

**0**

votes

**0**answers

111 views

### Does the equality of product of integers modulo prime p holds in a given interval?

For any given prime $p$, does there exist $a_1,a_2,\dots,a_k,$ (not necessarily distinct) $b_1,b_2,\dots,b_m$ (not necessarily distinct) and $y_1$, $y_2$ such that
...

**6**

votes

**1**answer

258 views

### Combinatorial formula for the number of different words

I originally posted this question here:
http://math.stackexchange.com/questions/1296199/combinatorial-formula-for-the-number-of-different-words :
I am interested in the asymptotic behaviour of the ...

**11**

votes

**2**answers

304 views

### The most number of points that realize only $k$ distinct distances

For $k \ge 1$, let $f_d(k)$ be the largest possible number of points $p_i$
in $\mathbb{R}^d$ that determine at most $k$ distinct (Euclidean) distances,
$\|p_i-p_j\|$.
Example. For points in the plane ...

**2**

votes

**0**answers

56 views

### Euclidean minimum spanning trees intersecting each unit square

The recent question "Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell" can be restated in terms of "minimum spanning trees intersecting each (closed) lattice square of an ...

**-2**

votes

**1**answer

75 views

### How does deletion-contraction affect chromatic number? Can it increase chromatic number? [closed]

Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these ...

**5**

votes

**1**answer

190 views

### Representing one diagonal of Pascal's triangle using special sums coming from a different diagonal

Let $m, n$ be any fixed natural numbers. Is it true that infinitely many elements of the sequence $\binom{m+k}{m}_{k=1,2,3,...}$ ( as well as of the sequence ...

**12**

votes

**1**answer

333 views

### How long can a cycle of antichains in a finite partial order be?

Suppose that $X$ is a finite partially ordered set. Then a subset $A\subseteq X$ is said to be an antichain if there do not exist elements $a,b\in A$ with $a<b$. Let $\mathcal{A}_{X}$ be the set of ...

**11**

votes

**2**answers

314 views

### Graph $G$ with $\omega(G) = 2$ but $\chi(G) \geq \aleph_0$

Given an infinite cardinal $\kappa$, is there a graph $G$ that has no clique consisting of more than 2 points, but $\chi(G) = \kappa$?

**5**

votes

**3**answers

471 views

### Permutations with all cycles odd length and permutations with all cycles even length

If $n$ is even, then the number of permutations of $n$ in which all cycles have odd length equals the number of permutations of $n$ in which all cycles have even length. This fact is easily proved, ...

**18**

votes

**0**answers

396 views

### Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...

**2**

votes

**0**answers

64 views

### A basic minimization problem over finite fields

Let $p$ be a prime, and suppose we are given $n$ values mod $p$: $a_1,...,a_n\in Z_p$. Is there a fast algorithm for finding $\alpha\in Z_p$ which minimizes the value $\max_i (\alpha\cdot a_i$ mod ...

**1**

vote

**1**answer

72 views

### Coxeter Isometry groups whose center has torsion

I'm looking for examples of Riemannian manifolds M of dimension $\geq 2$ such that the isometry group $Isom(M)$ contains as subgroup a finite Coxeter group $G$ such that $Tor(Z(G))$, the torsion group ...

**13**

votes

**2**answers

569 views

### Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n).
The restriction on the first type of bit string is that they must have the same ...

**11**

votes

**1**answer

229 views

### No limit shape for random Young diagrams under z-measure?

In their paper Random partitions and the Gamma kernel (Advances in Mathematics 194 (2005) 141–202), Borodin and Olshanski state that:
An important difference between the Plancherel measures and ...

**3**

votes

**1**answer

317 views

### Is this version of van der Waerden's Theorem consistent with ZFC?

One way to phrase van der Waerden's Theorem is:
For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...

**10**

votes

**2**answers

531 views

### Does van der Waerden's Theorem hold for $\omega_1$?

One way to phrase van der Waerden's Theorem is:
For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...

**1**

vote

**1**answer

150 views

### Enumerating Lattice points

Let $A \in \mathbb{R}^{d\times d}$ be an invertible matrix. Consider the set
$$P_d := A\mathbb{Z}^d = \{A x| x \in \mathbb{Z}^d \} \subset \mathbb{R}^d$$.
and
$$ Q_d := [-1,1]^d.$$
I am interest in ...

**1**

vote

**0**answers

57 views

### Presentation of the Rybnikov matroid

In this well celebrated work Gregory Rybnikov exhibit an example of two arrangements with the same underlying matroid, but with fundamental groups which are not isomorphic. This is a key ...

**5**

votes

**0**answers

122 views

### Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell

Given an $n \times n$ grid with unit grid cells, and one point from the interior
of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...

**4**

votes

**1**answer

247 views

### Strings with no long runs from proper subalphabets

Let $R_{n,k,b}$ be the number of $b$-ary strings of length $n$ that contain some run of length at least $k$ from some $(b-1)$-ary subalphabet. Let $N_{n,k,b}=b^n-R_{n,k,b}$ be the size of the ...

**6**

votes

**1**answer

94 views

### Sum identities with immanants

For $\chi$ being an irreducible character of the symmetric group $S_n$ and being $M$ a complex $n\times n$-matrix, I would like to show
$$
\sum_{\sigma, \rho \in S_n} \overline{\chi(\sigma)} ...

**5**

votes

**0**answers

60 views

### Uniform generation of Symmetric Plane Partitons

In the conclusion of An Involution Principle-Free Proof of Stanley's Hook-Content Formula Krattenthaler notes that the techniques of the paper might be useful for finding bijective proofs of the ...

**1**

vote

**1**answer

205 views

### A Bernstein-like Combinatorial Sum

Do sums of the "convoluted Bernstein" form
$$
\sum_{j=1}^m {m\choose j} q^j (1-q)^{m-j} {n \choose k} \left(\frac j m\right)^k \left(1- \frac j m\right)^{n-k}
$$
admit closed forms? My attempts to ...

**6**

votes

**0**answers

282 views

### What can I further assume about the speeds of runners of Lonely Runner Conjecture WLOG?

Lonely Runner Conjecture is the following problem, and the conjecture was proven to be true for $k\leq 7$:
Let $V$ be the set of $k$ distinct positive integers with $v_1<v_2<...<v_k$ ...

**5**

votes

**1**answer

340 views

### How many random matrices does it take to generate a matrix algebra?

Let $\mathbb{F}$ be a finite field.
Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra.
Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$
that one needs to take ...

**2**

votes

**0**answers

39 views

### A weaker version of Randell Isotopy Theorem

I am studying a problem in hyperplane arrangement theory related to the homotopy type of the complement manifold of a certain class of hyperplane arrangements.
In a well celebrated paper Richard ...

**23**

votes

**1**answer

1k views

### Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...