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)

3
votes
0answers
76 views

Nonattacking configurations of k bishops on an m by n rectangular board

The number of ways to place k bishops in a nonattacking configuration on an n by n square board is a well known result and can for example be found in ...
0
votes
0answers
41 views

Number of faces of polytope projecting to lower dimensional polyhedron

Denote $K=\mathrm{conv}(v_1, \ldots, v_n)\subsetneq\Bbb R^m$ to be convex set spanned by vectors $v_i\in\Bbb R^m$ with $m\leq n$ then what technique could be useful to upper bound minimum number of ...
3
votes
2answers
297 views

How to flip one triangulation on a surface into another

Let $S$ be a compact orientable surface and $p_1,\dots, p_n\in S$ be distinct points. We consider all triangulations on $S$ with vertices $p_1,\dots, p_n$. Is there an algorithm which takes two ...
2
votes
0answers
96 views

Volume of bounded regions in hyperplane arrangements

I am given a hyperplane arrangement $\mathcal{H}_0$ in $\mathbb{R}^n$ and a function $\phi \colon \mathbb{R}^n \to \mathbb{Q}.$ I choose any enumeration on the set of primitive vectors (i.e. vectors ...
1
vote
0answers
81 views

Multiple Bipartite graphs and matchings

I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...
10
votes
1answer
270 views

Soft question: mathematics about truchet tiles

It seems that this is the first question on Truchet tiles on MO. Shown above is a picture of a random tile, which you can see the resulting configuration is much like many membranes of cells. I ...
1
vote
0answers
34 views

Rook Polynomials of Skew-Ferrers Boards

What are some known method for calculating the rook polynomials of skew Ferrers boards? Currently all I have been able to find is the following paper Bruhat intervals as rooks on skew Ferrers boards ...
0
votes
0answers
64 views

When is edge colored circulant isomorphism polynomial?

Don't understand enough group theory, but two papers appear to give partial results about an open problem. Edge colored graph isomorphism is isomorphism which preserves the edge coloring (the ...
2
votes
1answer
127 views

NP-hardness of finding maximum of minimum element in diagonal of a matrix

For $A = \{a_{ij}\} \in R^{n\times n}$, is finding $$ \max_{\sigma \in S_n}\min_{1 \le i \le n} a_{i,\ \sigma_i} $$ NP-hard?
1
vote
0answers
95 views

Determining strong base-orderability of a matroid

A matroid is said to be strongly base-orderable when for any two bases $B_1,B_2$ there exists a bijection $f:B_1 \mapsto B_2$ such that for any $X\subseteq B_1$ set $B_1 - X+ f(X)$ is also a base. ...
2
votes
1answer
193 views

Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets: Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...
5
votes
1answer
198 views

Is there a standard name for this poset

I've run into the following poset and I would expect it has a standard name. Let $n\geq k\geq 0$. Then $P_{n,k}$ consists of all $k$-element subsets of $\{1,\ldots,n\}$ ordered by $X\leq Y$ if ...
1
vote
2answers
177 views

Expected matching in a bipartite graph

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
5
votes
1answer
294 views

Common sizes of intersections

I'm trying to come up with the largest family of sets that obeys the following properties: Consider $X = \{1,\dots,n\}$ and take $\mathcal{F} \subset 2^X$ such that for any three subsets $A,B,C \in ...
2
votes
0answers
107 views

Number of degree $k$ functions [closed]

Given a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, there is a real multivariate multilinear polynomial that is associated with in through interpolation. Example: ...
0
votes
2answers
175 views

A specific polynomial triplet question

Notation $P_k[n]=\{$multilinear polynomials in $\Bbb R[x_1,x_2,\dots,x_{n-1},x_n]$ of total degree exactly $k\}$. $k=1$ is just linear polynomials. QUESTION Is there a triplet $(p,f,g)\in ...
7
votes
1answer
97 views

Covering a set with images of a transversal

Let $G$ be a permutation group on a finite set $\Omega$ with orbits $\Omega_1,\ldots,\Omega_k$. By a transversal we mean a set $\lbrace\omega_1,\ldots,\omega_k\rbrace$ with $\omega_j\in\Omega_j$ for ...
1
vote
0answers
63 views

Rook Polynomial of Quasi-Ferrers Board?

One can compute the rook polynomial of the following board: by transforming it to the following equivalent board, which is a Ferrers board, and then using the formula given here: How to compute ...
5
votes
6answers
579 views

Binomial coefficient identity

It seems to be nontrivial (to me) to show that the following identity holds: $$ \binom {m+n}{n} \sum_{k=0}^m \binom {m}{k} \frac {n(-1)^k}{n+k} = 1. $$ This quantity is related to the volume of the ...
1
vote
0answers
42 views

Embedding a collection of finite subsets efficiently

Are there any general non-trivial methods for solving the following problem? Suppose one has a collection of subsets $\mathcal{C} \subseteq \mathcal{P}\mathcal{P}\{1,\dots,n\}$. They may be viewed ...
2
votes
1answer
93 views

Minimality condition in a certain class of hypergraphs

A hypergraph is a pair $H=(V,E)$ such that $V$ is a (possibly infinite) set and $E\subseteq \mathcal{P}(V)$. $C\subseteq E$ is said to be a cover if $\bigcup C = V$ and $C$is minimal if $C'\subseteq ...
1
vote
0answers
142 views

covering high dimensional hypercube by balls

suppose we are given the $d$-dimensional hypercube $H^d$ defined as $$ H^d:=\left\{\sum_{i=1}^d\epsilon_ie_i:\ \epsilon_i\in \{0,1\}\mbox{ for }i=1,\dots , d\right\} $$ and $(e_i)_{i=1}^d$ the ...
2
votes
1answer
109 views

Totally aperiodic sequence

Let $A$ be a finite set. Let $A^k$ be the set of words in the alphabet $A$ of length $k$ and $A^*$ be the set of infinite words. I was looking for an element $a = \lbrace a_n \rbrace_{n \in ...
2
votes
1answer
165 views

Minimum number of edges to remove to have low degree

I have the following problem (k fixed integer): Input: Graph G. Output: Minimum number of edges to remove to G to obtain a graph such that every node has degree at most k. Do you know the complexity ...
12
votes
1answer
291 views

Plane partitions not containing (1,1,1)

A plane partition is a subset of $\mathbb Z_{\geqslant0}^3$ s.t. if it contains $(i+1,j,k)$ or $(i,j+1,k)$ or $(i,j,k+1)$ it also contains $(i,j,k)$. What is the generating function $R(q)$ of ...
0
votes
1answer
32 views

Minimal covers of hypergraphs

Suppose that $H=(V,E)$ is a hypergraph, so $V\neq \emptyset$ is a set and $E$ is a collection of subsets of $V$. A subset $C\subseteq E$ is said to be a cover if any $v\in V$ is contained in some ...
11
votes
0answers
306 views

How large must $A$ be if $\{1, \ldots, N\} \subseteq A-A$?

Given a positive integer $N$, what is the size of the smallest set of integers $A$ such that, for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$ such that $x - y = k$? (An ...
6
votes
0answers
315 views

Large sets not containing arithmetic progressions of length 3 in intervals

Given a large enough natural number $N$, let $\Delta_N=\{A \subseteq [N, 2N]: A$ contains no arithmetic progressions of length $3 \},$ where for natural numbers $N<M$ we have $[N, M]=\{N, N+1, ..., ...
1
vote
0answers
118 views

Young symmetrizers question

Let $\lambda$ be a partition of $n$, and let $T$ be the standard tableau associated to $\lambda$ (write the Young diagram of $\lambda$ down and fill in the boxes with $1$ through $n$ left to right, ...
3
votes
1answer
165 views

Reference for puzzle on dividing piles and scoring products

There is a pile of $n$ items. Every time you divide a pile into two piles, you get a score being the product of the number of items in the two piles. Show that the sum of your scores at the end is ...
5
votes
0answers
153 views

Sets of spreads in graphs

Let $G$ be a graph. A $k$-spread is a set of cliques of order $k$ which partition the vertex set (so $k|n$, where $n$ is the number of vertices). A partial $k$-resolution of $G$ is a set of pairwise ...
5
votes
1answer
122 views

Strongly minimal covers

Let $H=(V,E)$ be a hypergraph, that is $V$ is a set and $E\subseteq \mathcal{P}(V)$. We say that $C\subseteq E$ is a cover of $H$ if $\bigcup C = V$. A cover $M\subseteq E$ is said to be strongly ...
5
votes
1answer
92 views

Number of regions of a hyperplane arrangement avoiding a generic hyperplane

Let $\mathcal{A}$ be an essential arrangement of hyperplanes in $\mathbb{R}^n$. Zaslavsky's theorem says that the number of regions of $\mathcal{A}$ is given by ...
1
vote
0answers
64 views

Hamming graph and independent sets

I'm defining the Hamming graph $H(d,q)$ in the usual way, so we have a set $S$ of $q$ elements, the hamming graph $H(d,q)$ has vertex set $S^{d}$ (the set of all ordered $d$-tuples of elements of $S$) ...
2
votes
0answers
45 views

Optimal tiling for a collection of partitions

I'm interested in a possible generalization of Tiling relation on the set of partitions (the question has only been partially answered). Let $x$ be an infinite set and let $\text{Part}(x)$ be the ...
3
votes
1answer
218 views

Is this property of the Bell's number evident?

Let $B(n)$ denote the Bell's number which is the number of the equivalence relation which can be defined on a set of cardinality $n$. While I was trying to solve a problem, I reached another result; ...
1
vote
0answers
147 views

Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$. I know one way to prove the threshold of a perfect matching is ...
6
votes
3answers
432 views

Number of perfect matchings of the Dodecahedron

This question seems just to be an elementary enumeration problem, but I believe something deeper might be involved: How many perfect matchings does a dodecahedron graph have? Here the ...
4
votes
1answer
143 views

Structure of the stabilizer of a vertex-neighborhood of a vertex-transitive graph

Given a simple, undirected graph and a vertex $v$ of the graph, let $L_v$ denote the set of automorphisms of the graph that fixes the vertex $v$ and each of its neighbors. When the graph is ...
5
votes
2answers
222 views

covering designs of the form $(v,k,2)$

A covering design $(v,k,t)$ is a family of subsets of $[v]$ each having $k$ elements such that given any subset of $[v]$ of $t$ elements it is a subset of one of the sets of the family. A problem is ...
1
vote
1answer
97 views

asymptotic for restricted partitions

Let $m$ and $n$ be two positive integers and denote by $P(n,m)$ the number of partitions of $n$ into $m$ non-negative integers. Is there an asymptotic formula for $P(n,m)$ ?? Any reference is ...
5
votes
0answers
261 views

Transforming a binary matrix into triangular form using permutation matrices

I am interested in the complexity of the following problem: Given an $m\times n$ binary matrix $M$, can we permute its rows/columns to obtain a triangular matrix? I am also interested in ...
0
votes
0answers
61 views

Covering a set in a hypergraph

I'm interested in counting the following. Consider a set $\{v_1,\dots,v_m\}$ of $m$ vertices in the complete $k$-uniform hypergraph on $n$ vertices where $m < k$. I want to know the number of ...
5
votes
1answer
152 views

Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem: $Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...
1
vote
0answers
119 views

Distinct determinants of circulants

If $M$ is a circulant integer matrix of size $n\times n$ whose entries are randomly chosen from $\{0,1\}$ value, how many different determinants does $M$ possibly take value in? For $n=1,2,3,4$, I ...
1
vote
0answers
132 views

Distinct Numbers

Let $x_{ij}\in\{0,1\}$ for ${i=1}$ to ${m}$ and for ${j=1}$ to $n$. How many different values does $$\prod_{i=1}^m\sum_{j=1}^nx_{ij}$$ cover? Is there an $a_{ijk}\in\Bbb R$ (there is a $a_{ijk}\neq0$ ...
3
votes
1answer
147 views

Stable Household Formation

I want to model the problem of household formation by a finite number of individuals, each of whom has preferences over sets of housemates. A collection of households is unstable if there is a set ...
9
votes
3answers
395 views

Cubic-exponential enumerative combinatorics

There are many quantities in enumerative combinatorics that grow roughly exponentially, like the Fibonacci numbers, the Catalan numbers, and the factorials; indeed, most of the functions that arise in ...
2
votes
1answer
185 views

Trying to prove a congruence for Stirling numbers of the second kind

This a repost of a question I asked at Stack Exchange, but I got no answer so far, so I am trying here, even though it may not suit the "research level" requirement. Proposition: When $n$ and $m$ are ...
11
votes
0answers
284 views

Evaluating products of cyclotomic polynomials at roots of unity

Are there general non-trivial conditions on $p(\cdot)$ and $n$, where $p(\cdot)$ is a product of cyclotomic polynomials and $n$ is a positive integer, such that all the coefficients of $p(\cdot)$ are ...