All Questions
Tagged with combinatorics or co.combinatorics
11,021 questions
2
votes
1
answer
111
views
Is there a ternary Cayley graph on 27 vertices that is a non-complete core?
Is there a non-complete ternary Cayley graph that is a core with $3^3 = 27$ vertices?
By a ternary Cayley graph, I mean a (simple, undirected) graph whose vertex set is $\mathbb{Z}_3^n := \bigoplus_{i ...
- 331
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
1
vote
0
answers
149
views
Inequalities in the classic proof of perfect matching in Erdős–Rényi graph
I am checking the classic paper by Erdős and Rényi, "On the existence of a factor of degree one of a connected random graph" with the link here. I am curious about the computation of the ...
- 97
0
votes
2
answers
115
views
Upper bounds on quotients of binomial coefficients
Let $\gamma>1$ be a real number and let $n\in \mathbb{N}$.
Define $f\colon\mathbb{N}\to[0,1]$
$$
f(n_0) = \frac{\binom{n-n_0}{m}}{\binom{n}{m}},
$$
where
$$
m = \Big\lfloor{\frac{n}{\lceil\gamma ...
8
votes
1
answer
255
views
Maximal Ramsey families
We say that a family $\mathcal R\subseteq \mathcal P(\omega)$ is Ramsey if
$\bigcup \mathcal R = \omega$, and
for every map $f:\mathcal R \to \{0,1\}$ there is an infinite set $X\subseteq \omega$
...
- 48.8k
-3
votes
1
answer
73
views
Non-Ramsey function $f:[\omega]^{<\omega}\to\{0,1\}$ [closed]
Let $\newcommand{\o}{\omega}\o$ be the set of non-negative integers, and for any set $X$, let $\newcommand{\oo}{[\o]^{<\o}}X^{<\o}$ denote the collection of all finite subsets of $X$.
What is an ...
- 48.8k
1
vote
1
answer
73
views
"Gray code" for $[\omega]^{<\omega}$
Let $\newcommand{\oo}{[\omega]^{<\omega}}\oo$ denote the collection of finite subsets of the set of non-negative integers $\newcommand{\o}{\omega}\o$.
If $A,B$ are any sets, let $A \,\triangle \, B ...
- 48.8k
1
vote
1
answer
99
views
Is there any known upper bound for the local crossing number of a graph drawing in the plane?
The local crossing number ${\rm LCR(G)}$ of a graph $G$ is defined as the least nonnegative integer $k$ such that the graph has a $k$-planar drawing. In other words, it is the smallest possible number ...
- 1,190
2
votes
0
answers
182
views
Algorithm for $\frac{1}{1-x} = \sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n}\frac{1-kx}{1+kx}$
Let $a(n)$ be A208832. Here
$$
\frac{1}{1-x} = \sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n}\frac{1-kx}{1+kx}.
$$
Start with vector $\nu$ of fixed length $m$ with elements $\nu_i = 1$ (that ...
- 4,928
4
votes
0
answers
67
views
is a 4-connected planar graph still Hamiltonian after removing an edge?
We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
- 1,851
1
vote
1
answer
324
views
Want to show that this sum vanishes modulo p
Let $p\ge 5$ be a prime number, and consider the following sum:
\begin{align}
S &= \sum_{v_0 = 1}^{p - 2} \binom{p - 2}{v_0} \, \theta^{v_0 - 1}(Y) \cdot \theta^{p - 2 - v_0}(Y) \\
&+ \frac{1}{...
- 29
0
votes
0
answers
52
views
Reference request for the determinant of a matrix constructed from Pascal's triangle
One can prove by induction that the matrix $M^{(n)}$ given by
$$ \begin{pmatrix}
1 & 1 & 1 & 1 & \dots & \binom{n}{0} \\
1 & 2 & 3 & 4 & \dots & \binom{n+1}{1} \...
- 5,546
1
vote
1
answer
76
views
Determinant formula for a certain parametrized M-matrix
Let $P_{ij}$ be variables, and let $A \in \mathbb{R}^{n\times n}$ be the matrix defined by
$$
A_{ij} = \begin{cases}
-P_{ij} & i \neq j,\\
P_{i1} + P_{i2} + \dots + P_{in} & i=j.
\end{cases}
$$...
- 20.2k
4
votes
0
answers
115
views
Complexity to find "short" (e.g. polynomial in diameter) decomposition of the permutation into the product of generators?
Question 1: Consider the symmetric group $S_n$ and some set of permutations $p_i$. Given permutation $g$ - what is known about the algorithmic complexity to decompose $g$ into product of $p_i$ ...
- 24.9k
9
votes
0
answers
292
views
Tilings in finite (not necessarily Abelian) groups
Let $G$ be a finite (not necessarily abelian) group. We call $A \subseteq G$ a right-tiling (for simplicity, a tiling) of $G$ if there exists a $B \subseteq G$ so that
$$ G = \bigsqcup_{b\in B} bA.$$
...
- 1,354
0
votes
0
answers
44
views
Lattice points in the boundary of a Minkowski sum of two convex lattice polygons
Let $P$ and $Q$ be two convex lattice polygons in $\mathbb{R}_+^2$ and let $P+Q$ be their Minkowski sum. Given a set $S \subset \mathbb{R}^2$, we let $L(S) =\#( S \bigcap \mathbb{Z}^2)$.
The equality $...
- 183
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-...
1
vote
0
answers
51
views
Coarse-graining a hypergraph
$\DeclareMathOperator{\poly}{\mathrm{poly}}$I have asked this question on math.SE here, but couldn't get a satisfactory answer. I have also asked a related question on math overflow here, but haven't ...
- 277
8
votes
0
answers
244
views
Strengthening of Frankl's union-closed sets conjecture: An algebraic approach
Let $\mathcal F$ be a union-closed family of subsets of $[n]=\{1,2,...n\}$ and $n$ real numbers $x_1,x_2,...,x_n\geq 1$.
Conjecture: There exists $k\in [n]$ such that:
$$\sum_{k\in A,A\in \mathcal F}\...
- 1,462
3
votes
0
answers
101
views
Tuple rearrangement: a combinatoric problem emerging from the Hurwitz action on Coxeter groups
I am working on Artin Groups, so called Dual Artin groups and the conjecture that they are isomorphic. Tuples of $n$ group elements can be acted on by the braid group $B_n$ in a particular way called ...
- 31
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
0
votes
1
answer
98
views
Only special permutations result in a constant expression when permuting coefficients in a sum involving binomials?
Fix $n\geq 1$ and let $p_k(x) := x^k(x-1)^{n-k}$.
Suppose $\pi$ is a permutation on $\{0,1,\dotsc,n\}$, such that
$$
\sum_{k=0}^n (-1)^k \binom{n}{k} p_{\pi(k)}(x) \text{ is a constant}.
$$
Must it be ...
- 15.8k
1
vote
1
answer
134
views
A distributive identity for products of partition functions
An $r$-composition of a non-negative integer $s$ is an expression $s=s_1+s_2+\cdots+s_r$ where the $s_i$ are also non-negative integers. Define $k(r,s):=\sum \pi(s_1)\pi(s_2) \cdots \pi(s_r)$ where ...
- 161
11
votes
2
answers
386
views
Bounds for the difference in the number of ones in $M$ and $M^{-1}$
If $M$ is a full rank $n$ by $n$ binary matrix over $\mathbb{F}_2$, how much larger or smaller can the number of $1$s in $M^{-1}$ be, compared to the number of $1$s in $M$?
Clearly the identity matrix ...
- 3,377
0
votes
0
answers
56
views
Does Forcing conjecture equals to assume the host graph is regular?
Given two graphs $H$ and $G$, the homomorphism density $t(H, G)$ is defined as the proportion of mappings from the vertices of $H$ to the vertices of $G$ that preserve adjacency. Formally,
$$
t(H, ...
- 349
9
votes
3
answers
1k
views
Examples of combinatorial problems where the only known solutions, or most "natural" solutions, use representation theory?
In Solution of two difficult combinatorial problems with linear algebra, Robert Proctor presents two simply stated combinatorial problems, and gives solutions to them using a linear algebraic approach ...
2
votes
0
answers
67
views
$R$-recursion for A006351
Let $a(n)$ be A006351 (i.e., number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon). Here exponential generating function is $A(x)$ such that $B(x) = ...
- 4,928
3
votes
0
answers
92
views
Realized graph of majority of permutations
This question was asked several months ago on Math.SE, but remains unsolved.
For any collection of permutations of $\{1,2,\dots,n\}$, we say that it realizes a directed multigraph with $1,2,\dots,n$ ...
- 277
4
votes
1
answer
119
views
Proving Equal Set Sizes in Sequential Point Selection on a Real Interval with Variable-Length Intervals
I'm here as an engineer working on a point sampling algorithm and I've noticed that when I perform the algorithm on an ordered set of points in one direction it selects the exact same number of points ...
- 151
4
votes
1
answer
304
views
Minimum eigenvalue of a symmetric matrix
I was solving a problem and got stuck on the following:
Let $[p] = \{1, \ldots, p\}$ where $p \in \mathbb{N}$. Let $P(n, r)$ denote the set of all injective functions from $[r]$ to $[n]$ and write a ...
- 41
1
vote
1
answer
77
views
Enumeration of permutations with prescribed numbers of fixed points and excedance/deficiency statistics
Consider the following refinement of permutation statistics. For $π ∈ S_n$, let:
$\mathrm{fix}(π) = |\{i : π(i) = i\}|$ (number of fixed points)
$\mathrm{exc}(π) = |\{i : π(i) > i\}|$ (number of ...
- 11
0
votes
0
answers
60
views
Bounding number of commutators of a certain type
Say I have a vector space $V$ over $\mathbb{C}$, generated by $2n$-letters, $(x_1,...,x_n,y_1,...,y_n)$. Let $C_d$ denote the commutators on $V$ of length $d$, and let $(B_1,...,B_r)$ denote a basis ...
- 2,907
2
votes
0
answers
59
views
$R$-recursion for A338193
Let $a(n)$ be A338193. Here generating function is $A(x)$ such that
$$
A(x) = 1 + \int\frac{\left(\frac{x}{A(x)}\right)'}{\left(\frac{x}{(A(x))^2}\right)'} \, dx.
$$
Let
$$
R(n, q) = \begin{cases}
1 &...
- 4,928
0
votes
0
answers
58
views
Searching another example related to the union-closed sets conjecture
Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.
Let $\mathcal{H} \subseteq \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (...
- 990
2
votes
1
answer
207
views
Proving an exponential sum inequality for symmetric Hamming distance sequences in binary vectors
Background: Let $X = \{0,1\}^k$ represent the set of all binary vectors of length $k$. For two binary vectors $x, y \in X$, the Hamming distance $d_H(x, y)$ is defined as the number of positions where ...
- 349
0
votes
0
answers
166
views
Combine two types of permutations in a Young diagram?
Given a Young diagram $Y$, for each row $R$ choose a permutation $\sigma_R$ of $\{1,\dots, |R|\}$, where $|R|$ is the size of row $R$. Let $\sigma_R(i)$ be the “row coordinate” of the $i$th cell in ...
- 281
-2
votes
1
answer
141
views
Solution to Erdos-Ulam problem [closed]
I have solved the Erdos-Ulam problem (see link) and can construct a set that satisfies the conditions (dense in R2 with all interpoint distances rational). I have expanded the solution from two ...
6
votes
1
answer
173
views
$\omega$-de-Bruijn sequences
Let $\omega$ denote the set of non-negative integers. For which integers $n>1$ is there a sequence $b_n: \omega\to\omega$ with the following property?
Whenever $v\in\omega^n$ there is a unique $...
- 48.8k
26
votes
0
answers
512
views
A non-self-intersecting unit side length polygon in a unit square has odd number of sides unless it is the square itself
This is the same question as here in SE.
I have a conjecture, it is like this:
Suppose there is a non-self-intersecting polygon lies inside a closed square of length $1$. The polygon has every side ...
- 843
2
votes
1
answer
71
views
APs in sumsets of exponential growing sequences
I posted this initially on SE, but after I didn't found a particular reference on it, I decided it would be more appropriate to post it here. A friend shared this observation with me and I thought ...
- 63
3
votes
0
answers
168
views
Basis of Specht module of symmetric groups
I am reading the construction of the Specht module from James's book. The Specht module of a symmetric group corresponding to a partition $\lambda$ is spanned by all polytabloids $e_{t}$ associated ...
- 179
5
votes
0
answers
140
views
Combinatorial rule for Schubert times Coxeter-Schubert
For $w \in S_n$, let $\mathfrak{S}_w$ be the Schubert polynomial. For geometric reasons, we know that $\mathfrak{S}_u \mathfrak{S}_v = \sum c_{uv}^w \mathfrak{S}_w$ for some nonnegative integers $c_{...
- 156k
1
vote
0
answers
161
views
Efficient algorithm for A217061
Let $a(n)$ be A217061. Here
$$
a(n) = \sum\limits_{m=1}^{n}\frac{1}{(m-1)!}\sum\limits_{k=0}^{n-m}(n+k-1)!\sum\limits_{j=0}^{k}\frac{1}{(k-j)!}\sum\limits_{\ell=0}^{j}\frac{2^{\ell-j}(-1)^{\ell+j}s(n-...
- 4,928
1
vote
0
answers
98
views
Simplicial complexes on $[n] := \{0,\ldots,n\}$ that are identical under any contraction of consecutive vertices
For $n\in\mathbb{N}$, let us denote by $\Omega(n)$ the set of all (possibly empty) “abstract” simplicial complexes on $[n] := \{0,\ldots,n\}$ (“on $[n]$” means “labeled by the elements of $[n]$”). To ...
- 32.5k
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
10
votes
0
answers
287
views
Coefficients of polynomials vs trigonometric product
Let's consider the family of sequences of coefficients in the expansion
$$\prod_{i=0}^{n-1}(1+x^{3^i}+x^{3^{i+1}})=\sum_{k\geq0}a_n(k)\, x^k.$$
Remark. Evidently, the RHS is a finite sum.
Here is a ...
- 43.2k
0
votes
0
answers
45
views
Another version of Sidorenko's conjecture(?)
I would like to ask a question about Sidorenko's conjecture. Here is the background of my question:
Quasi-random graphs
A sequence of graphs $(G_n)$ is called quasi-random if it satisfies certain ...
- 349
0
votes
0
answers
36
views
Construct a maximum matching from a minimum vertex cover in bipartite graph?
Konig's theorem in graph theory says that for a bipartite graph $G$, the size of maximum matching in $G$ is equal to the size of minimum vertex cover of $G$.
Typically, one of the proofs is to ...
- 281
0
votes
0
answers
27
views
Projection onto polytopes as tropical polynomial
Let $C$ be a convex polytope in $\mathbb{R}^n$ with $m$ extremal points. Let $p\in \{1,2\}$.
Can the $\ell^p$-projection $\Pi_C:\mathbb{R}^n\to C$
$$
\Pi_C(x) \in \operatorname{argmin}_{z\in C}\, \|x-...
- 364
1
vote
1
answer
92
views
Equivalence of sequences related to A033264
Let $a(n)$ be A033264 (i.e., number of blocks of $\{1,0\}$ in the binary expansion of $n$). Here
$$
a(4n) = a(4n+1) = a(2n), \\
a(4n+2) = a(n)+1, \\
a(4n+3) = a(n), \\
a(0) = 0.
$$
Let
$$
\ell(n) = \...
- 4,928