All Questions
Tagged with combinatorics or co.combinatorics
11,021 questions
2
votes
1
answer
105
views
How to maximize the variance of a subset of integers?
$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
- 46
4
votes
1
answer
147
views
Lower bounding a sumset quantity
Given $A,B \subset[0,...,d]^n$ such that $A \cap B = \phi$. Can we show
$$ |(2A \cup 2B) \triangle (A + B)| \geq \Omega_d({\rm poly}(|A|,|B|))$$
where $2A = A+A, 2B = B+B$ and we are taking the ...
- 341
0
votes
1
answer
107
views
Coxeter matrix of Dyck path
I am trying to understand Gjergji Zaimi's answer in What are the periodic Dyck paths?. In the third paragraph he claims that
Next, we define the matrix $X_D$
similarly to the Cartan matrix except we ...
- 85.6k
0
votes
0
answers
20
views
Vertex coloring of the Rado graph
Is there a reference for the following fact about the Rado graph (the random countable graph) which came up in an answer to this question?
If the vertices of the Rado graph $G=(V,E)$ are colored with ...
- 13.4k
8
votes
1
answer
531
views
How large can the dimension of a 'Span of powers of a finite field basis' be?
Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
CommunityBot
- 1
0
votes
0
answers
23
views
Graph classes which have small edge k-cuts
I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the ...
- 516
1
vote
1
answer
177
views
Refinement of face vectors of the simplicial noncrossing hypertree complexes of McCammond
Einziger on page 65 of "Incidence Hopf algebras: Antipodes, forest formulas, and noncrossing partitions" presents the antipode of a noncrossing partition Hopf algebra as a graded sequence of partition ...
CommunityBot
- 1
3
votes
0
answers
67
views
While expanding Jack polynomials in monomial basis
Denote $\mathbf{z}=(z_1,\dots,z_n)$. Let $P_{\kappa}(\mathbf{z};\alpha)$ be the symmetric Jack polynomials and suppose they are expanded in terms of the monomial symmetric basis $m_{\rho}(\mathbf{z})$ ...
- 43.2k
4
votes
1
answer
229
views
Minimum number of possible proper colorings
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
For any graph with $2k-2$ edges such that it can be properly colored using $k$ colors. What is the ...
- 91
2
votes
1
answer
91
views
Number of disjoint set triplets in a union-closed family
Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the ...
- 109k
1
vote
0
answers
29
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
5
votes
2
answers
723
views
Shifting an irrational binary sequence
Let $\newcommand{\tn}{\{0,1\}^\mathbb{N}}\tn$ be the collection of all infinite binary sequences. For $s\in\tn$ and $k\in\mathbb{N}$ let the left-shift of $s$ by $k$ positions, $\ell_k(s)\in \tn$, be ...
- 6,652
37
votes
3
answers
2k
views
How to prove the identity $L(2,(\frac{\cdot}3))=\frac2{15}\sum\limits_{k=1}^\infty\frac{48^k}{k(2k-1)\binom{4k}{2k}\binom{2k}k}$?
For the Dirichlet character $\chi(a)=(\frac a3)$ (which is the Legendre symbol), we have
$$L(2,\chi)=\sum_{n=1}^\infty\frac{(\frac n3)}{n^2}=0.781302412896486296867187429624\ldots.$$
Note that this ...
- 215
6
votes
0
answers
128
views
Is there a more natural way to define the Young symmetrizer and the Specht module?
It's well known that Young symmetrizer is a fundamental tool in the representation theory of symmetric groups.
For instance, for every Young diagram $\lambda\vdash n$, we construct a Young tableau $T_\...
5
votes
3
answers
284
views
The max-clique chromatic number of a graph
Let $G = (V,E)$ be a graph. Every clique, that is, complete subgraph, is
contained in a maximal clique with respect to $\subseteq$ (this is
an easy consequence of Zorn's Lemma). Let $\newcommand{\MC}{\...
- 13.4k
1
vote
0
answers
160
views
+50
A question relates to edge chromatic-polynomial
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
For any graph with $m$ edges such that it can be properly colored using $k$ colors. What is the minimum ...
- 91
2
votes
0
answers
110
views
+50
How to apply Pohlig Hellman using a very limited set of auxiliary inputs in that case?
So I was reading about Talotti, Paier, and Miculan - ECC’s Achilles’ Heel: Unveiling Weak Keys in Standardized Curves. The underlying idea is to lift the discrete logarithm problem to $\mathrm{prime}−...
- 87
7
votes
3
answers
707
views
Properties of $P_{n}(x)={e}^{-x}\sum_{k=0}^{\infty}\frac{a_{k,n}{x}^{k}}{k!}$
I know this will sound like a general question, but given the structure $$P_{n}(x)={e}^{-x}\sum_{k=0}^{\infty}\frac{a_{k,n}{x}^{k}}{k!}$$ where $$a_{k,n} = \frac{1}{\prod_{i=1}^{n} (k+2i) }, $$ what ...
1
vote
0
answers
108
views
Generalized identity with Stirling numbers of the second kind and falling factorials
It is known that Striling numbers of the second kind satisfy the relation
$$
\sum\limits_{k=0}^{n}{n \brace k}(x)_k = x^n.
$$
where $(x)_n$ is the falling factorials such that
$$
(x)_n = x(x-1)(x-2)\...
- 4,928
1
vote
0
answers
375
views
How to verify if sets satisfying cardinality condition exist? [migrated]
I am trying to find out if sets satisfying the following properties exist:
Call the sets $A_1, \ldots, A_{20}$ and $B_1, \ldots, B_{20}$.
For each $i \in \{1, \ldots, 20\}$, $|A_i| \in \{1,2\}, |B_i| ...
- 39.7k
11
votes
3
answers
557
views
In search of a $q$-analogue of a Catalan identity
Let $C_n=\frac1{n+1}\binom{2n}n$ be the all-familiar Catalan numbers. Then, the following identity has received enough attention in the literature (for example, Lagrange Inversion: When and How):
\...
- 31
0
votes
1
answer
82
views
Median of cardinality of set union
Let $U$ be an arbitrary finite universe (you can just think of it as $[N]=\{1,2,\ldots,N\}$), and $\mathbf{S} = (S_i)_{i \in [n]}$ ($S_i \subseteq U$) be the sets that we are drawing from. Define a ...
- 29
1
vote
0
answers
22
views
maximal length of saturated chains with a given terminal point in the lattice of partitions of an integer ordered by dominance
Let $Pr(n)$ be the set of partitions of the positive integer $n$. This is a lattice with respect to the dominance order: if $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$, $\mu=(\mu_1\geq\mu_2\geq\cdots)...
- 593
10
votes
2
answers
909
views
Status of the Stanley–Stembridge conjecture
As mentioned in the post on Stanley's 25 positivity problems, Tatsuyuki Hikita posted a preprint on October 16, 2024 purporting to prove Problem 21, the Stanley–Stembridge conjecture about e-...
- 82.6k
7
votes
1
answer
539
views
Distribution of longest run locations in a random string
Let x be a random n-bit string, and let $I ={i_1,i_2,...,i_n}$ be the starting indexes of the longest 0-runs of x, sorted in decreasing order (so $i_1$ is the starting index of the longest (~$\log n$) ...
CommunityBot
- 1
21
votes
1
answer
737
views
Does $A-A=\mathbb Q$ hold for $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$?
Let $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$. Then
$$A-A:=\{a-b:\ a,b\in A\}=\{u^4+v^4-x^4-y^4:\ u,v,x,y\in\mathbb Q\}.$$
Motivated by Question 415482, here I ask the following question.
Question. Is it true ...
- 1,567
9
votes
1
answer
456
views
A conjecture related to Frankl's conjecture
Let $\mathcal{F}\subseteq2^{[n]},\emptyset\in\mathcal{F}$ be an union-closed family of sets. For $S\in\mathcal{F}$, let $w(S)$ be the number of subsets of $S$ in $\mathcal{F}$. Does there always exist ...
- 5,409
-1
votes
1
answer
93
views
Variance of bins for N balls into M bins [closed]
If I throw N balls independently into M bins with uniform probability, the expected mean of the M bins is N/M balls.
What is the expected variance of the M bins?
I was thinking of what bin size I ...
- 111
0
votes
1
answer
187
views
Matching bins up to shuffling II
Suppose a school purchases a set $\mathcal{S}$ of balls, say
$$\displaystyle \mathcal{S} = \{b_1, b_2, \cdots, b_n\}$$
with $n$ very large. The balls $b_j$ are pairwise distinct and have distinct ...
CommunityBot
- 1
2
votes
2
answers
496
views
Nested De Bruijn sequences
A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1 a_2 \dots a_{2^n},$ with $a_i \in \{0,1\},$ and such that each of the $2^n$ binary $n$-uples occurs exactly once in $S.$
Is ...
- 63.9k
4
votes
0
answers
106
views
Differential duality: Triangular codes vs. VT codes / Single-substitution vs. Single-deletion
Here is the introduction to my problem:
Codes correcting single-deletion. Let $q$ and $n$ be non-negative integers, and let $\mathbf{x}= \left ( x_{1}, x_{2}, \ldots, x_{n} \right )\in\mathbb{Z}_{q}^{...
- 10.4k
19
votes
4
answers
1k
views
Minimal graphs with a prescribed number of spanning trees
As it's long ago since Erdős died and MathOverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem that I ...
- 8,597
1
vote
1
answer
177
views
Spectral characterization of complete or complete bipartite graphs
The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs:
Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
CommunityBot
- 1
2
votes
1
answer
107
views
Counting problem, tiling rectangle with two types right isosceles triangle
How many ways are there to tile a rectangle of size $m\times n$ with two types of isosceles triangle, type 1 having area $\frac{1}{2}$ and type 2 having area 1?
I know with only type 1 there are $2^{...
CommunityBot
- 1
7
votes
1
answer
165
views
$|G|/\alpha(G) \leq \eta(G)$ where $\eta(G)$ is the Hadwiger number
Let $G=(V,E)$ be a finite, simple, undirected graph. The Hadwiger number $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.
Hadwiger's celebrated conjecture states that $\chi(...
CommunityBot
- 1
0
votes
0
answers
112
views
Minesweeper constructions in combinatorics
In a related question I asked if constructions based on Sudoku puzzles could be used to obtain any deep results in combinatorics and noted that there were papers of Greenfeld and Tao where Sudoku ...
- 5,146
0
votes
1
answer
81
views
Image and pre-image integer choice function
Let $\newcommand{\Nplus}{\mathbb{N}^+}\Nplus$ denote the set of positive integers. Is there a function $f:\Nplus\to\Nplus$ with the following property?
For all $(a,b)\in \Nplus\times\Nplus$ there is ...
- 109k
0
votes
0
answers
137
views
State of the art on attempts to solve the elliptic curve discrete logarithm problem through transfering the problem to a weaker curve
Let an elliptic curve $E$, and 2 points on such curve $P$ and $O$ the methods I’m talking about consist in creating a weaker elliptic curve $F$ and mapping $P$ and $O$ to $F$ while successfully ...
- 87
6
votes
5
answers
542
views
Tiling with ten-fold symmetry and (unoriented) Penrose tiles?
Consider tilings of the plane made out of rhombi of side 1 and either angles $\pi/10$ and $2\pi/5$ or angles $\pi/5$ and $3\pi/10$. If we give a certain orientation to the edges and respect that ...
- 2,370
1
vote
1
answer
186
views
Existence of Finite Amicable Groups
I'm interested in exploring the concept of "amicable groups" as follows:
Definition. Two finite groups $G$ and $H$ are called amicable groups if:
$G$ is the direct sum of proper subgroups ...
- 6,357
5
votes
1
answer
259
views
Diagonal analogue of symmetric functions
Let $n$ be a positive integer and consider the ring $R$ of power series over $\mathbb{Q}$ in commuting variables $x_1,y_1,x_2,y_2,...$. Let the symmetric group $\mathfrak{S}$ of permutations of the ...
- 17k
7
votes
4
answers
497
views
Distinguishing finite families of sets by algebras of bounded size
Say that an algebra of sets $K$ distinguishes set $B$ from set $C$ provided that for some $A\in K$, we have exactly one of $A\cap B$ and $A\cap C$ non-empty. Given families $F$ and $G$ of sets, say ...
- 2,555
1
vote
0
answers
123
views
Growth polynomial of the Associahedron graph ? (Is it approximately Gaussian ?)
Consider Associahedron, consider graph build from its vertices and edges. Choose some vertex. Let us count the number of vertices on distances $k$ from the selected vertex. Write a generating ...
- 24.9k
2
votes
0
answers
163
views
Nonabelian groups where every element has small order
Let $G$ be a finite nonabelian group with the property that if $g \in G$, then
$$\DeclareMathOperator{\ord}{ord} \ord(g) \leqslant 10 \log_2 |G|, $$
where $\ord(g)$ is the order of the element $g$, ...
- 1,354
38
votes
1
answer
4k
views
Updates to Stanley's 1999 survey of positivity problems in algebraic combinatorics?
In 1999, Richard Stanley wrote a very nice survey on open problems in algebraic combinatorics, with a specific focus on positivity, called "Positivity problems and conjectures in algebraic ...
- 24.2k
5
votes
1
answer
277
views
Set-theoretic generation by circuit polynomials
Let $P$ be a prime ideal in $S=\mathbb{C}[x_1,\ldots , x_n],$ and write $[n] = \{ 1, \ldots , n \}.$ The algebraic matroid of $P$ can be defined according to circuit axioms as follows: $C\subset [n]$ ...
- 1,046
5
votes
2
answers
241
views
Expansion of key polynomials in terms of non-symmetric Hall-Littlewood polynomials and charge-like statistics
Edit: The problem I pose here is impossible to solve with the basis $H$, in the answer I made to this post I explain why. The only way I can think it to amend the situation would be to try with ...
- 161
1
vote
0
answers
30
views
Balanced cocircuit cover
Are there studies on matroids which can be covered by $r$ cocircuits ($r$ is the rank of the matroid), so each element is covered by a small number of times?
For example, it is known graphic matroids ...
- 63.9k
0
votes
0
answers
34
views
separator and vertex-connectivity
A definition of "separator" is the following: Let $G$ is an $n$-vertex graph, then $S\subseteq V(G)$ is a separator if there is a partition $V=A\cup B\cup S$ such that $|A|,|B|\le 2n/3$ and ...
- 281
56
votes
1
answer
3k
views
Intersecting family of triangulations
Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
- 24.7k