# 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,445
questions

0
votes

0
answers

46
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

612
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$ ...

34
votes

5
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

35
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

83
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

72
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

35
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

376
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

113
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

232
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

609
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

157
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

737
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

84
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

607
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

120
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

77
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

246
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

181
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

229
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

151
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

106
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

197
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

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

7
votes

2
answers

700
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

166
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

116
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

68
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

132
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

401
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

473
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

594
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

194
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

111
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

101
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

403
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

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

4
votes

2
answers

578
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

264
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

45
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

87
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}(...

0
votes

0
answers

121
views

### Naming convention for different type of triangulations

When studying random geometries and related mathematical/physical stuff conflicting naming convention pops up regarding the naming of the different ensemble types of triangulations (in general ...

0
votes

0
answers

142
views

### Generate all non-isomorphic signed graphs

A signed graph is a graph in which each edge has a plus or minus sign. More specifically, a signed graph is a couple $S=(G, s)$, where $G=(V, E)$ is a graph with vertex set $V$ and edge set $E$, and $...

5
votes

2
answers

626
views

### Minimum number of swaps to make multisets elements sums close

This problem was originally posted at math.stackexchange but there is no answer there, even after a (now expiring) bounty.
Choose $4$ multisets of size $n$ with elements $x \in \mathbb{R}$, $0 \le x \...

0
votes

0
answers

200
views

### On characters of the symmetric group: Part 2

This question is related to my earlier MO quest.
For an integer partition $\lambda$, denote $\ell(\lambda)=$ length, $\vert\lambda\vert=$ size and $\lambda=$ conjugate of $\lambda$. Allow to write $\...