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
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}=...
domotorp's user avatar
  • 18.3k
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 \; ...
Francesco Polizzi's user avatar
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 ...
GSofer's user avatar
  • 191
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 ? ...
Alexander Chervov's user avatar
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 ...
Carl-Fredrik Nyberg Brodda's user avatar
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 ...
Anon's user avatar
  • 41
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 ...
Notamathematician's user avatar
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 ...
Alexander Chervov's user avatar
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&...
smoneh's user avatar
  • 11
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 $\...
Ryan Mickler's user avatar
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 ...
Nathaniel Johnston's user avatar
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 ...
freishahiri's user avatar
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 ...
Dale's user avatar
  • 431
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 ...
James's user avatar
  • 1
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 ...
Tom Copeland's user avatar
  • 9,937
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 ...
Qixian Zhao's user avatar
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}\...
T. Amdeberhan's user avatar
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 ...
Jeja's user avatar
  • 21
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
vidyarthi's user avatar
  • 2,007
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$ ...
domotorp's user avatar
  • 18.3k
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 ...
Denis Ivanov's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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,...
Notamathematician's user avatar
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?
5th decile's user avatar
  • 1,461
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)&...
Tom Copeland's user avatar
  • 9,937
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 ...
Math_Newbie's user avatar
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) ...
Yuting Li's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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(...
Gjergji Zaimi's user avatar
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 ...
Masood's user avatar
  • 169
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 ...
Notamathematician's user avatar
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 ...
Cardstdani's user avatar
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 ...
domotorp's user avatar
  • 18.3k
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 ...
fosco's user avatar
  • 13k
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 ...
domotorp's user avatar
  • 18.3k
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 $...
SetFamilyStudent's user avatar
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 ...
user369335's user avatar
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$ ...
SetFamilyStudent's user avatar
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 ...
Notamathematician's user avatar
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^{...
Hao Yu's user avatar
  • 185
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 ...
thomasfreund's user avatar
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 ...
guipivoto's user avatar
  • 101
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 ...
Matt Zaremsky's user avatar
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 ...
user139952's user avatar
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 ...
T. Amdeberhan's user avatar
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 ...
Nandakumar R's user avatar
  • 5,473
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 ...
Groups's user avatar
  • 369
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, ...
Notamathematician's user avatar
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 ...
Zach Hunter's user avatar
  • 3,393