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,511
questions
4
votes
1
answer
201
views
Double cover the edges of a complete graph by smaller complete graphs
Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly ...
0
votes
0
answers
56
views
Pairs of permutations such that $p(n)<2^k$ iff $n<2^k$
Let $p(n)$ be an arbitrary permutation of natural numbers such that $p(n)<2^k$ iff $n<2^k$.
Let $q(n)$ be an inverse permutation of $p(n)$.
Let
$$
\ell(n)=\left\lfloor\log_2 n\right\rfloor
$$
...
1
vote
2
answers
233
views
Joint moments like $\tau(XYXYXY)$ in terms of individual moments of free variables $X,Y$
Terry Tao RMT book has the following formula for joint moment of freely independent random variables $X,Y$ in Section 2.5
$$\tau(XYXY)=\tau(X)^2\tau(Y^2)+\tau(X^2)\tau(Y)^2-\tau(X)^2\tau(Y)^2$$
...
3
votes
1
answer
184
views
Some questions about induced subgraphs of the directed hypercube graph
Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
5
votes
0
answers
77
views
Formula and smallest solution for the A260711
Let $a(n)$ be A260711 without initial $0$ (i.e., numbers of the form $x^2 - y^2$ with $x > y$ where $x$ and $y$ are odd, $x + y$ is a power of $2$).
The sequence begins with
$$
8, 16, 32, 48, 64, ...
4
votes
2
answers
270
views
Lower bounding a partition-related sum
We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\...
5
votes
0
answers
74
views
Subspaces of $\mathbb{F}_2^N$ containing many pairs of far apart vectors
Let $S$ be a subset of vectors in $\mathbb{F}_2^{3n}$ having Hamming weight $n$. Suppose that $S$ contains $m$ pairs of vectors having disjoint supports (that is, they are at Hamming distance $2n$ ...
4
votes
0
answers
186
views
Polynomials of growth for finite Heisenberg groups
Take a standard finite Heisenberg group with two standard generators and let's consider its growth polynomial - the polynomial which coefficients are equal to the sphere sizes.
For example for $H_3(Z/...
2
votes
2
answers
73
views
Reference request for a subfamily of regular graphs
[Repost of same question math stack exchange which got no answers]
I'm looking for literature on the following family of graphs:
Call a regular graph $G=(V,E)$ (of regularity degree $d$) nice if there ...
1
vote
1
answer
63
views
Multidimensional power series with coefficients equal to an order of stabilizer of a set of powers
I have encountered a necessity to work with a series of the following form.
There are $N$ variables $x_1,\ldots x_N$. It is convenient to introduce monomial symmetric polynomials $m_{\lambda}$. They ...
2
votes
2
answers
203
views
Factorizations of an $n$-cycle in $S_n$ into a product $xy$ where $|x| = 2, |y| = 3$
Let $S_n$ be the symmetric group on $n$ letters. When (and how) can an $n$-cycle in $S_n$ be factored into a product $xy$, where $x,y$ have orders 2,3 respectively?
More precisely, I'd like to ...
1
vote
0
answers
126
views
Exploring the Intersection of Expander Graphs, Number Theory, Representation Theory and Recent Computer Science Developments [closed]
I have a solid understanding of the basics of expander graphs and their properties and the recent development of High-Dimensional Expanders and their application to Random Walks, along with other ...
5
votes
0
answers
91
views
Generalized Puiseux series for diagonal reflections of the curves $y = \frac{x}{(1-ax)(1-bx)^m}$
Reflection of the curve $y = f_m(x) = \frac{x}{(1-ax)(1-bx)^m}$ through the diagonal line $y=x$ in the $xy$-plane can be regarded as local compositional inversion of the curve $y=f_m(x)$. ($x,y,a,b$ ...
4
votes
0
answers
141
views
Subdivision via poset maps and pullback
In the following, all posets and complexes are assumed to be finite.
For a poset $P$ denote by $|P|$ its geometric realization or nerve (i.e. forming the order complex and taking its geometric ...
3
votes
1
answer
670
views
Infinite dimensional lattice for integers and the Riemann hypothesis?
It is known that for each finite set of primes $p$ we have: $\log(p)$ are linear independent over the rational numbers.
We have $\log(ab) = \log(a)+\log(b)$ and $\log(n) = \sum_{p |n}v_p(n) \log(p)$.
...
2
votes
1
answer
240
views
The probability that iid draws from a mean zero random variable sum to zero
Suppose we have a probability distribution $p(\cdot)$ supported on the integers between $-m$ and $m$ for some positive integer $m$, with $\sum_k kp(k) = 0$. Suppose furthermore that all $p(k)$ are ...
4
votes
1
answer
331
views
Kuratowski's 14 theorem and universal algebra
For a tuple of functions $\overline{p}$ on a set $Y$, let $cl_{\overline{p}}$ be the associated closure operation: $cl_{\overline{p}}(Z)$ is the smallest subset of $Y$ containing $Z$ and closed under ...
2
votes
1
answer
165
views
Estimating ${\left(\sum_{i=j}^k {x_i}\right)^2} \times \left\lvert\sum_{i=j}^k {a_i}\right\rvert$
Given two sets; $X = \{x_i : x_i \geq 0; i \in [\sqrt{n}]\}$ and $A = \{a_i : |a_i| \leq 1; i \in [\sqrt{n}]\}$ of size $n^{\frac{1}{2}}$ each, with the following properties
\begin{equation}\label{...
4
votes
0
answers
135
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
0
votes
1
answer
162
views
Reflections on subspaces of $\text{codim} > 1$
Let $V$ be a real finite-dimensional vector space with inner product $\langle \cdot , \cdot \rangle$.
Let $x,y \in V$ be linearly independent. I was wondering how a reflection $s_{x,y}$ through the $\...
6
votes
2
answers
721
views
Prove positivity of a binomial sum
Some problems appear easy on the face of it, but perhaps they are not. Here is an instance of a certain calculation which is slightly reformulated from its original encounter in a current work. I have ...
1
vote
0
answers
61
views
On a numbers $k$ with specific $2$-adic valuation
Let $a(n)$ be A002326 (i.e., multiplicative order of $2 \operatorname{mod} 2n+1$).
Let $b(n)$ be A179382 (i.e., the smallest period of pseudo-arithmetic progression with initial term $1$ and ...
5
votes
3
answers
398
views
Applying $\sum_i \partial_{x_i}$, $\sum_i x_i \partial_{x_i}$ and $\sum_i x_i^2 \partial_{x_i}$ to Schur polynomials
The operators $L_k=\sum_i x_i^k\frac{\partial}{\partial x_i}$, with integer $k$, take symmetric polynomials into symmetric polynomials.
Is it known how to write the result of the application of $L_0$, ...
0
votes
0
answers
121
views
Optimal strategy of modified Mastermind game
The following game is a modified version of the popular game Mastermind described here in which you are only given information about the total correct guesses you have made, and nothing about how many ...
0
votes
0
answers
93
views
Formula for individual term of the Proth numbers
Let $a(n)$ be A080075 i.e. Proth numbers: of the form $k2^m + 1$ for $k$ odd, $m \geqslant 1$ and $2^m > k$.
The sequence begins with
$$
3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129
$$...
4
votes
1
answer
221
views
Permutation of a mixture of (anti)commuting variables and consistency issue regarding the sign
I asked a similar question in PhysicsSE but it seems more like a mathematical issue, so I post here in a more refined form.
I am not confident if the below description of the problem makes sense. ...
0
votes
0
answers
104
views
Using matrix tree theorem on enlarged graphs
The matrix tree theorem for weighted graphs
Seeing this question left me wondering, is it possible to modify the matrix so one can compute the following sum:
$$
P'(G) = \sum_{T\subseteq G}{m'(T)}
$$
...
2
votes
0
answers
113
views
Adding partitions of one but not the other kind
Say that two partitions $(P_i)_{i\in I}, (Q_j)_{j\in J}$ are isomorphic iff there is a bijection $f: I\rightarrow J$ such that $\vert P_i\vert=\vert Q_{f(i)}\vert$ for all $i\in I$. (Note that in the ...
2
votes
0
answers
69
views
Possible subsequence of the A110978
Let $a(n)$ be A110978 i.e. odd integers that are nonprime, such that there exist two factors of each number that when multiplied together in binary base, do not ever require the use of a "carry&...
4
votes
2
answers
294
views
Number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$
I was wondering about sets that do not contain any $3$-term AP, and came to know that the official name of such a set is Salem–Spencer set. I was considering the question of counting the number of ...
0
votes
1
answer
118
views
The generating series of the weighted species of fixpoints
I am wondering if the series
$$\sum_{n=0}^\infty \left(\sum_{k=0}^n \frac{D_{n-k}}{k!(n-k)!}t^k\right)X^n$$
where $D_m$ is the number of derangements of $m$ letters, admits a representation in closed ...
3
votes
0
answers
239
views
On thickness of binary polynomials
OEIS A169945 introduces the concept of thickness of a polynomial as the magnitude of the largest coefficient in the expansion of the square of the polynomial. Considering the $2^{n+1}$ polynomials $p(...
2
votes
1
answer
95
views
Exhaustive list of small graphs for which $\frac{\alpha(G)\omega(G)}{n}$ is small?
I am looking for a list of small graphs (say on less than 10 vertices) for which the parameter $p(G) = \frac{\alpha(G) \omega(G)}{n}$ is small. Here $\alpha(G)$ and $\omega(G)$ is the size of the ...
9
votes
1
answer
505
views
Shortest almost trivial element of free group [duplicate]
Let $F_n$ be the free group with $n$ generators $\gamma_1,\dots,\gamma_n$.
Consider the homomorphisms $h_i\colon F_n\to F_{n-1}$ defined by adding the relation $\gamma_i=1$ in $F_n$.
What is the ...
2
votes
0
answers
102
views
Proof that a pandiagonal Latin square of order $n$ exists iff $n$ is not a multiple of $2$ or $3$?
A pandiagonal Latin square of order $n$ is an assignment of the numbers $\{0,\ldots,n-1\}$ to the cells of an $n \times n$ grid such that no row, column, or diagonal of any length contains the same ...
0
votes
0
answers
69
views
Graphs where any cycles are adjacent
Graphs with minimum degree three that any two cycles have common vertex, have been characterized by Lovász. I see this result from the Plumer article (On the cyclic connectivity of planar graphs (...
8
votes
0
answers
148
views
Inversions for parity preserving presentations
I've gotten stuck on a slightly random combinatorial question, and I'm doing a bit of a shot in the dark here to see if someone else has thoughts about it. I'm interested in studying a permutation of ...
5
votes
1
answer
139
views
Given a 3-connected graph $G$, is there an edge $e$ so that both $G-e$ and $G/e$ are still 3-connected?
Let $G$ be a 3-connected (simple) graph other than $K_4$. In Diestel's "Graph Theory" Section 3.2 we find
Lemma 3.2.2. There is an edge $e$ so that $G\mathbin{\dot-}e$ is still 3-connected (...
1
vote
1
answer
204
views
Sums of products over restricted set compositions
For any two nonconstant functions $f,g$ on the positive integers, e.g., polynomials, first note that the product of the following evaluation binomials can be expanded as
$$
\prod_{k=1}^n (f(k)+g(k)) = ...
3
votes
1
answer
201
views
Partition numbers and Gaussian binomial coefficient
Let $a(n)$ be A000041 i.e. the number of partitions of $n$ (the partition numbers).
Let $T(n, k)$ be A083906. Here
$$
T(n, k) = [q^k]\sum\limits_{m=0}^{n} \binom{n}{m}_q
$$
where $\binom{n}{m}_q$ ...
2
votes
1
answer
214
views
Name for generalization of trees to digraphs
One definition of tree in graph theory could be as follows:
A tree is a(n undirected) graph for which there is a unique (undirected) path between any pair of vertices.
This suggest a possible ...
1
vote
0
answers
81
views
Interpreting multiple property tests at different values of $\epsilon,\delta$ [closed]
I am doing some work in the area of Property Testing, as in Goldreich, Goldwasser, and Ron (2008) or the textbook Introduction to Property Testing (Goldreich). In this framework, I run a test to see ...
2
votes
0
answers
62
views
cocycle datum for principal $G$-bundle over base space Delta set
Let $X$ be topological realization of a (finite)
Delta set, $G$ a finite group and $p: P \to X$ a
principal $G$-bundle.
Let's recall the standard fact that more generally any
numerable principal G-...
5
votes
1
answer
266
views
Expected number of coin flips before you see a $k$-term arithmetic progression of heads
Let $\{X_i\}_{i \in \mathbb Z_+} $ be independent fair coin flips. Write $S := \{i \in \mathbb Z_+\, | \, X_i \text{ is heads}\}$, and define, for an integer $k \geq 3$,
$$Y := \inf \{n \in \mathbb N \...
1
vote
2
answers
202
views
Relationship between fixed points and inversions in permutations
Inversions in a permutation $Y$ are defined as pairs where $Y_a < Y_b$ but $a > b$, while fixed points in $Y$ are defined as elements where $Y_a = a$ (i.e., 1-cycles). Let $S_\alpha$ be the set ...
2
votes
0
answers
99
views
The fluctuations of a random path
Suppose I have a $n \times n$ square grid and for each square, I assign 1 with probability $\frac{1}{2}$ and 0 with probability $\frac{1}{2}$. On the boundary, I put 1s on the lower half and 0s on the ...
15
votes
1
answer
866
views
Scrambling a “Connections” grid
Given a 4-by-4 array of distinct words, is it possible to scramble the array in four different ways in such a fashion that each possible word-pair appears adjacently in one of the five arrays (the ...
1
vote
0
answers
115
views
On a Fibonacci and binary
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
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let
$$
T(n, k) = \left\lfloor\frac{n}{2^k}\...
-8
votes
2
answers
367
views
Infinite set intersection with arithmetic progressions
Let $\mathcal{A}$ be the set of all arithmetic progressions in $\mathbb{N}$ i.e
\begin{align*}
\mathcal{A} = \{a + b\mathbb{N} : a,b\in\mathbb{N}, b\neq 0\}.
\end{align*}
Does there exist a set $X \...
0
votes
0
answers
55
views
How many rigid 4-regular graphs are there?
I am interested in any formulas for the number of globally rigid 4-regular graphs, or Laman graphs of degree at most 4, on $n$ vertices. The bound can be for graphs with labeled or unlabeled vertices.