Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

5
votes
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
5answers
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
9answers
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
2answers
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
2answers
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
1answer
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
2answers
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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} ...