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.
10,560
questions
2
votes
0
answers
512
views
Is there a known proof that $R(5,5)\leq 47$ in Ramsey theory?
As an application to a model describing graphs with partial information, I found what might be an (as yet unverified) proof that $R(5,5)\leq 47$.
According to the Dynamic Survey of Ramsey Numbers at ...
- 3,204
12
votes
4
answers
578
views
A specific collection of subgraphs in $K_{70, 70}$
Does there exist a collection of subgraphs $\{\Gamma_i\}_{i = 1}^{24}$ of $K_{70, 70}$, that satisfy the following two properties:
1)$\Gamma_i \cong K_{i, i} \forall 1 \leq i \leq 24$;
2)Any edge of $...
CommunityBot
- 1
4
votes
1
answer
185
views
Applying a simple involution to Hall-Littlewood polynomials
Consider the Hall-Littlewood polynomial
$$
P_\lambda(x_1,\ldots,x_n;t)=\sum_{\sigma\in S_n/S_n^\lambda}\sigma\left(x_1^{\lambda_1}\cdots x_n^{\lambda_n}\prod\limits_{\lambda_i>\lambda_j}\dfrac{x_i-...
- 380
3
votes
1
answer
150
views
Are there any more polytopes whose 2-faces are identical 4-gons?
What are examples for convex polytope $P\subset \Bbb R^d,d\ge 3$ for which holds
$P$ is 2-face transitive (that is, all 2-faces are equivalent under the symmetries of $P$), and
all 2-faces of $P$ are ...
- 12.6k
6
votes
0
answers
123
views
Squared squares and partitions of $K_{nn}$
This is inspired by a recent question.
Define a square square sum (SSS) of order $n$ to be any partition $$n^2=\sum_1^tc_ii^2 \tag{*}$$ of $n^2$ into square summands. Call it perfect if all $c_i \leq ...
- 30k
5
votes
1
answer
434
views
Polynomial defined recursively by a resultant
Cross posting from MSE.
Definition:
For any natural number $n\ge 3$, define the polynomial $P_{n}\left(x_1,x_2,...,x_{n-1},x_{n} \right)$, with indeterminates $x_{i}$, where $i\in\{1,2,...,n-1,n\}$, ...
- 4,745
5
votes
2
answers
195
views
Coloring in Combinatorial Design Generalizing Latin Square
I have a question about a combinatorial design very similar to a Latin Square, which is arising out of an open problem in graph theory. The design is an $n \times n$ matrix whose entries we want to ...
- 1,327
4
votes
1
answer
114
views
What is the probability of an empty convex $k$-gon among many given points?
Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points.
For a big number $n$ of randomly distributed ...
- 149k
21
votes
1
answer
1k
views
Permutations $\pi\in S_n$ with $\sum_{k=1}^n\frac1{k+\pi(k)}=1$
Let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
Motivated by Question 315568 (http://mathoverflow.net/questions/315568), here I pose the following question.
QUESTION: ...
- 51.6k
9
votes
1
answer
648
views
A stronger version of a problem of Kenneth Brown using representations
Let $G$ be a finite group and $\mathcal{L}(G)$ its subgroup lattice. Let $\mu$ be the Möbius function on $\mathcal{L}(G)$.
The reduced Euler characteristic of the order complex of the coset poset $\{ ...
- 1,368
3
votes
1
answer
177
views
Strict unimodality of bipartite partitions
For non-negative integers $k$ and $l$ let $p(k,l)$ denote the number of vector partitions of $(k,l)$. In other words, $p(k,l)$ is the number of ways of writing
$$
(k,l) = (k_1,l_1)+\dotsb + (k_r,l_r),
...
- 5,594
2
votes
0
answers
152
views
The topological complexity of polytopes
Polytopes arise naturally when modelling fundamental structures in Biology such as RNA and proteins [1,2]. Recently, it occurred to me that a complexity measure on the topology of polytopes might be ...
CommunityBot
- 1
9
votes
2
answers
370
views
Every possible number of partitions by restricting parts?
Write $p(n)$ for the number of integer partitions of $n$. For $S \subseteq \{1, \ldots, n\}$, let $p_S(n)$ be the number of partitions of $n$ with all parts in $S$. So $p(n) = p_{\{1,\ldots,n\}}(n)$....
- 22.2k
3
votes
0
answers
172
views
Find every prime $p$ such that $p^3$ divides $(p-1)!+1$ [duplicate]
My main question is similar to the title:
Are there any primes $p$ such that $p^3$ divides $(p-1)!+1$?
It is hard to find all $p$ such that $p^2$ divides $(p-1)!+1$ (Wilson primes).
So, in my ...
- 501
5
votes
1
answer
713
views
Conjugacy classes in $GL_{n}(Z / pZ)$
Let $p$ be a prime number and $G=GL_n ( \mathbb{Z} / p \mathbb{Z}
)$. Consider the set $U$ of upper-triangular matrices of $G$
having entries of $1$ on the diagonal. The cardinality of $U$ is $p^{\...
- 9,421
12
votes
2
answers
945
views
How rare are unholey permutations?
For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...
- 19.4k
5
votes
1
answer
264
views
Diameter of Cayley graphs of finite simple groups
Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...
- 60.2k
4
votes
0
answers
210
views
How frequent are permutations with small interleaving?
For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Let $\pi$ be a permutation of $[n]$. For simplicity, assume that $\pi$ is an $n$-cycle. ...
- 19.4k
3
votes
0
answers
141
views
Under what conditions on $A$ and $v$ is the size of the sumset $v \cdot A + A$ over $\mathbb{F}_p$ equal or close to $|A|^2$?
Let $p$ be a prime, let $A$ be a subset of $\mathbb{F}_p$, and let $v \in \mathbb{F}_p \setminus \{0\}$.
Under what conditions is $|v \cdot A + A|$ (that is, $|\{ va + b : a \in A,\ b \in A \}|$) ...
1
vote
1
answer
124
views
Finding $P$ points among $N$ to approximate a probability density function?
Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ ...
CommunityBot
- 1
0
votes
1
answer
237
views
Showing equality of Eberlein polynomials
I have thought about the following question a long time and still got no progress.
Currently I am writing my master thesis about association schemes in combinatorics and need an equality which seems ...
33
votes
1
answer
1k
views
What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?
It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:
$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$
$a$ is an ...
- 457
0
votes
1
answer
91
views
If the core of a graph is a forest, then it is Class 1
It is a standard result, due to Fournier, that if the core of a graph (the induced graph by the vertices having their degrees equal to maximum degree of the graph) is a forest (acyclic), then the ...
- 2,027
5
votes
1
answer
405
views
Iterated derivative and rectangular standard Young tableaux
We first make a few definitions, seemingly out of the blue (they are introduced/defined in this paper).
Let $F^0_{a}(z) = (1-z)^{-1}$ and define recursively
$$
F^{k+1}_{a}(z) = z^{a-1} \frac{d^a}{dz^...
- 436
1
vote
1
answer
97
views
Are non-trivial interval-isomorphic posets lattices?
We say that a partially ordered set $(P,\leq)$ is interval-isomorphic if for all $a<b \in P$ we have $P \cong [a,b]$, where $[a,b]=\{x\in P:a\leq x\leq b\}$.
Suppose $(P,\leq)$ is interval-...
- 44.7k
1
vote
1
answer
152
views
$q$-plane partitions & specialization & interlinks
MacMahon's enumeration of all plane partions (PP) inside an $n$-cube generalizes to
$${\tt PP_n}(q)=\prod_{i,j,k=1}^n\frac{1-q^{i+j+k-1}}{1-q^{i+j+k-2}}.$$
A $q$-analogue of symmetric plane partitions ...
CommunityBot
- 1
19
votes
3
answers
1k
views
The sum of integers being a bijection
What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map
\begin{eqnarray*}
P\times Q & \rightarrow & {\mathbb N} \\\\
(p,q) & \mapsto & p+q
\end{eqnarray*}
is a bijection ...
- 51.6k
7
votes
0
answers
176
views
Matrix of high rank mod $2$: must it have a large non-singular minor (with disjoint rows and columns)?
Let $A$ be a $2n$-by-$2n$ matrix with entries in
$\mathbb{Z}/2\mathbb{Z}$ such that, for every $2n$-by-$2n$ diagonal
matrix $D$ with entries in $\mathbb{Z}/2\mathbb{Z}$, the matrix $A+D$
has rank $\...
- 19.4k
5
votes
2
answers
391
views
What is this sequence counting?
While solving (a system of) a system of linear equations level-by-level recursively, I am finding some redundant equations for level $n\geq5$. The reason why the redundancies arise is because $P(n)\...
- 30.7k
27
votes
2
answers
2k
views
Combinatorics of K(Z,2)?
Anybody knows a semi-simplicial model for $K(Z,2)$ having finite number of simplexes in any dimension? With some regular description? I have heard about big activity on triangulating $CP^n$ but this ...
- 1,482
1
vote
0
answers
136
views
Strategy of Responder in Rényi Ulam Liar Games
I tried posting this in Math Stack Exchange but got no responses, so I figured I could try my luck here. My main concern is that I can't figure out how to get started on my "research" (bear with me, I'...
- 39k
16
votes
2
answers
517
views
Surprising appearances of Painlevé transcendents
What are some of your favorite examples of enumerative problems whose answer ended up being (related to) a solution to one of the Painlevé equations?
I have seen examples from enumeration of classes ...
- 401
13
votes
2
answers
633
views
A reformulation of Erdős conjecture on arithmetic progressions
Erdős conjecture on arithmetic progressions states that if $S$ is a set of positive integers such that $c(S):=\sum_{n \in S} \frac{1}{n} = \infty$ (large set), then $ \forall \ell \ge 3$ the set $S$ ...
28
votes
1
answer
2k
views
How can I improve my formal definitions?
I am a Software Architect and not very familiarized with standard notation in mathematics. Nonetheless, I would like to write a paper explaining a normalization of a computing model for expert systems....
CommunityBot
- 1
2
votes
0
answers
85
views
chromatic class of graphs of order $n$
Let $\mathcal{G}(n)$ be the isomorphism class of simple graphs of order $n$. We say two graphs in $\mathcal{G}(n)$ are chromatic equivalent if their chromatic polynomials have an equal linear ...
- 1,219
1
vote
1
answer
432
views
Quotient graph of a tree
We know that every graph is isomorphic to a subgraph of a complete graph. Similarly, can we say that every graph is isomorphic to a quotient graph of a tree?
- 12.6k
4
votes
4
answers
279
views
How many residues mod p do you need to take to ensure that you can always find some multiple that contains 3 elements within ϵ of each other
For $\epsilon<p$, let $N(\epsilon,p)$ be the smallest value of $n$ such that for any set $S \subset \mathbb Z_p$ of size $n$, there exists $\lambda\in \mathbb Z_p^{*}$, $\mu \in \mathbb Z_p$ s.t $\...
- 4,792
9
votes
5
answers
851
views
Sums of binomial coefficients weighted by incomplete gamma
I am interested in proving that
$$\sum_{k=0}^n\frac{k}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=1
$$
and
$$\sum_{k=0}^n\frac{k^2}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=2.
$$
I verified it numerically ...
0
votes
1
answer
53
views
Writing a set of all possible (symmetric) products condensely? [closed]
I have a set of elements $\{a_1, a_2, a_3...\}$ and $\{b_1, b_2, b_3...\}$ and I want to condensely formally write the set of all possible products of these elements, where the ordering does not ...
- 118k
3
votes
1
answer
106
views
Asymptotic estimate of the cardinality of $H_{2n}=\{\vec{a} \in [-N,N]^{2n}:\sum_{i=1}^{2n} a_i = 0\}$
Let's suppose $a_i \sim \mathcal{U}([-N,N])$ where $[-N,N] \subset \mathbb{Z}$. We may then define:
\begin{equation}
S_n = \sum_{i=1}^n a_i \tag{1}
\end{equation}
Now, in order to estimate $\lvert ...
- 3,827
2
votes
1
answer
106
views
Probability distributions with irregular behaviour
Might there be a probability distribution $\mathcal{D}$ such that if we sample $a_i \sim \mathcal{D}([-N,N])$ where $[-N,N] \subset \mathbb{Z}$ then if we define the asymptotic estimate $f$:
\begin{...
- 118k
0
votes
1
answer
131
views
Combining three matchings to form a maximal matching
Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite.
Now, is there a way to ...
- 2,027
3
votes
2
answers
222
views
Strong chromatic index of some cubic graphs
Edit 2019 June 26 New computer evidence forces us to revise our guesses relating strong chromatic index and girth
Edit 2019 June 25 Some mistakes have been corrected. Question 2 has changed.
...
- 1,018
8
votes
1
answer
226
views
Prominent examples of $q$-analogs without known cyclic sieving
The cyclic sieving phenomenon is nicely summarized in the following AMS Notices "What is...?" article: https://www.ams.org/notices/201402/rnoti-p169.pdf.
In that article, Reiner, Stanton, and White ...
- 15.6k
4
votes
1
answer
526
views
Geometric RSK correspondece and classical RSK correspondence
In the paper, geometric RSK correspondence is given by
$$
\left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \mapsto \left( \begin{matrix} \frac{bc}{b+c} & ab \\ ac & \frac{ad}{...
- 22.9k
35
votes
5
answers
4k
views
Cliques, Paley graphs and quadratic residues
A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...
- 4,792
4
votes
1
answer
166
views
Complementing the red and blue boolean cube?
Given a boolean $0/1$ cube in $n$ dimensions with $2^{n-1}$ red and $2^{n-1}$ blue points can we complement the cube (blue becomes red and vice versa) in $\operatorname{poly}(n)$ transformations?
...
- 43.7k
8
votes
2
answers
560
views
Pfaffian representation of the Fermat quintic
It is known (see for instance Beauville - Determinantal hypersurfaces) that a generic homogeneous polynomial in $5$ variables of degree $5$ with complex coefficients can be written as the Pfaffian of ...
- 7,200
12
votes
2
answers
962
views
Higman's lemma and a manuscript of Erdős and Rado
Motivated by a problem in factorization theory, I've recently proved the following:
Theorem. If $X$ is a non-empty finite alphabet and $\mathcal W$ an infinite subset of the free semigroup, $X^\ast$...
- 2,329
7
votes
1
answer
217
views
Partitions restricted to only certain summands
Here $n$ is a positive integer and $p(n)$ is the number of unrestricted partitions.
Can one always find a subset $s$, of $\{1,2,\ldots,n\}$ such that the number of partitions of $n$ with parts from ...
- 4,199