All Questions
Tagged with combinatorics or co.combinatorics
11,023 questions
2
votes
1
answer
169
views
Is this formula for certain structure constants of quantum Schubert polynomials known?
Quantum Schubert polynomials $\mathfrak{S}_u^q(x)$ indexed by $S_\infty$ are polynomials in the polynomial ring $\mathbb{Z}[x,q]$ in infinitely many variables that form a basis of this ring over $\...
- 2,168
3
votes
2
answers
468
views
How fast does the number of "fixed" points grow compared to the size of the ball in the following group?
I have copied this question from Math.StackExchange, in the hope that some experts here can provide some relevant insight.
Let $M = \oplus_{i\in \mathbb Z} V^{(i)}$ where each $ V^{(i)} \cong \mathbb ...
- 1,819
1
vote
0
answers
63
views
Is there any other norms besides cut norm defined on graphon?
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 349
1
vote
1
answer
194
views
Bounds on lengths of intervals in bounded-degree interval graphs
A graph is said to be an interval graph if its vertices can be associated with (closed) intervals on the real line $\mathbb R$ and there is an edge between two vertices if and only if the ...
- 277
2
votes
1
answer
80
views
Positive-semidefiniteness of Laplacian of signed graph
Consider a signed complete graph $G(E,V)$ with adjacency $A_{ij}\in\{-1,+1\}$. Define the Laplacian matrix as $L:=D-A$ where $D$ is the degree matrix, $D_{ii}=\sum_{j\neq 1}A_{ij}$.
my question.
If $\...
- 12.9k
3
votes
1
answer
238
views
Clique and chromatic number when removing an edge
For any set $X$, let $[X]^2=\big\{\{x,y\}: x\neq y\in X\big\}$. If $G=(V,E)$ is a simple undirected graph and $e\in E$, let $G\setminus e = \big(V\setminus e, E \cap [V\setminus e]^2\big)$.
If $G=(V,E)...
- 3,319
3
votes
1
answer
260
views
Davenport constant $D(S_5)=10$ or $11$?
I am working on computing the Davenport constant $D(G)$
of symmetric groups, which is the minimal number $d$
such that every sequence of $d$
elements, possibly with repetitions, is one-product, i.e. ...
- 12.9k
1
vote
1
answer
141
views
Covering a bounded degree graph with subgraphs of bounded sizes
Let $G$ be a connected graph on $n$ vertices with maximum degree $\Delta \ge 2$. Let $\mathcal G = \{G_1,G_2,\ldots\}$ be a collection of subgraphs of $G$ such that every edge of $G$ is contained in ...
- 242
3
votes
1
answer
343
views
Reference request: about “SNF” (Smith Normal Form)
I've read about some studies on the Paley I Construction. Among them I found the following notations ( See this page: https://documents.uow.edu.au/~jennie/matrices/32P02.html ).
$$SNF:1,2^a,4^{b},8^{b}...
- 4,713
4
votes
2
answers
686
views
Is there a way to find a representative set for double cosets of groups?
Let $\lambda=(\lambda_1,\lambda_2)$, $\mu=(\mu_1,\mu_2)$ be two compositions of $n$. Just to remind that $\lambda$, $\mu$ are not necessarily partitions. Denote $S_{\lambda}$ and $S_{\mu}$ the Young ...
- 61
2
votes
0
answers
100
views
Another (unique) algorithm for the A329369
Let $a(n)$ be A329369 (i.e, number of permutations of ${1,2,...,m}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \leqslant k ...
- 4,938
3
votes
1
answer
606
views
Matryoshka doll problem
Notation: We fix some integer $d \geq 1$ and $N \geq 2$. We use $[m, n]$ to denote the set of integers $\{m, \dots, n\}$, and $\mathbb L_N := [1, N]^d$ to denote the set $\{1, \dots, N\}^d \subset \...
- 6,215
6
votes
1
answer
127
views
Convex planar regions with all area bisectors having equal length
Following A claim on the concurrency of area bisectors of planar convex regions, let me record a couple of simple queries.
An area bisector (perimeter bisector) of a planar convex region is a chord ...
- 37.7k
3
votes
0
answers
155
views
Correspondence between even and odd permutations in $S_5$
I am working on the Davenport constant for symmetric groups, $D(G)$
, which is the minimal number $d$
such that every sequence of $d$
elements in the group G
is one-product sequence, i.e, we can ...
1
vote
1
answer
86
views
Isomorphic hypergraph duals
Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$.
We say hypergraphs $H_i=(V_i, E_i)$ for ...
- 13.4k
1
vote
0
answers
67
views
Conjecture on the increasing efficiency of the shortest minimum-link polygonal chains covering any grids of the form $\{0,1,2\}^k$ as $k$ grows
From the well-known Nine dots problem, we know that we need a polygonal chain with at least $4$ edges to connect the $9$ points of the planar grid $G_{3,2}:=\{\{0, 1, 2\} \times \{0, 1, 2\}\} \subset \...
- 1,451
10
votes
3
answers
1k
views
What did Rota mean by "one can define cumulants relative to any sequence of binomial type"?
This question is cross-posted from MSE.$\newcommand{\E}{\mathbb{E}}$
Near the end of "Finite Operator Calculus" (1976), G.C. Rota writes:
Note that one can define cumulants relative to any ...
1
vote
0
answers
76
views
Shellable non-pseudomanifolds with dimension greater than 2
Shellability of simplicial balls and spheres (simplicial complexes whose geometric realizations are homeomorphic to balls and spheres) has been studied quite extensively. There are many explicit ...
3
votes
0
answers
188
views
Frankl's conjecture for infinite lattices
Given a poset $L$, call it trivial if $\left|L\right| < 2$ and let $\mathcal I\left(L\right)$ be its poset of ideals, $\mathcal C\left(L\right)$ be its set of chains, and $\mathcal M\left(L\right)$ ...
- 63.9k
2
votes
2
answers
205
views
Monotonicity of the sum of coefficients of a family of generating functions
Let
\begin{equation*}
A_{n,w}(z)=\left(\sum_{i=0}^{\lfloor\frac{w}{2}\rfloor-1}\binom{w}{i}z^i+\frac{1}{2^{(w+1)\bmod 2}}\binom{w}{\lfloor\frac{w}{2}\rfloor}z^{\lfloor\frac{w}{2}\rfloor}\right)^{n/w}
\...
- 23
4
votes
1
answer
485
views
Intersection theory on moduli spaces of curves without marked points
1. There are a lot of works concerning the intersection theory on the moduli spaces of curves $\mathcal M_{g,n}$ (and their Deligne-Mumford compactifications $\overline{\mathcal M}_g$), for $n>0$.
...
- 2,175
1
vote
0
answers
85
views
Closed form for the family of polynomials
Let $s(n,k)$ be a (signed) Stirling number of the first kind.
Let $R(n,x)$ be the family of polynomials such that
$$
R(2n+1,x) = xR(n,x), \\
R(2n,x) = x(R(n,x+1) - R(n, x)), \\
R(0, x) = x
$$
Let $\...
- 4,938
7
votes
1
answer
390
views
Questions on symmetric Hadamard matrices
Definitions: An $n\times n$ Hadamard matrix (HM for short) is a matrix whose entries are either $1$ or $−1$ and whose rows are mutually orthogonal.
If $A$ is a symmetric matrix, then $A = A^T$ and if $...
- 696
8
votes
2
answers
270
views
Equal segmentation of a series of numbers
How can a series of real numbers be split into subsets in a way that the sum of the real numbers within each subset is as equal as possible?
Coming across from StackOverflow this is the first time, I'...
- 63.9k
2
votes
0
answers
46
views
Chromatic number of the dual hypergraph [duplicate]
Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$.
If $\kappa>0$ is a cardinal, a map $...
- 48.9k
11
votes
3
answers
636
views
Domination problem with sets
For nearly two years, I have been struggling with the next task I have already published on MSE, but unfortunately with no respond.
Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
...
- 101
0
votes
0
answers
43
views
Locally uniformly convexity in kernels (generalized definition of graphon) with cut norm
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
1
vote
0
answers
58
views
Simple recursion for the A329369 using Stirling numbers of both kinds
Let $s(n,k)$ be a (signed) Stirling number of the first kind.
Let $n \brace k$ be a Stirling number of the second kind.
Let $a(n)$ be A329369 (i.e, number of permutations of ${1,2,...,m}$ with ...
- 4,938
6
votes
0
answers
254
views
Maximal bijection-dodging families on $\mathbb{N}$
We say that a family ${\cal S}\subseteq{\cal P}(\mathbb{N})$ is bijection-dodging if there is a bijection $\varphi:\mathbb{N}\to\mathbb{N}$ with $\varphi(T)\notin {\cal S}$ for all $T\in{\cal S}$.
...
- 800
23
votes
3
answers
3k
views
Proofs of parity results via the Handshaking lemma
I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).
Let me ...
- 32.1k
2
votes
1
answer
208
views
How many cap sets are there?
Most research on cap sets that I'm aware of focuses on the size of a cap set. Are there any results about the number of maximum-cardinality cap sets?
For example, it is known that in the game of SET, ...
CommunityBot
- 1
6
votes
1
answer
388
views
What is the max number of self-segregating words of length n?
A set of words S is called self-segregating if you don't need whitespaces to read them. It means that for any two words from S no new words from S arise between them.
For example the set ab, bc, ac, ...
- 125
4
votes
2
answers
299
views
Is there a set of point $S \subset \mathbb R^2$ such that $|\{C: C \text{ is unit circle boundary }, |C \cap S| = 10\}| > |S|$
There are some blue points and red points on the plane such that in the boundary of every unit circle centered at one blue point there are exactly 10 red point. Can the number of blue points strictly ...
31
votes
2
answers
3k
views
Is there a "finitary" solution to the Basel problem?
Gabor Toth's Glimpses of Algebra and Geometry contains the following beautiful proof (perhaps I should say "interpretation") of the formula $\displaystyle \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} ...
- 4,713
3
votes
1
answer
205
views
Cartesian product of $(k-2)\text{-times } [\text{Interval}_1] \times [\text{Interval}_2] \times [\text{Interval}_2]$
This is a soft question, hoping that it is still appropriate for this forum.
I need to describe twice the following region of $\mathbb{R}^k$ (i.e., we are in a $k$-dimensional Euclidean space, where $...
- 1,451
1
vote
0
answers
42
views
What lower bounds are known for pair crossing number and related questions in multigraphs?
So in terms of crossing number https://arxiv.org/pdf/1808.10480 gives a lower bound of $O(e^{2.5}/n^{1.5})$ for multigraphs with no face of length 2 with no node contained inside.
What do we know ...
- 111
1
vote
0
answers
108
views
Schur Weyl Duality for Maximal Torus
I wanted to know if there's some version of Schur Weyl Duality for the maximal torus $T \subset \operatorname{GL}(V)$? Is there also some combinatorial object which might be useful for the same?
1
vote
1
answer
173
views
Some ideas about parking functions and integer partitions
We know that a integer partition of $\lambda=(\lambda_1, ..., \lambda_m)$ of $n$ satisfying $\lambda_1\geq \cdots \geq \lambda_m$ and $\sum_{i=1}^m\lambda_i=n$. Let $\mathcal{P}(n)$ be the set of ...
- 175
1
vote
1
answer
1k
views
Hamming distance distribution induced by binary hypercube
The following problem arises in a particular machine learning problem:
Assume that we have $n$ independent Bernoulli random variables with parameters $p_i$, e.g. $n=5$ and the $p$ vector is $(0.2, 0....
- 10.4k
3
votes
1
answer
595
views
Euro2024-inspired scoring problem
Motivation. The Euro 2024 soccer football championship is in full swing, and the male part of my family are avid watchers. Right now the championship is in the group stage where every group member ...
- 4,219
1
vote
1
answer
130
views
reference for a formula of the Motzkin triangle on OEIS
Motzkin triangles (OEIS A064189) $[T_{n,k}]$ are the Riordan arrays $(M(x),xM(x))$, where $(M(x))$ is the g.f. for the Motzkin numbers(OEIS A001006). The OEIS page shows that $$T_{n,k}=\frac{k}{n}\...
- 135
0
votes
0
answers
82
views
On 'Bisecting sections' of 3D convex bodies
Following shadows and planar sections, we ask about bisecting sections. This post also continues Convex planar regions with all area bisectors having equal length and A claim on the concurrency of ...
- 5,979
1
vote
0
answers
132
views
Sequence that sums up to A000153
Let $a(n)$ be A329369 (i.e, number of permutations of ${1,2,...,m}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \leqslant k ...
- 4,938
0
votes
1
answer
61
views
Is every connected edge-swapping graph edge-transitive?
We say that a connected, simple, undirected graph $G=(V,E)$ is edge-swapping if for every $e\in E$ there is a graph isomorphism $\varphi:G\to G$ such that for the restriction $\varphi|_e$ we have $\...
- 20.9k
2
votes
1
answer
170
views
The number of small sum-free subsets of $[n]$
I'm interested in the following question:
Can we bound the number of sum-free subsets of size $k$ of $\{1,2,\dots,n\}$, as a function of $n$ and $k$? In particular, what can we say about a function $...
- 3,319
35
votes
12
answers
4k
views
Open questions about posets
Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
- 1,644
42
votes
2
answers
2k
views
How decreasing can a bijection $f:\mathbb{N}\to\mathbb{N}$ be?
This is a follow-up to this question by
Dominic van der Zypen. For each bijection $f:\mathbb{N}\to\mathbb{N}$, let
$$\operatorname{rc}(f) := \liminf_{N\to\infty} \frac{\left|\left\{(m,n)\in\{1,\dots,N\...
- 114k
-1
votes
1
answer
825
views
How to calculate determinants of such types?
Consider next determinant that we want to expand around $h=1$
\begin{eqnarray}
Z_q \ = \ h^{N N_f} \ \ \left ( \prod_{n=1}^{N} \ \sum_{l_n=0}^{N_f -q} \ h^{2l_n+q} \ \binom{N_f}{l_n} \right ) \ \...
CommunityBot
- 1
7
votes
1
answer
412
views
*Friendly* coloring of a digraph
Given a simple, finite, directed graph $G$, let's call a $2$-coloring of the vertices of $G$ is friendly if every vertex has an out-neighbour of the same color (while not all vertices are same-colored)...
- 12.9k
1
vote
0
answers
194
views
'Imperfect' squarings of a square
Ref: https://en.wikipedia.org/wiki/Squaring_the_square
This is a planar version of the question at Cubing the cube - as 'perfectly' as possible.
Question: How does one cut a square into the ...
CommunityBot
- 1