**4**

votes

**0**answers

61 views

### Reference for statement that almost every $n$-element partial order has trivial automorphism group

I'm looking for a reference for the statement that almost every partial order on $n$ elements has trivial automorphism group. I've been told that this is a folklore result. Does anyone know of a ...

**2**

votes

**0**answers

44 views

### Any one know the results of tensor decomposition by hypergraph partitioning?

Tucker Decomposition and CANDECOMP/PARAFAC (CP) Decomposition are two widely used tensor decomposition methods.
However, when we model the hypergraph into tensor, what's the connection between the ...

**3**

votes

**1**answer

112 views

### Is the domination number NP for non-bipartite graphs?

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?

**5**

votes

**0**answers

64 views

### Classifying two-faces of four-polytopes

Motivation: This question is related to my study of hyperbolic Coxeter polytopes. In general, if one put some restrictions on the type of their dihedral angles (say, all dihedral angles are equal to ...

**2**

votes

**1**answer

108 views

### Coloring vertices in a cubic lattice graph and counting edges between vertices of identical and vertices of distinct coloration

Take an $A \times B \times C$ cubic lattice graph $G$, and paint $k_1$ vertices with color $c_1$ & $k_2$ vertices with color $c_2$, where $(k_1 + k_2)$ is equal to the total vertex count. Let ...

**3**

votes

**1**answer

219 views

### Flow of an integer

I've stumbled across this family of flow networks, and posted the sequence of maximal flows to OEIS. It doesn't appear at this time. I can't find any reference to it either. Has anyone seen it?
...

**16**

votes

**3**answers

2k views

### Silly me & Van der Waerden conjecture

So I walked into this very innocent-looking combinatorics problem,
and quite soon I ended up with the problem to prove that any doubly stochastic $n \times n$ matrix has a non-zero permanent.
Now ...

**0**

votes

**0**answers

98 views

### excplicit formula of iterates of an interval exchange

Let $f$ be an interval exchange transformation of $[0,1]$. Is there an explicit formula giving $f^k(0)$ in function of $k$?
If not, are there particular cases where this formula is simple? (except ...

**4**

votes

**1**answer

178 views

### Is Van der Waerden's function elementary

Van der Waerden's function was proved to have elementary upper bound on growth rate.
Is the Van der Waerden's function itself elementary in the sense of Kalmar?

**1**

vote

**1**answer

64 views

### $top_0(n) / top(n) \rightarrow\ $?

Combinatorics provides us with many fast growing integer sequences. An exact computation of terms does not have to be crucial. Instead, and in addition to standard questions about the approximate ...

**4**

votes

**1**answer

712 views

### Goin' with the flow with Kummer and Pascal: Combinatorics and geometry underlying the logarithm of the derivative operator

In a MO-Q111165 and associated MSE-Q125343, I present a pair of raising / lowering (creation / annihilation) operators $R_x = log(D)$ and $L_x = -x·D$ with $D=d/dx$ (for a sequence of functions ...

**17**

votes

**5**answers

489 views

### Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?

This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the ...

**3**

votes

**3**answers

321 views

### Estimating a sum involving binomial coefficients [refined]

Having some work done, here is a refined version of my initial question.
For integer $m>0$ and $0\le q\le m$, consider the sum
$$ S(m,q) = \sum_{i=0}^{m-q} \binom{m}{i} \binom{m-i}{q}^2. $$
I ...

**5**

votes

**2**answers

276 views

### Construction of a family of sets satisfying specific properties

Is it possible to construct a family of sets $\{A_{ij}\}_{i,j=1}^\infty$ and $\{B_{ij}\}_{i,j=1}^\infty$ such that:
$(1)$For any positive integer $i\geq1$,$A_{ij}\searrow\emptyset$ and ...

**1**

vote

**1**answer

253 views

### Number of matrices with no repeated columns or rows

If you consider all $m$ by $n$ matrices with entries that are either $0$ or $1$, there are ${2^{n} \choose m}$ with no repeated rows (up to row permutation) and ${2^{m} \choose n}$ with no repeated ...

**1**

vote

**0**answers

122 views

### Monotone mappings between finite partially ordered sets

How many monotone mappings are there between $P(E)$ (set of all subsets of $E$) and $P(F)$ if $\text{card}(E) = n$ and $\text{card}(F) = m$?

**1**

vote

**1**answer

167 views

### Simplifying a sum in terms of divisor function Cauchy products

I'm trying to simplify this combinatorial looking sum:
$$\sum_{ax+by=n}_{(a,x,b,y)\in \mathbb{N^4}}\max{\{a,b\}}$$
In terms of possibly some scaled divisor functions plus a Cauchy product/convolution ...

**3**

votes

**0**answers

148 views

### Littlewood-Richardson rule for Schubert polynomials

What is the current state of the problem of finding a combinatorial rule for multiplying two Schubert polynomials? Is the problem still open?

**6**

votes

**1**answer

149 views

### What is/are the best bound/s on the sum of squares of degrees in a graph?

Let $G$ be a graph with degrees $d_{1},\ldots,d_{n}$. I am interested in upper bounds on
$$
\sum_{i=1}^{n}{d_{i}^{2}}.
$$
An example is de Caen's bound:
$$
\sum_{i=1}^{n}{d_{i}^{2}} \leq ...

**3**

votes

**1**answer

126 views

### Partition All $n$-bit Binaries into $n$ Parts

For what values of $n$, it is possible to partition $\mathbb{Z}_2^n$ into $n$ disjoint parts, say $A_1, ..., A_n$ such that every element in $\mathbb{Z}_2^n$ is at most one-edit away from each part, ...

**3**

votes

**0**answers

125 views

### What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...

**0**

votes

**0**answers

190 views

### Sum over a product of binomial coefficients related to a collision problem

I am working on a certain collision problem. The probability of forming $j$ particles upon collision of $m$ and $n$ particles is given by the following equation:
...

**5**

votes

**0**answers

87 views

### Tensor product of hyperplane arrangements

Let $(A_{1},V_{1})$ and $(A_{2},V_{2})$ be two central hyperplane arrangements, which 0 belongs to their intersections. Let $V=V_{1}\otimes V_{2}$. Define the tensor product arrangement $(A_{1}\otimes ...

**8**

votes

**2**answers

360 views

### Finite field Szemeredi-Trotter theorem with unequal number of points and lines

My question concerns the Szemerédi-Trotter theorem in $\mathbb{F}_q^2$. If we have $m$ points and $n$ lines in $\mathbb{F}_q^2$, then by Cauchy-Schwartz the number of point-line incidences is as most ...

**7**

votes

**1**answer

392 views

### Seeming contradiction about P vs NP between graphclasses.org and at least two papers about clique in even-hole-free graphs

I believe correctness about clique in even-hole-free graphs
of graphclasses.org
and the paper Vertex elimination orderings for hereditary graph classes, Pierre Aboulker, Pierre Charbit, Nicolas ...

**4**

votes

**1**answer

187 views

### Maximum distance between two consecutive points of N random points on a unit length line

I have encountered a seemingly simple question on distances of random points.
Place N points randomly and uniformly on the line segment [0..1].
How to derive the expectation (or the distribution) of ...

**3**

votes

**1**answer

581 views

### Big binary tree as an induced subgraph

I believe this is true:
Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an
induced subgraph which is a subdivision of a large binary tree or the line ...

**5**

votes

**1**answer

258 views

### Number of partitions whose blocks form arithmetic progressions

As is known, the set $\{1,\ldots,n\}$ has $2^n$ many subsets and $B_n$ (the $n$th Bell number) many partitions, where clearly $B_n<2^{2^n}$ and it is actually known that $B_n<n^n$ for large $n$. ...

**9**

votes

**1**answer

478 views

### Real-rootedness, interlacing, root-bounds of a sequence of polynomials

Problem: the number $a(n,k)$ is defined by the following recurrence
\begin{equation}
a(n,k)=(k+1)(k+2)\, a(n-1, k)+\frac{(k+1)(k+2)(k+3)}{k} \,a(n-1, k-1),
\end{equation}
with $a(1,1)=1$ and ...

**4**

votes

**2**answers

200 views

### Is there a theory of oriented subspace arrangements?

The theory of hyperplane arrangements is a rich and intensely studied subject, especially from the perspective of combinatorics; see e.g. this wonderful monograph of Stanley. Oriented hyperplane ...

**19**

votes

**4**answers

1k views

### Number of vectors so that no two subset sums are equal

Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 ...

**9**

votes

**0**answers

259 views

### A $q$-analogue of Foulkes' character related to alternating permutations

My paper "Alternating permutations and symmetric functions" at
http://math.mit.edu/~rstan/papers/altenum.pdf enumerates certain
classes of alternating permutations, such as those whose inverse is
...

**9**

votes

**1**answer

201 views

### Why are the power symmetric functions sums of hook Schur functions only?

One interesting fact in symmetric function theory is that the power symmetric function $p_n$ can be written as an alternating sum of hook Schur functions $s_{\lambda}$:
$$
p_n = \sum_{k+\ell = n} ...

**0**

votes

**2**answers

59 views

### Finding minimal number of expressions (a minimum spanning tree-like problem)

Although the title is similar to this one
Finding minimal or canonical expressions for Boolean truth tables
that topic should be about something else.
Given a vector consisting of "n" slots, the ...

**0**

votes

**0**answers

48 views

### Cycles of Permutation Related to Rectangular Matrix Transposition

let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$
Question:
How can the first element ...

**6**

votes

**1**answer

161 views

### Under which constraints are there only finite numbers of irreducible eta product identities?

For the Dedekind eta function, defined as usual by $\eta(q) = q^{\frac1{24}} \prod\limits_{n=1}^{\infty} (1-q^{n})$, let for brevity $e_k:=\eta(q^k)$.
An eta product identity (or eta identity for ...

**5**

votes

**1**answer

324 views

### Lights out game

I would like to ask about the game Lights Out for a square nxn. In http://mathworld.wolfram.com/LightsOutPuzzle.html there is a list of the number of solutions to the game, and the number of solutions ...

**10**

votes

**2**answers

171 views

### Big Mono-Chromatic Subgraphs of Vertex 2-Colourings

I'm not a graph theorist, but the following quantity came up in my work and I'm curious if it has been studied. Given a connected finite graph $\Gamma = (V,E)$ define: $$ c(\Gamma) = \min_{f : V ...

**0**

votes

**0**answers

77 views

### Sum of powers of multinomial coefficients

I would be interested in evaluation the sum of the following type of sums:
$$\sum_{|\alpha|=m}\binom{m}{\alpha_1,\dots,\alpha_n}^q$$
with $1/2\leq q<1$. More precisely, I would like to estimate ...

**0**

votes

**1**answer

251 views

### Pros and cons of probability model for permutations

I am studying probability model of random permetuation
Let $b(n; k)$ denote the number of permutations of {1,...,n} with precisely k
inversions ($inv(\pi)$). The analytic approach was considered by ...

**3**

votes

**0**answers

88 views

### Generating random weak k-bounded reverse plane partitions

Fix a partition $\lambda$. A weak reverse plane partition of shape $\lambda$ is a filling $0\leq \pi_{ij}$ of $\lambda$ with $\pi_{ij}\leq \pi_{kl}$ whenever $i\leq k$ or $j\leq l$. Note that ...

**0**

votes

**0**answers

48 views

### A particular method of removing edges from strong di-graphs

I have been mulling over a little puzzle I gave myself involving a particular type of iterative removal of edges from a digraph and I'm stuck -- thought I'd consult experts.
Start with an ...

**7**

votes

**3**answers

289 views

### Increasing tower of subsets of ${1, …, k}$

Suppose $k$ is fixed. Consider a set $X$ of subsets of the ground set $\{1, \dots, k \}$, with the following property: there is some ordering of the elements of $X$, as $X = \{ x_1, \dots, x_n \}$, ...

**0**

votes

**0**answers

47 views

### A lower bound on the number of matrices whose image contains all multiples of $p^e$

Let $0\leq e<e^\prime$ be integers. Now suppose $N$ is the number of $n\times n$ matrices over the ring $R:=\mathbb{Z}/p^{e^\prime}\mathbb{Z}$ (where $p$ is prime) such that ...

**0**

votes

**1**answer

86 views

### Permutation with restricted pairwise ordering

There exist work on permutation with restricted positions (say, a permutation $\sigma$ satisfies $\sigma(i) = k$), and I am wondering if there exists a theory on permutation with restricted pairwise ...

**8**

votes

**0**answers

115 views

### Erdös-Fuchs Theorem for multivariate linear forms

Let $A$ be an infinite set of positive integers, and denote by $r(n)$ the number of solutions to the equation $a+a'=n$, with $a,\, a' \in A$.
It is not very difficult to show that if $r(n) > 0$ ...

**6**

votes

**1**answer

160 views

### Almost Hadamard matrices

As well-known, a Hadamard matrix is a square matrix with all coefficients $\pm 1$
and pairwise orthogonal rows or columns. Such matrices exist conjecturally
in every dimension divisible by $4$. Call ...

**7**

votes

**1**answer

303 views

### A combinatorial problem concerned with logic circuits

Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that ...

**4**

votes

**0**answers

176 views

### A closed formula for this arithmetic function

The following function comes up in my research as part of a sufficient condition for capability of $p$-group of class two and prime exponent. Given a nonnegative integer $m$, express $m$ as a ...

**3**

votes

**2**answers

186 views

### Making a graph claw-free by adding as few edges as possible

Independent set is polynomial in claw-free graphs,
so I am wondering if this can approximate independent set.
By adding enough edges to $G$ and gets claw-free $G'$.
IS in $G'$ is IS in $G$, so this ...