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,516
questions
5
votes
0
answers
229
views
Nonrepetitive nonhomogenous partition regularity
Is it true that for every $k$ for every $k$-coloring of the natural numbers there are naturals $a_1,\dots,a_{2l}$ for some $l\ge 2$ such that $a_1+a_3=2a_2+2$, $a_2+a_4=2a_3+2$, ..., $a_{2l-2}+a_{2l}=...
5
votes
1
answer
334
views
Number of $k$-tuples of elements generating a cyclic group
Let $k$, $m$ be natural numbers, and $C_m:=\mathbb{Z}/ m \mathbb{Z}$ be the cyclic group of order $m$.
Let $N_{k, \, m}$ be the cardinality of the following set: $$\{(a_1, \ldots, a_k) \in (C_m)^k \; ...
5
votes
0
answers
78
views
Recovering a binary function on a lattice by studying its sum along closed walks
I recently posted this question on MSE. While it attracted interest, no answers were submitted, so I thought to try and post it here.
I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While ...
2
votes
0
answers
54
views
Distance distribution for Cayley graphs of the fintie Heisenberg groups H3(Z/nZ) approaches Gaussian for large "n"?
I wonder several questions about Cayley graphs of finite Heisenberg groups H3(Z/nZ).
Question 1: do we know the diameter dependence on "n", at least for the standard choice of generators ? ...
20
votes
1
answer
942
views
Proof of CFSG assuming every simple group is two-generated
It is well-known that one of the corollaries of the classification of finite simple groups (CFSG) is that every finite simple group can be generated by two elements. In a comment on an answer to an ...
3
votes
1
answer
113
views
The pseudo-randomness/jumbledness of $G(n, p)$
In his original paper on pseudo-randomness, Thomason defines a graph to be $(p, \alpha)$-jumbled if, for every set of vertices $U$, $|e(U) - p\binom{|U|}{2}| \leqslant \alpha |U|$. The paper states ...
3
votes
1
answer
367
views
Generalized harmonic numbers and Riemann zeta function
The $n$-th harmonic number is defined as
$$
H_{n}=\sum\limits_{k=1}^{n}\frac{1}{k},
$$
and the generalized harmonic numbers are defined by
$$
H_{n}^{(m)}=\sum\limits_{k=1}^{n}\frac{1}{k^m}.
$$
It is ...
1
vote
0
answers
123
views
Random walk on N-Rubik cube group is going like sqrt(number of moves) or linear (number of moves) or? "commutative" vs. "free"(like) group pattern?
Consider higher (NxNxN) Rubik's cube group, with specific set of generators described below.
What is important - that there are huge COMMUTING subsets of generators.
Question: Consider a random walk ...
1
vote
0
answers
66
views
Ordered combinatorial classes and partitions
Let $\mathcal{C}$ be a combinatorial class and let $\leq$ be a partial order on $\mathcal{C}$. We say that $(\mathcal{C},\leq)$ is an ordered combinatorial class if for all $x,y\in\mathcal{C}$, $$x&...
3
votes
1
answer
205
views
Factorization of Littlewood-Richardson Coefficients
For partitions $\mu \subset \lambda$, let $\kappa \subseteq \mu$ be a partition such that the shape $\lambda/\kappa$ contains at least two non-empty components $\lambda_i, i=1,2$, and similarly let $\...
3
votes
1
answer
285
views
Smallest number of subsets whose squares cover the whole square
Let $2 \leq k \leq n$ be integers, let $[n] := \{1,2,\ldots,n\}$, and for a subset $A \subseteq [n]$ let $A^2 := A \times A$ be the Cartesian product of $A$ with itself and let $|A|$ denote the ...
1
vote
0
answers
54
views
Possible variant of Lovász: Graphs without 3 vertex-disjoint cycles
Is there a classification, or perhaps some exhaustive description, of graphs without 3 vertex-disjoint cycles,
and/or do you maybe know about some reference for such?
The case of graphs without 2 ...
4
votes
0
answers
103
views
Can we extend "every finite lattice is a sublattice of partitions of a finite set" to linear and/or finitary lattices?
Pudlák and Tůma https://link.springer.com/article/10.1007/BF02482893 proved that every finite lattice can be
embedded as a sublattice of the partition lattice of a finite set.
Can this be generalized ...
0
votes
1
answer
65
views
Number of bi-directional (or symmetric edges) [closed]
I am trying to figure out the least number of directed edges that would be bi-directional after constructing a graph with $2k-1$ nodes that are each $k$ in-degree. For example, $2(2)-1=3$ nodes that ...
1
vote
0
answers
54
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
30
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
266
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
636
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
39
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
75
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
394
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
233
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
621
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
161
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
808
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
85
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
122
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
182
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
233
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
164
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
706
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
120
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
136
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 ...