**5**

votes

**1**answer

452 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**1**

vote

**2**answers

359 views

### When is a power of an indeterminate in an ideal with 2 generators?

If I have an ideal ${\frak a} \colon= (f(X,S), g(X,S))$ of height $2$ in ${\Bbb C}[X, S]$, is it easy to know what power of $S$ is contained in $\frak a$? For example, what is the minimal number $m$? ...

**4**

votes

**1**answer

436 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**4**

votes

**0**answers

58 views

### Pattern Avoidance in Poset Permutations

I am not sure if it is appropriate to use MathOverflow to publicize a conjecture, but I think this is an interesting question and I have no real ideas of how to solve it.
A permutation on a ...

**8**

votes

**0**answers

140 views

### Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)

The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is ...

**1**

vote

**0**answers

503 views

### Maximal disjoint hyperplanes

Assume a set of $n^{r}$ points $X_{r} = \{ x_{1}, \cdots, x_{n^{r}} \}$ is given occupying a codimension $t^{r}$ subspace in $\mathbb{R}^{n^{r}}$. Let $M_{r}$ be the set of $t^{r}$-tuples of these ...

**-2**

votes

**1**answer

83 views

### Recursion, Common Term, Combinatorics [on hold]

May we find the common term for recursive sequence? if yes that how to find the common term of recursive sequence such: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 ...
in a ...

**2**

votes

**1**answer

175 views

### Expected value (probability) maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like
$$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$
Here $f(k,x)$ is actually a probability coming from a ...

**1**

vote

**0**answers

49 views

### A specific class of $(0,1)$-matrices

Let $T_n$ be the class of $(0,1)$-matrices of order n with no row sum equal to a column sum. Is there any name or research about this kind of matrix?
For any $A\in T_n$, let $S_A$ be the sum of all ...

**1**

vote

**0**answers

117 views

### Probability of correlated residues

Given $N,c\in\Bbb N$, where $c\ll(\log N)^{1/b}$ for any $b>1$ is fixed, what is the probability that given $A_1,A_2,A_3\in\Bbb N$ with ...

**0**

votes

**0**answers

24 views

### probability of reaching a point in a 2d grid in a certain number of steps [on hold]

I have a random walk process in a 2d grid with N steps where N is small. How can I calculate the probability that any given cell was reached in N, N-1, N-2 ... 1 steps. That is, I would like to be ...

**7**

votes

**1**answer

590 views

### Counting subspaces

We are given the finite vector space $V = V(n,p) = \mathbb{F}_p^n$ and two fixed subspaces $W_1, W_2 \subseteq V$ of dimensions $m_1$, $m_2$ respectively. Suppose
that the dimension of $W_1 \cap W_2$ ...

**4**

votes

**0**answers

49 views

### Asymptotics of a Bivariate Generating Function

I have the following generating function,
$$G(x,y)=\sum_{n,k \geq 0}a(n,k)x^ny^k = \frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$
and I am interested in obtaining an asymptotic for the sequence $a(n,k)$ ...

**2**

votes

**0**answers

104 views

### Permutation equivalence classes with kendall-tau distance

I asked this question on Stack Exchange a few days ago with no help. I am not sure if the question seems too trivial or of not enough general interest to get any attention. Anyway, any sort of ...

**1**

vote

**2**answers

129 views

### How do powers affect asymptotics in generating functions?

Let $a_n$ be a sequence of non-negative real numbers, and $A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$ its exponential generating function. Also, suppose $B(x) = \sum_{n=0}^{\infty} b_n ...

**0**

votes

**1**answer

94 views

### Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...

**4**

votes

**1**answer

128 views

### Number of bases of a matroid

I would like to know the minimum number of bases of a matroid of rank $k$ and $n$ elements, knowing that each singleton is independent. At least for small ranks.

**4**

votes

**1**answer

348 views

### Is the face poset a Heyting algebra?

Is the face poset of a simplicial or nice enough cellular complex a Heyting algebra in some natural way?
Edited to add: For the benefit of illustration, here's a few face posets:
the boundary of a ...

**11**

votes

**1**answer

210 views

### Complexity of planar scissor congruence

