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.

Filter by
Sorted by
Tagged with
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 ...
Wallace Rin's user avatar
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 $$ ...
Notamathematician's user avatar
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$$ ...
Yaroslav Bulatov's user avatar
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 ...
Agile_Eagle's user avatar
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, ...
Notamathematician's user avatar
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(\...
MikeG's user avatar
  • 665
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$ ...
Kevin's user avatar
  • 530
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/...
Mikhail Evseev's user avatar
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 ...
jojo's user avatar
  • 21
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 ...
V. Asnin's user avatar
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 ...
stupid_question_bot's user avatar
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 ...
total dependent random choice's user avatar
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$ ...
Tom Copeland's user avatar
  • 9,937
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 ...
KoopaTroopa's user avatar
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)$. ...
mathoverflowUser's user avatar
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 ...
James Propp's user avatar
  • 19.4k
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 ...
Noah Schweber's user avatar
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{...
Krish's user avatar
  • 23
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 ...
Mohammad Al-Turkistany's user avatar
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 $\...
Bipolar Minds's user avatar
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 ...
T. Amdeberhan's user avatar
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 ...
Notamathematician's user avatar
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$, ...
thedude's user avatar
  • 1,417
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 ...
wjmccann's user avatar
  • 315
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 $$...
Notamathematician's user avatar
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. ...
Isaac's user avatar
  • 2,727
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)} $$ ...
juan manuel rodriguez's user avatar
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 ...
Noah Schweber's user avatar
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&...
Notamathematician's user avatar
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 ...
Sayan Dutta's user avatar
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 ...
fosco's user avatar
  • 13k
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(...
Sayan Dutta's user avatar
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 ...
Agile_Eagle's user avatar
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 ...
Anton Petrunin's user avatar
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 ...
Milo B's user avatar
  • 21
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 (...
L.C. Zhang's user avatar
  • 1,605
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 ...
Ben Webster's user avatar
  • 43.9k
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 (...
M. Winter's user avatar
  • 12.5k
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)) = ...
Javier Álvarez's user avatar
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$ ...
Notamathematician's user avatar
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Paul's user avatar
  • 171
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-...
JackYo's user avatar
  • 541
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 \...
Nate River's user avatar
  • 4,822
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 ...
virtuolie's user avatar
  • 173
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 ...
Frederik Ravn Klausen's user avatar
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 ...
James Propp's user avatar
  • 19.4k
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}\...
Notamathematician's user avatar
-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 \...
Family Values's user avatar
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.
domotorp's user avatar
  • 18.3k