# 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.

10,550
questions

1
vote

0
answers

55
views

### Factorization of the symmetric function identity $E(t)=1/H(t)$ with the refined Euler characteristic polynomials of associahedra / Lagrange inversion

I've come across two matrix identities, flagged with daggers below, relating the two sets of elementary and complete homogeneous symmetric polynomials/functions via the two sets of refined Lah and ...

0
votes

0
answers

31
views

### When is an affine left cell finite?

Consider an affine Weyl group $\hat W$ of a simple Lie type. Let $w \in \hat W$ and let $C^L(w)$ denote the left cell in $\hat W$ containing $w$.
Is there a good criterion to test whether $C^L(w)$ has ...

11
votes

0
answers

267
views

### Color your partitions by parity

Let $a_c(n)$ be the number of ways to partition a positive integer $n$ where each even part comes in $c$ colors. Then, we can supply the generating function
$$\sum_{n\geq0}a_c(n)q^n=\prod_{k\geq1}\...

2
votes

0
answers

83
views

### Computationally decomposing a complete geometric graph into forests of stars

I'm working on the following problem:
I would like to see if it possible to decompose a complete geometric graph on $8$ vertices into $5$ planar star-forests. As doing this by hand was hopeless, I ...

0
votes

0
answers

48
views

### Clique sizes of generalized Kneser graphs

Are there known bounds for clique size in generalized Kneser graphs $KG(n,k,t)=K(n,k,t-1)$, the graph formed by distinct $k$ subsets of $n$ set so that two subsets with at most $t$ elements in common ...

0
votes

0
answers

55
views

### Cycles in Kneser graphs with three vertices forming triangles

Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form ...

9
votes

2
answers

638
views

### Does every big polyomino contain a big arithmetic progression?

Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP.
Is it true that for every $k$ ...

36
votes

6
answers

3k
views

### Number of real roots of 0,1 polynomial

$0,1$ polynomial has coefficients from $\{0,1\}$.
I investigate the number of roots in such polynomials.
We are talking about real roots, and multiples are counted only once.
It was found numerically ...

0
votes

0
answers

40
views

### Determining homomorphism using automorphism group of two graphs

I wish to know the connection between the automorphism group of two graphs and homomorphism between them, if any.
Like all Kneser graphs $K(n,k)$ have the same automorphism group $S_n$. But, given ...

1
vote

1
answer

85
views

### $R$-recursion for the A307389

Let $a(n)$ be A307389 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A(x)=\exp\left(\frac{\exp(2x)-2\exp(x)+2x+1}{2}\right)
$$
The sequence begins with
$$
1,...

4
votes

0
answers

77
views

### Software reference for combinatorial design

If one were to require quick and easy access to sizeable latin squares, room squares, Steiner systems, designs, balanced block designs... where to look, what software to use?

1
vote

0
answers

37
views

### Matrix transform of the bivariate Narayana polynomials into the arithmetic and geometric means of the two indeterminates

The matrix identity presented below is a specialization of the more general result displayed in the MSE-Q "Lah and associahedra partition polynomials and symmetric functions (reference request)&...

7
votes

2
answers

405
views

### Upper bound on VC-dimension of partitioned class

Fix $n,k\in \mathbb{N}_+$.
Let $\mathcal{H}$ be a set of functions from $\mathbb{R}^n$ to $\mathbb{R}$ with finite VC-dimension $d\in \mathbb{N}$. Let $\mathcal{H}_k$ denote the set of maps of the ...

1
vote

0
answers

116
views

### Relationship between the symmetric group representation (Specht module) of a Young diagram and the Young diagram obtained by deleting one row

Suppose $\lambda$ is a Young diagram, and $\lambda'$ is obtained by deleting one particular row of $\lambda$. Is there any relationship between the symmetric group representation (Specht module) ...

1
vote

1
answer

235
views

### Choosing sets with a few properties from a given set of elements

Fix $n$ and $k$ with $n \geq 2k+1$. Let $X$ be an $n$ element set. Let $\binom{X}{k}$ denote the collection of $k$-element subsets of $X$. Suppose that $\mathcal{Y} \subseteq \binom{X}{k}$ is a family ...

14
votes

1
answer

626
views

### Is this generalized version of plethysm Schur positive?