Two (not necessarily convex) poygons of equal area are scissor-congruent, i.e. both can be cut along a finite number of straight lines or segments into isometric pieces.
What can be said about the ...

**3**

votes

**0**answers

104 views

### How many different sums of parts of a vector

I hope this question isn't too basic for MO. I also asked it on math.se previously. This mathematical puzzle was given to me by a friend a while ago and I can't work out how to solve it. Does anyone ...

**0**

votes

**0**answers

64 views

### Showing that a sequence of random variables with increasing expected value converges to a Poisson random variable

Consider a sequence $\{X_n\}_{n \geq 1}$ of nonnegative, integer-valued random variables. For any random variable $Y$ and $k \geq 1$, let $(Y)_k = Y(Y-1)(Y-2)\dots(Y-k+1)$ be the $k^\mathrm{th}$ ...

**1**

vote

**1**answer

344 views

### Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition

Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...

**14**

votes

**0**answers

222 views

### An algebraic strengthening of the Saturation Conjecture

The Saturation Conjecture (proved by Knutson-Tao) asserts that
$c_{n\mu,n\nu}^{n\lambda}\neq 0\Rightarrow c_{\mu,\nu}^{\lambda} \neq
0$, where $c$ denotes a Littlewood-Richardson coefficient and $n$ ...

**14**

votes

**0**answers

149 views

### Minimal number of intersections in a convex $n$-gon?

For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...

**0**

votes

**0**answers

63 views

### A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...

**2**

votes

**1**answer

118 views

### Is the top interval of a finite distributive lattice an hypercube lattice?

Let $(L,\wedge,\vee)$ be a finite distributive lattice. Let $M$ be the (unique) maximum element. An element $a \in L$ is called maximal if $a \le a' < M$ implies $a = a'$. Let $b = ...

**1**

vote

**0**answers

24 views

### What is the minimum number of filled cells in a partial Latin rectangle with autotopism group $\cong C_2$ and autoparatopism group $\cong S_3$?

Definitions: a partial Latin rectangle is an $r \times s$ matrix containing symbols from $[n] \cup \{\cdot\}$ such that each row and each column contains at most one copy of any symbol in $[n]$. The ...

**1**

vote

**0**answers

170 views

### system with solutions $\{x-a:0\leqslant a\leqslant z-1\}$ [closed]

What must be $F$ there where $0=F(1,x,0)=F(x-0,x,z)=F(x-1,x,z)=F(x-2,x,z)=F(x-3,x,z)=$ $\dots$ $=f(x-z-1,x,z)=0$?
Define $F$ in the domain where a continuous function exists that behaves so for ...

**2**

votes

**0**answers

52 views

### A question on the behavior of intersections of certain block design

Let $[d]$ be a universe and $S_1, \dots, S_m$ be an $(\ell, a)$-design over $[d]$ which means that:
$\forall i \in [m], S_i \subseteq [d], |S_i|=\ell$.
$\forall i \neq j \in [m]$, $|S_i \cap S_j| ...

**2**

votes

**1**answer

190 views

### Existence of functions on finite sets with specific propertise

Let $\Omega$ be an universal set and $|\Omega|=N$, denote $\mathcal{F}$ to be the family of all subsets $\subset \Omega$ with cardinal $n$. We now define a function $f:\mathcal{F}\rightarrow \Omega$, ...

**23**

votes

**5**answers

1k views

### Integers in a triangle, and differences

I read about the following puzzle thirty-five years ago or so, and I still do not know the answer.
One gives an integer $n\ge1$ and asks to place the integers $1,2,\ldots,N=\frac{n(n+1)}{2}$ in a ...

**54**

votes

**9**answers

3k views

### What are some examples of interesting uses of the theory of combinatorial species?

This is a question I've asked myself a couple of times before, but its appearance on MO is somewhat motivated by this thread, and sigfpe's comment to Pete Clark's answer.
I've often heard it claimed ...

**12**

votes

**2**answers

405 views

### Number of nonzero terms in polynomial expansion (lower bounds)

Let $f(x) = a_1x^{z_1} + a_2x^{z_2} + \cdots + a_kx^{z_k}$ be a polynomial with coefficients $(a_1, \ldots, a_k) \in \mathbb{F}_q^*$ and $z_i$ are distinct positive integers. If I need to compute the ...

