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)

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