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.

Filter by
Sorted by
Tagged with
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 ...