Question: Suppose that $f(x_1, x_2, \dots x_n)$ is a polynomial with nonnegative integer coefficients. For each permutation $\sigma\in S_n$, let $f_{\sigma}$ denote $f(x_{\sigma(1)}, \dots, x_{\sigma(...

3
votes

1
answer

162
views

### Subset of the vertices in a tournament

Suppose we have a directed complete graph. Can we always find a subset $S\neq \emptyset$ of the vertices such that for every vertex $v$, $v$ has incoming edge from at least $\dfrac{|S|}{2}$ of the ...

1
vote

0
answers

71
views

### Slightly modified program for the A345253 such that specific partial sums equal A066258

Let $F(n)$ be A000045 i.e. Fibonacci numbers. Here
$$
F(n) = F(n-1) + F(n-2), \\
F(0) = 0, F(1) = 1
$$
Let $a(n)$ be A345253 i.e. maximal Fibonacci tree: arrangement of the positive integers as ...

4
votes

0
answers

834
views

### Number of arrangements that contain at least 1 path from top to bottom of 2D matrix

I have a $n\times n$ matrix of objects. $n'$ objects are black, and the rest $n^2-n'$ are white.
With that information, I can easily calculate the total number of black element arrangements that exist ...

0
votes

0
answers

86
views

### Turán number of even cycles with diagonal

Let $C_{2k}'$ denote the graph that consists of the cycle on $2k$ vertices and one more edge, a chord connecting two opposite, i.e., distance $k$ vertices of the cycle.
What is known about the Turán ...

13
votes

1
answer

612
views

### The category theoretic origin of arithmetic product

$\newcommand\Bij{\mathrm{Bij}}\newcommand\Set{\mathrm{Set}}\newcommand\Species{\mathrm{Species}}$The paper "On the arithmetic product of combinatorial species" by Maia and Méndez introduces ...

6
votes

0
answers

123
views

### Do vertex-maximal paths in 4-connected graphs intersect?

Call a path in a (possibly infinite) graph vmax (for vertex-maximal) if there is no path that covers a containmentwise larger subset of vertices.
For example, in any spider graph the union of any two ...

2
votes

0
answers

78
views

### A variant of the social golfer problem and the kirkman schoolgirl problem

I came across the following simple question that seems to be open:
Let $U$ be a set of $n$ elements.
Let $P_1$ be a partition of $U$ into $k\le n$ "blocks" (i.e. disjoint subsets) and let $...

2
votes

0
answers

248
views

### Two questions about three circulant matrices

Consider the following matrix equation in $n \times n$ circulant $\pm 1$ matrices $A$, $B$, $C$
$$2AA^T+BB^T+CC^T=(4n+4)I-4J$$
where $I$ is the $n \times n$ identity matrix and $J$ is the $n×n$ matrix ...

1
vote

0
answers

44
views

### How small must partitions be to ensure overlapping blocks?

Consider the set family $F$ of all $t$-element subsets of $[n]$, for some positive integer $n$.
Let $P_1$ be a partition of $F$ into $k$ blocks.
Let $P_2 \ne P_1$ be another partition of $F$ into $k$ ...

4
votes

1
answer

190
views

### Partition numbers as the specific sums of the A161511

Let $p(n)$ be A000041 i.e. number of partitions of $n$ (the partition numbers).
Let
$$
\ell(n)=\left\lfloor\log_2 n\right\rfloor
$$
Let $a(n)$ be A161511 i.e. number of $1\cdots0$ pairs in the ...

1
vote

2
answers

237
views

### Estimation of a combinatoric formula

Assume $n\ge m$, what is the estimation of
$$\sum_{k_1+\dots +k_m\,=\,n,\\ k_1\ge 1,\,\dots,\,k_m\ge 1} C_n^{k_1,\dots,k_m} \left(\frac{1}{k_1}+\frac{1}{k_2}+\dots +\frac{1}{k_m} \right)$$
where $C_n^{...

1
vote

0
answers

167
views

### Amateur Exploring the 'Honeycomb Sequence': A Novel Mathematical Pattern Derived from Pascal's Triangle [closed]

I am an amateur, and for fun, I was studying a specific number sequence I called the "Honeycomb Sequence," derived from hexagonal patterns in Pascal's Triangle. The sequence involves ...

0
votes

1
answer

110
views

### Lottery - Avoid unecessary subsets from a set when aiming prizes of lower order [closed]

I have a Lottery app and I'm implementing a feature to optimize the number of bets that are necessary to cover a subset of numbers since they can repeat on several bets.
What I have:
Supposing a ...

3
votes

2
answers

200
views

### Descending chain in $\mathbb{Z}$ with certain confining property, but not strongly

Call a sequence $A_1 \supseteq A_2 \supseteq \cdots$ of subsets of $\mathbb{Z}$ confining if for all $i$ we have $A_i \supseteq A_{i+1}+A_{i+1}$. (Let us insist that the $A_i$ are symmetric and ...

7
votes

1
answer

297
views

### Fraction of subsets with one-third sum

Given is a multiset $A$ of positive real numbers that can be partitioned into three subsets of equal sum (call this sum $s$). Is it true that more than $3/4$ of $A$'s subsets necessarily have sum at ...

6
votes

2
answers

708
views

### Recreation with Catalan

Consider the well-known sequence $C_k=\frac1{k+1}\binom{2k}k$ of Catalan numbers. I came across the below identity while working with certain generating functions. I thought it might be of interest to ...

4
votes

0
answers

170
views

### Can a square be partitioned into mutually non-congruent triangles all of same area and perimeter?

It is known that the plane cannot be tiled by pair-wise non-congruent triangles all having same area and same perimeter (https://arxiv.org/abs/1711.04504).
Question: Can a square be partitioned into ...

1
vote

0
answers

121
views

### On a generalisation of the EKR theorem

Let $n > k >t$ be positive integers, and let us assume $2k \leqslant n$. We denote the set of $k$-subsets of $[n]$ by $\mathcal{F}$.
Let $C_1\subseteq \mathcal{F}$ be such that any two elements ...

3
votes

0
answers

69
views

### $R$-recursion for the A249833 (similar to A235129)

Let $a(n)$ be A249833 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A(x) = 1 + \int A(x) + (A(x))^2\log A(x)\,dx
$$
The sequence begins with
$$
1, 1, 2, 7, ...

3
votes

0
answers

137
views

### Smallest dominating set

Given a graph $G$, we say $S$ is a dominating set if $S\cup \{N(x):x\in S\}=V(G)$. Let $d(n,k)$ be the smallest integer $s$ so that every $n$-vertex graph $G$ with minimum degree $k$ has some ...

10
votes

1
answer

414
views

### Where does the definition of ($\infty$-)groupoid cardinality come from?

The cardinality of a finite set $X$ is the number of its elements. Once you know that, you would define the groupoid cardinality of a $\infty$-groupoid $X$ as the quantity
$$\lvert X\rvert := \sum_{[x]...

11
votes

0
answers

480
views

### Are there 100 points that are part of every half-density part of the plane?

Is there a configuration $P$ that consists of 100 points of the plane such that every $X\subset\mathbb R^2$ whose density is half contains an isometric copy of $P$?
I am deliberately being vague ...

7
votes

1
answer

597
views

### do all two manifolds admit a three-colorable triangulation?

A triangulation of a two-manifold $M$ is three-colorable if all vertices of the triangulation can be colored red, green, or blue without any two adjacent vertices having the same color.
My question: ...

1
vote

1
answer

197
views

### Calculating the value of periodic continued fractions with $a_i\in\lbrace 0,1\rbrace$

Question:
How can the value of continued fractions of the form
$$y:=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\begin{align}\ddots& \\ &a_{n-1}+\cfrac{1}{a_n+y}\end{align}}}}}$$
$$...

5
votes

0
answers

113
views

### Do uniquely Hamiltonian graphs have cycles of a sufficiently long length?

Let $C$ be a Hamiltonian cycle of a graph $G$.
Call an edge $e$ of $G$ a chord if $e\not\in C$.
Let each edge of $C$ be weighted $1$ and each chord be weighted $2$.
The weight of a path or cycle of ...

2
votes

0
answers

102
views

### $R$-recursion for the A235129

Let $a(n)$ be A235129 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A'(x) = 1 + A(x)\exp(A(x))
$$
The sequence begins with
$$
1, 1, 3, 12, 64, 424, 3358, ...

0
votes

0
answers

175
views

### Upper bound of number of different rows for a binary matrix

Let $\mathcal{X} \subseteq \mathbb{R}^n$ be a measurable space, Fix $m,q \in \mathbb{N}^*$, (the $m$ $x_i$'s are i.i.d and follow distribution $\mathcal{D}$)
and $X = (x_1, \dots, x_m) \sim \mathcal{D}...

5
votes

2
answers

464
views

### Minimum number of transpositions to make two multiset permutations equal

I think this problem should have a known solution, but I wasn't able to find any reference.
Consider a multiset of size $n \cdot m$: it has $n$ elements, and all element multiplicities equal to $m$.
...

4
votes

0
answers

212
views

### Economic equilibrium and tropical geometry

There is a famous saying in economics: When everyone pursues his or her own interests, there is an invisible hand that brings the market to equilibrium. However, this is not always the case. Here is ...

3
votes

2
answers

590
views

### Computing hypergeometric function at 1

I'm looking to compute
$${}_ 3F_ 2\biggl(\begin{matrix} -m-1/2,\ -m,\ k-m+1/2 \cr
1/2-m,\ k-m+3/2\end{matrix};1\biggr)$$
for $m,k > 0$ are positive integers and $0 < k < m$. I'm wondering if ...

6
votes

1
answer

273
views

### Generating 21-vertex 4-regular plane graphs with 8 faces of degree 3 and 15 faces of degree 4

Is there any way to generate all 4-regular plane graphs with 21 vertices, 8 faces of degree 3, and 15 faces of degree 4? If so, how many of these graphs are there and what are they?

2
votes

0
answers

56
views

### Some version of graph removal lemma

I found the following statement in 'A proof of the stability of extremal graphs,
Simonovits’ stability from Szemerédi’s regularity' by Zoltán Füredi:
Lemma: For any $\alpha>0$ and a graph $F$, ...

4
votes

0
answers

58
views

### Existence of finite 3-dimensional hyperbolic balanced geometry

Together with @TarasBanakh we faced the problem described in the title. Let me start with definitions.
A linear space is a pair $(S,\mathcal L)$ consisting of a set $S$ and a family $\mathcal L$ of ...

0
votes

1
answer

94
views

### How far is the slice rank of a tensor from its CP rank

Assume we work on any infinite field and 3-ordered tensor. Clearly for any tensor $T$, we have $\operatorname{srk}(T)\le \operatorname{rk}(T)$. Here, $\operatorname{srk}(T)$ (resp. $\operatorname{rk}(...