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
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 ...
Tom Copeland's user avatar
  • 9,931
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 ...
Qixian Zhao's user avatar
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}\...
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,027
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,027
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$ ...
domotorp's user avatar
  • 18.4k
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
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 ...
vidyarthi's user avatar
  • 2,027
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
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?
5th decile's user avatar
  • 1,451
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,931
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 ...
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
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 ...
vidyarthi's user avatar
  • 2,027
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(...
Gjergji Zaimi's user avatar
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 ...
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
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 ...
Cardstdani's user avatar
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 ...
domotorp's user avatar
  • 18.4k
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
  • 13.2k
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 ...
domotorp's user avatar
  • 18.4k
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
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 ...
Notamathematician's user avatar
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^{...
Hao Yu's user avatar
  • 185
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 ...
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
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 ...
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,483
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 ...
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
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 ...
Zach Hunter's user avatar
  • 3,403
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]...
Matthew Niemiro's user avatar
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 ...
domotorp's user avatar
  • 18.4k
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: ...
A_Physicist.'s user avatar
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}}}}}$$ $$...
Manfred Weis's user avatar
  • 12.6k
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 ...
kabenyuk's user avatar
  • 673
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, ...
Notamathematician's user avatar
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}...
rivana's user avatar
  • 29
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$. ...
Fabius Wiesner's user avatar
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 ...
Surpass2019's user avatar
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 ...
JMK's user avatar
  • 299
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?
Xin Zhang's user avatar
  • 1,130
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$, ...
Isomorphism's user avatar
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 ...
Ihromant's user avatar
  • 471
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}(...
Nick Chen's user avatar
  • 151

1
3 4
5
6 7
211