Tagged Questions
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
0
votes
0answers
57 views
An extrasensory perception strategy :-)
I asked this question at MSE some months ago
but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...
4
votes
2answers
82 views
combinatorial and linear duality
Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual ...
2
votes
2answers
84 views
Is the domination number of a combinatorial design determined by the design parameters?
Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$.
Is $\gamma(L(D))$ determined only by ...
6
votes
2answers
313 views
A combinatorial problem - counting the solutions
Consider a square. There are 16 ways to paint its sides with two colors.
For convenience, we will represent one color with a blank side, and the other - with a line drawn from the squares' center to ...
4
votes
0answers
44 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 ...
1
vote
0answers
35 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
94 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
61 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
84 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
208 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?
...
15
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 ...
-2
votes
0answers
25 views
A combinatorial identity [migrated]
Can anyone prove the following identity for me?
$\sum_{i=0}^k
\begin{pmatrix}
n\\
i
\end{pmatrix}
\begin{pmatrix}
-n\\
k-i
\end{pmatrix}=0$ for any positive integers $n,k$.
I'm pretty sure this is ...
0
votes
0answers
89 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
173 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
59 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
385 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
456 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 ...
0
votes
0answers
28 views
Summing the product of combinations of matrix elements [migrated]
I have a situation where I have an $NxN$ matrix $A$ where each element $a_{i,j}\in\mathbb{R}_{\leq 0}$. I would like to consider the set of all collections of elements such that each collection of $N$ ...
3
votes
3answers
299 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
264 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
234 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
108 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
154 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
136 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
134 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
121 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
113 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
182 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:
...
4
votes
0answers
81 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
309 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 ...
-1
votes
0answers
70 views
what is the Erdos Discrepancy Problem connection(s) to (T)CS? [migrated]
recently there are some new results on computer-based empirical/experimental study of the Erdos Discrepancy Problem (via SAT solvers, cited below). this problem has been cited & studied by several ...
7
votes
1answer
384 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
142 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 ...
2
votes
1answer
299 views
Big constant degree tree as an induced subgraph
First, a preliminary question:
Suppose $G$ is a graph with bounded tree-width. If $G$ has a big binary tree minor, prove that $G$ has an
induced subgraph which is a subdivision of a large ...
5
votes
1answer
249 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$. ...
7
votes
1answer
324 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
191 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
+50
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
182 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
185 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
54 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
42 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 ...
5
votes
0answers
72 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 ...
4
votes
1answer
309 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
158 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
74 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
129 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 ...
2
votes
0answers
66 views
+100
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
45 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 ...
6
votes
3answers
282 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 \}$, ...
