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
4 views
The largest size of a boolean subgraph (a hypercube) of a given graph
Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...
4
votes
0answers
50 views
Normal polytopes - counterexample?
An integral polytope $P$ is normal if all lattice points inside the integer dilation $kP$ can be expressed as $p_1+p_2+\dots+p_k$, where $p_i \in P$ are lattice points.
I am looking for an example ...
0
votes
0answers
41 views
Sequence of n numbers and arithmetic means [on hold]
I'm struggling with this exercise:
Prove that sequence of n numbers 1,2, ..., n can be arranged to sequence where arithmetic mean of any two numbers is not between those two numbers.
For example: ...
6
votes
0answers
127 views
Counting categories with at most $n$ morphisms
There are a number of results which count the number of possible algebraic structures on a set of $n$ elements. Notable previous MO questions are for example here and here. The analogous question for ...
1
vote
0answers
120 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
101 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
115 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 ...
7
votes
3answers
406 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
48 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
36 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
97 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
62 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?
...
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 ...
-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
90 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
392 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
461 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
301 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
137 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
136 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
185 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
83 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
313 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
147 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
305 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
326 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
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
310 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
159 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 ...
