Questions tagged [co.combinatorics]
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
8,419
questions
4
votes
2answers
240 views
High degree differences in bipartite graphs
Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us define the quantity:
$$\mathcal{I}_k(G) := \sum_{1\le i,j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v_i)-\...
5
votes
1answer
132 views
Signs in Chevalley systems for reductive groups
Let $G$ be a pinned split reductive group. There exists a Chevalley system:
For each root $b$ in its root system there are parametrisations $x_b: \mathbb{G}_a \rightarrow U_b$ of the corresponding ...
7
votes
1answer
306 views
Independent vectors in the permuting coordinates action of $S_n$ on $\mathbb{R}^n$
Let $V$ be the hyperplane in $\mathbb{R}^n$ with equation $\sum_i x_i=0$. The symmetric group $S_n$ acts on $V$ by $s\cdot (v_1,\ldots,v_n)=(v_{s^{-1}(1)},\ldots,v_{s^{-1}(n)})$. Consider those $v\in ...
3
votes
1answer
171 views
Difference set of difference set
I am a hobby computer scientist and searching for an algorithm to construct a set of n numbers (integers) with certain properties.
Property 1 / Step 1
All pairwise differences of the elements should ...
3
votes
0answers
120 views
Partitions of n into k distinct parts which are multiples of given numbers
Is there anything known about the number of partitions of an integer $n$ into $k$ distinct parts in the following way?
Let $a_1,\dotsc,a_k\geqslant1$ be given integers. In how many ways can we write $...
2
votes
0answers
102 views
Magic squares as sums of permutation matrices
A magic square of size $n$ and sum $k$ is a $n\times n$ matrix with non-negative integer elements, whose rows and columns all sum to $k$. A permutation matrix is a magic square of sum $1$. Every magic ...
1
vote
1answer
38 views
Minimal volume of fundamental domains of lattices
Consider a full rank integer lattice in $\mathbb{R}^n$. Let $v_1$ be the shortest non-zero vector in the lattice, $v_2$ be the shortest one among those not parallel to $v_1$, $v_3$ be the shortest one ...
11
votes
1answer
394 views
“Drinking number” of a graph
Motivation. A while ago I attended a party and I only knew some, but not all, of the attendees. There were 2 kinds of drinks: beer and soda. I noticed that amongst my acquaintances, more than half ...
8
votes
1answer
206 views
Find all Non-isomorphic good drawings of $K_{3,3}$？
Sometimes I look at all non-isomorphic good drawings of graphs on a plane or sphere.
Good drawing means that no edge crosses itself, no two edges cross more than once, and no two edges incident with ...
1
vote
1answer
69 views
Knapsack problem with capacity constraint
The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...
5
votes
0answers
69 views
Permutations in a Bruhat interval with a fixed point
Let $[e,\sigma_0]$ be the Bruhat interval of the permutations $\sigma\leq \sigma_0$ for the (strong) Bruhat order. I am interested in the following set, for fixed $i,j$:
$$[e,\sigma_0]_i^j:=\{ \sigma \...
1
vote
1answer
108 views
Partity of partitions with distinct parts of parts $>1$
This question is motivated by my earlier (unanswered) MO post.
The number of partitions into distinct parts is generated by $\sum_{n\geq0}Q(n)x^n=\prod_{k\geq1}(1+x^k)$. Focusing on parity of ...
0
votes
0answers
44 views
Sufficient criterion for unit distance graphs
There are many necessary criteria for a graph to be a unit distance graph. For example, it must not have $K_4$ as a subgraph etc. Can we find some sufficient criterion for a graph to be a unit ...
2
votes
1answer
276 views
Is the number of words finite, when you don't know how to count?
This question is inspired by this one:
Can you do math without knowing how to count?
Let $M_2$ be the set of words constructed by concatenation of the letters $a_1$ and $a_2$, with :
(*) : for any $x$ ...
15
votes
2answers
631 views
n sets, each is large, the intersection of every three is small, what is the size of the union?
Let $A_1, A_2, \ldots, A_n$ be $n$ sets such that:
(1) for each $i\in [n]$, $\frac{n}{3}\leq |A_i|\leq n$;
(2) for any $1\leq i<j<k\leq n$, $|A_i\cap A_j\cap A_k|\leq a$, where $a$ is a constant ...
2
votes
0answers
42 views
Coloring finite subsets of a fixed size with a single modular function
Let $k$ and $N$ be positive integers so that $k\mid N$. Let $M=(k/N){N\choose k}$. A function $f:[N]^k\rightarrow M$ is a coloring function if $f(s_1) = f(s_2)$ implies that $s_1=s_2$ or $s_1 \cap ...
9
votes
0answers
262 views
Being even or odd in the product expansion $\prod(1+x^k+x^{k+1})$
Consider the generating function of "partitions with distinct parts"
$$\sum_nQ(n)x^n=\prod_k(1+x^k).$$
It's known that
$$\left[\prod_k(1+x^k)\right] \mod 2=\prod_m(1-x^m)=\sum_{j\in\mathbb{Z}...
1
vote
1answer
165 views
What is the inverse Laplace transform of $\frac{(1/s)_{n}}{s} $?
Introduction
So far, I have found (p. 5) the following generating functions of the unsigned Stirling numbers of the first kind:
\begin{equation} \tag{1} \label{1} \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)...
2
votes
0answers
91 views
Number of sets of distinct pairs which doesn't share difference
Inspired by This question by Vidyarthi I tried to find the value of $T(2m)$ where, $T(2m)$ is the number of sets of distinct pairings (so, the sets have $m$ elements) of the numbers $1,2,3....,2m$ ...
2
votes
0answers
83 views
Partitioning a set of consecutive nonnegative integers into distinct pairs
Let us have a set of $k$ consecutive natural numbers $2,3,\ldots, k+1$, $k$ even. In addition, we are given a set of $m=\frac{k}{2}$ 'differences' from one among the $k$ numbers $1,2,\ldots, k$.
My ...
1
vote
1answer
81 views
Knapsack problem with value range constraint
The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...
1
vote
0answers
133 views
Is this graph theory paper in German translated into English?
I recently read such a paper and want to understand the proof idea of this article. However since it is in German and I have not studied German before, I'd like to ask whether this paper has an ...
4
votes
0answers
105 views
Positivity conjecture for Somos sequences
Let $\{s_n\}$ be the Somos-$4$ sequence, which is defined by $$s_{n+4}s_n=\alpha s_{n+3}s_{n+1}+\beta s_n^2.$$ It is known that $s_n$ is a Laurent polynomial: $s_n\in\mathbb{Z}[s_1^{\pm1}, \ldots, s_4^...
5
votes
1answer
219 views
Positioning ice-cream stands on a street
We want to position $n$ ice-cream stands on a street. Assume that the population on the street is modeled by a nonnegative integrable function $f$, and everyone goes to the nearest ice-cream stand. ...
8
votes
2answers
223 views
Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$
Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$.
Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...
7
votes
0answers
105 views
On the number of Reed–Muller codewords with no consecutive ones
$\DeclareMathOperator\RM{RM}\DeclareMathOperator\Eval{Eval}$Consider the polynomial ring $\mathbb{F}_2[x_1,x_2,\dotsc,x_m]$ and let $f\in \mathbb{F}_2[x_1,x_2,\dotsc,x_m]$. Let us now fix a Gray ...
0
votes
0answers
43 views
maximum radius for a $k$-set of vertices in a graph
this is a cross-post from mse here.
Let $G$ be a connected graph and $S$ a subset of its vertices. Given a vertex $v$ of $G$ we define the $S$-eccentricity of $v$ as the largest distance between $v$ ...
1
vote
1answer
47 views
Expectation of the sum of the squares of the cardinal of an inverse function
I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as:
$$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$
where $\oplus$ is the bitwise XOR.
...
1
vote
0answers
63 views
Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph
A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
3
votes
1answer
113 views
A ratio of two probabilities
I am concerned about the monotonicity of the following ratio
$
f(\eta)=\frac{\sum_{x=K}^{N}\left(\begin{array}{c}
N\\
x
\end{array}\right)\left(q_{G}\eta\right)^{x}\left(1-q_{G}\eta\right)^{N-x}}{\...
0
votes
0answers
217 views
Equality of the products involving (prime powers - 1)
Let $q_1,q_2,\dots,q_m$ be a collection of prime powers such that $q_i = p_i^{k_i}$. I have the following questions.
When the products $\prod_{i=1}^m(q_i-1)^{r_i}$ and $\prod_{j=1}^m(q_j-1)^{s_j}$ (...
1
vote
1answer
122 views
Expectation of maximum of all period lengths of functions $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$
This is based on an older question.
For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ and ''starting value'' $...
1
vote
0answers
79 views
When are the 3-colorings of vertex subsets uncorrelated?
Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.
For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct ...
-1
votes
1answer
209 views
Given the index of two permutations, Is there a direct way to compute the index of their composition? [closed]
Suppose you are given two indexed permutations, (7 followed by 4, for instance)
What is the best way to go about finding their composition, given the indices themselves? I'd imagine that the answer ...
9
votes
3answers
413 views
Pairs of vertices with high degree difference
Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us also fix an integer $k> n/2$. What are we able to say about the following quantity:
$$\mathcal{I}_k(G) :=...
2
votes
1answer
242 views
Alternating sum of hook lengths: Part II
This is a follow up on my earlier MO post.
Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$. Let
$$f_n=\sum_{\...
0
votes
0answers
51 views
Multiplication on a group of given cardinal and random permutations
Let $n$ be an integer, that we assume to be large (the order of magnitude for the motivation about the question is about 2^100).
For the purpose of random automatic program certification, I need to be ...
7
votes
1answer
172 views
Constructing permutations avoiding a pattern
See here for some theory.
It is fairly easy to explicitly generate all permutations of $n$ elements that have a pattern (just begin with the pattern and add the rest in all possible positions), but ...
5
votes
2answers
190 views
Expectation of period length of functions $f:\{1,\ldots,n\}\to \{1,\ldots,n\}$
For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ associate a sequence $\text{seq}(f))$ defined recursively by
...
7
votes
2answers
401 views
Chip-firing clocks
Let $G$ be some outdegree-regular directed graph with $n$ vertices and let $H$ be the Laplacian of $G$, so that the rows of $H$ correspond to chip-firing moves. I’m interested in linear functions $f$ ...
2
votes
1answer
177 views
Find a collection of values of polynomial
Given a polynomial $f(x)\in \mathbb C[x]$ where $\deg f(x)=n-1.$ Assume that we need to find a collection of values of this polynomial corresponding to the following set of $x$-values: $\{ e^{ik} \}$ ...
2
votes
0answers
49 views
Tail asymptotics of Durfee square identity
This post is related to the problem Asymptotics of a combinatorial series
According to the Durfee square identity:
$$\sum_{k \ge 0} \frac{q^{k^2}}{(q;q)_k^2} (q;q)_{\infty} = 1,$$
where $(q;q)_k$ is ...
1
vote
0answers
34 views
Problem concerning cutting of 2n*2n square into 2 equal area connected figures using various cuts without self crossings
We have a square 2n*2n, where n belongs to N. The main problem is to find how many different equal area connected figures could be produced by cuttings without self-crossings. The orientability of the ...
11
votes
2answers
531 views
Alternating sum of hook lengths: Part I
Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$.
Is there a closed formula or a generating function for the ...
1
vote
0answers
40 views
Higher order Leibniz rule and ordered multiindex notation
Although I think this is probably known, I am making here a short exposition on the multiindex notations I am using to make this question self-contained. I note that there is at least two different ...
2
votes
1answer
113 views
Directed version of this lemma
On a paper by Shoham Letzter, available Here, there's a lemma that says as follows:
Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
0
votes
1answer
80 views
Number of linear inequalities describing a polyhedron with prescribed number of vertices
If a polytope has $d$ vertices in $k$ dimensions how many linear inequalities is required to describe it?
7
votes
1answer
426 views
Packing equal-size disks in a unit disk
Inspired by the delicious buns and Siu Mai in bamboo steamers I saw tonight in a food show about Cantonese Dim Sum, here is a natural question. It probably has been well studied in the literature, but ...
0
votes
0answers
243 views
Is there a permutation $\tau\in S_n$ with $\tau(1)^{\tau(2)}+\cdots+\tau(n-1)^{\tau(n)}+\tau(n)^{\tau(1)}$ a square?
Let $n>1$ be an integer, and let $S_n$ be the symmetric group of all the permutatins of $\{1,\ldots,n\}$.
I'm curious whether there is a permutation $\tau\in S_n$ such that
$$\tau(1)^{\tau(2)}+\...
2
votes
1answer
69 views
Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$
What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...