**0**

votes

**2**answers

334 views

### Worst case difference in rank by column-row swapping

Given a matrix $m\in\{-1,+1\}^{n\times n}$. Consider $m^\sigma$ to be collection of all matrices obtained from $m$ by permuting rows and columns.
Consider $\mathscr{M}[m^\sigma]$ to be collection of ...

**6**

votes

**1**answer

127 views

### Writing the quotient of solutions of linear ODEs as the solution of a nonlinear ODE

Let $A(x)$ and $B(x)$ be solutions to homogeneous linear ODEs with polynomial coefficients, i.e., $A(x)$ satisfies
$$p_KA^{(K)} + p_{K-1}A^{(K-1)} + \cdots + p_1A' + p_0A=0$$
and $B(x)$ satisfies
...

**1**

vote

**0**answers

219 views

### Incidence geometry and matrices

Supposing I have a $0/1$ or $\pm1$ matrix $A$ of size $m\times n$, is there a minimum $d$ (that works for every $m\times n$ $A$) such that there exists $m$ lines $r_1,\dots,r_m$, $n$ lines ...

**8**

votes

**1**answer

581 views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

**1**

vote

**1**answer

300 views

### Analytic Number Theory without Pigeonhole Principle [closed]

I don't know if this is an appropriate question for this website, but I will try my luck.
I am an undergraduate student, and recently I became interested in analytic number theory. When I started ...

**1**

vote

**0**answers

74 views

### Efficiently counting all paths of length n in a graph with vertex visitation contraints [closed]

I have a graph G with two classes of vertices. The first class represents no resource limitation entities and can be visited an unlimited number of times in any path traversal. The second class of ...

**12**

votes

**2**answers

294 views

### Asymptotics of coefficients of implicitely defined generating function

I have two integer sequences $\{a_n\}_{n=0}^\infty$ and $\{b_n\}_{n=0}^\infty$. Explicit formulas for the $a_n$ are known and their asymptotic growth is fully understood. My wish is to also understand ...

**2**

votes

**1**answer

97 views

### Inducing representations from the stabilizer of a partition

For each positive integer $i$, let $A_i$ be a fixed representation of the symmetric group $S_i$. I won't tell you exactly what $A_i$ is, but let's say that I have a very explicit description of its ...

**8**

votes

**2**answers

225 views

### Dividing the edges and diagonals of a polygon among disjoint sub-polygons

Let $P$ be a convex $n$-gon ($n$ is odd and $n \geq 5$).
Determine the smallest $m$ such that all edges and diagonals of $P$ can be covered by the edges
of $m$ convex sub-polygons of $P$ which ...

**5**

votes

**1**answer

142 views

### Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...

**1**

vote

**2**answers

107 views

### Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties:
The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
$T$ has a ...

**3**

votes

**2**answers

930 views

### Polya's theory of counting and commutative algebra

Do you know if there exist algebraic studies of the ring of the power series which emerge when using the theory of Polya for enumeration of sets with certain symmetries? For instance if some ideals ...

**5**

votes

**0**answers

168 views

### Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...

**1**

vote

**0**answers

149 views

### Nimbers and Surreal Numbers [closed]

I have been researching Combinatorial Game Theory. One common theme is the assignment of values to games in order to classify the game as a win for a specific player. One such way is class of surreal ...

**5**

votes

**1**answer

133 views

### Algorithm that generates a n-simplex that cover n-polytope?

Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?

**2**

votes

**1**answer

59 views

### Images of interval edge coloring

I found out the definition of interval edge colorings, concept put by Kamalian in various papers but could not find a graph depicting an example. Where can I find pictures of explicit examples of ...

**3**

votes

**2**answers

85 views

### Are there references for the properties of words formed in finite groups using L-systems? (In particular, the algae L-system.)

Let $G$ be a (finite) group, and $a, b \in G$ be any two elements. Consider the sequence defined by
\begin{eqnarray*}
s_0 &=& a, \\
s_1 &=& b, \text{and} \\
s_{n+2} &=& s_{n+1} ...