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.
9,274
questions
0
votes
0
answers
69
views
Optimal covering trails in 3 and 4 dimensions
A couple of years ago, I constructively solved (inside the $AABB$ $[0,3]$ X $[0,3]$ X ... X $[0,3]$) the $k$-dimensional generalization of the infamous Nine-Dot Problem by S. Loyd (see Cyclopedia of ...
- 1
0
votes
0
answers
75
views
Inverse limit in category of graphs
Let $... \leftarrow G_i \leftarrow G_{i+1} \leftarrow ...$ be an inverse system of graphs (which might not be locally finite), morphisms are symplicial maps (we allow collapsing of edges to vertices)....
- 1
2
votes
0
answers
81
views
A minimal size of a set of tuples for an upper bound of a distance between any pair of elements
Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
- 695
5
votes
1
answer
610
views
Much weaker condition for Kakeya sets over finite fields
What is the minimum size of a subset $S \subseteq \mathbb{F}_p^n$ such that for all directions $a \in \mathbb{F}_p^n$, there is a line in direction $a$ that intersects $S$ in at least $C$ points?
If $...
- 101
7
votes
0
answers
135
views
Number of tautologies of a given size?
Fix some complete set of $L$ logical connectives such as $\{ \wedge, \neg \}, \{\Rightarrow, \neg \}, \{\ \vee, \wedge, \neg \}, \{ \uparrow\}, \{\wedge, \vee, \neg, \Rightarrow \}$ - I'll assume all ...
- 593
1
vote
0
answers
89
views
Are there standard short notations for ascending and descending cyclic permutations?
In a paper I am currently writing I use cyclic permutations of the form
$$
(k,k+1,\dots,\ell)
$$
and
$$
(\ell,\ell-1,\dots,k)
$$
of consecutive elements quite a lot (I added the commas to avoid ...
- 5,661
15
votes
1
answer
375
views
Make $n$ numbers equal using pairwise averages
Given $n$ rational numbers. Every time you can delete $2$ numbers, and add 2 numbers which are equal to $\frac{a+b}{2}$ (assume the number you delete is $a$ and $b$). How to judge whether it is ...
- 151
22
votes
1
answer
3k
views
Can an odd number of marbles jump to infinity?
Loosely inspired by the game Abalone, I've encountered the following simple problem I cannot solve.
Suppose that we are given a finite set of marbles on an infinite chessboard.
One move consists of ...
- 17.2k
2
votes
0
answers
82
views
Reference request on Plancherel measure for partitions whose parts differing by more than $1$
Given an (unrestricted) integer partition $\lambda$ of $n$, let $f_{\lambda}$ denote the number of standard Young tableaux (SYT) of shape the Young diagram $Y(\lambda)$ of $\lambda$. Then,
$$\sum_{\...
- 38.3k
4
votes
1
answer
180
views
A combinatorial question about certain sequences
Consider the sequence defined by the following algorithm:
Make a stack of tickets numbered from 1 to $n,n>1 \in N$ and arranged in reverse order with the ticket numbered 1 at the bottom and that ...
- 552
0
votes
0
answers
64
views
Expectation of edge weights on the complete graph, Part 2
This question concerns the same basic set-up as my previous question: Expectation of edge weights on the complete graph
In that question an answer was given which shows that the expected value is as ...
- 21.4k
3
votes
1
answer
148
views
Total number of plane partitions for $4$ or more dimensions
According to MacMahon formula the total number $P_3(r, s, t)$ of plane partitions that fit in the $r \times s \times t$ box $\mathcal{B}(r,s,t)$ is equal to the following product formula:
$$
P_3(r,s,t)...
- 348
1
vote
1
answer
135
views
Expectation of edge weights on the complete graph
Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random ...
- 21.4k
7
votes
1
answer
237
views
Harmonic flow on the Young lattice
Let me begin with some preliminary concepts: A positive real-valued function $\varphi: P \rightarrow \Bbb{R}_{>0}$ on a locally finite, ranked poset $(P, \trianglelefteq)$ is harmonic if
$\varphi(\...
- 1,565
3
votes
1
answer
142
views
Existence of wild regular abstract polytopes
Is it possible for an edge to connect two non-adjacent vertices of a polygonal face in a regular abstract polytope? Here “adjacent” means that the two vertices are connected by an edge that is a facet ...
- 1,604
0
votes
0
answers
53
views
Determining the total number of nonzero expansion terms in a (0,1)-matrix
Let $A=(a_{ij})_{n\times n}$ be a $(0,1)$-matrix such that it contains equal number of $1$s in each row and column. Is there any general method to count the total number of the nonzero terms $\prod_{i=...
- 133
1
vote
0
answers
87
views
$r(M)$-subsets of a 3-connected matroid $M$
It is proved in Lowrance, Oxley, Semple, and Welsh - On properties of almost all matroids that almost all matroids are 3-connected asymptotically. Also, it is conjectured that almost all matroids are ...
- 359
4
votes
1
answer
240
views
Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?
Update: In light of Fedor Petrov's answer, I added an additional requirement that all strings in $A$ and $B$ have Hamming weight exactly $n/2$, which hopefully makes the question more interesting.
...
- 43
2
votes
0
answers
47
views
Does periodic pattern arise in syndetic pattern
We wonder for two "large" sets $I,J\subseteq \omega$, if $(J-J)\cap I=\emptyset$, then it must be due to certain periodic pattern.
We say $I\subseteq \omega$ is $t$-syndetic iff for every $n\...
- 909
0
votes
0
answers
56
views
Shattering of a set of binary classifiers
Let $S$ be a set, and let $\mathcal{F}_{S}=\{f:S\to\{-1,+1\}\}$ be a set of different label assignments. Show that $\mathcal{F}_{S}$ shatters at least $|\mathcal{F}_{S}|$ subsets of $S$.
Here is what ...
- 113
4
votes
1
answer
274
views
The fraction $\frac{g_{\mu}}{f_{\lambda}}$ is an integer
Let $\lambda=(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_{\ell(\lambda)}>0)$ be an integer partition of $n\in\mathbb{N}$; i.e., $\lambda_1+\cdots+\lambda_{\ell(\lambda)}=n$.
One may now associate $...
- 38.3k
1
vote
0
answers
79
views
cone structure of complement of hyperplanes
I want to know if in $\mathbb{R}^{m+3}$ we consider the following hyperplanes:
\begin{cases}
(1-g)y-\sum_{i\in I}x_i=0, & \text{if $I\subset\{1,\cdots,m+2\}$},|I|=g\\
gy-\sum_{i\in I}x_i+\...
- 451
1
vote
1
answer
99
views
Is there an efficient generalized algorithm to generate a set of binary words satisfying a particular cross-correlation property?
In this question, the term “word” implies a binary word, i.e. a sequence of bits.
Let $W(w)$ denote the number of non-zero bits in a word $w$.
Assuming that $l \geq 2$ is even, an $l$-bit word $w$ is ...
- 695
33
votes
1
answer
2k
views
Is there a configuration of 5 points on the plane where any two can be covered by an axis aligned rectangle?
I'm trying to figure out the question in the title for a project that I'm working on.
My goal is to find a configuration of five integer points on the plane, where we can overlap any pair of them ...
- 403
3
votes
1
answer
110
views
Cycle counts in Ewens measure as $\theta$ diverges
For $w$ a permutation, let $c(w)$ denote the total number of cycles and $c_i(w)$ denote the number of $i$-cycles.
The Ewens measure is a one-parameter probability distribution on permutations where ...
- 1,721
0
votes
0
answers
109
views
combinatorial way to count representatives of conjugacy class of elements of ord 5
I am trying to find a representative of each conjugacy class of order 5 elements in PGL$_6$($\mathbb C$).
Let $r$ in $\mathbb C$ such that $r^5 = 1$ and [ ] denote modular the center of GL$_6(\mathbb ...
- 41
24
votes
3
answers
666
views
What is the smallest size of a shape in which all fixed $n$-polyominos can fit?
Let $n$ be an integer and consider all fixed $n$-polyominos, i.e., without rotation or reflection. I am interested in finding a shape in which all polyominos can embed. (It is OK if multiple ...
- 409
5
votes
1
answer
303
views
Counting monomials and the Catalan numbers
Given a multi-variable polynomial $F$, denote the number of monomials by $N(F)$. Take for instance, \begin{align*}N(x(x+y)+(x+y)^2-(x-y)^2)=N(x^2+5xy)&=2 \qquad \text{and} \\
N((x+z)(x+y)^2)=N(x^3 ...
- 38.3k
7
votes
0
answers
170
views
Scalar products on symmetric functions behaving like the Macdonald scalar product
The Macdonald symmetric functions (or Macdonald polynomials)
$P_\lambda(x)$ are orthogonal with respect to the Macdonald scalar
product
$$ \langle p_\lambda,p_\mu\rangle =
\delta_{\lambda\mu}z_\...
- 43.8k
16
votes
0
answers
302
views
Row of the character table of symmetric group with most negative entries
The row of the character table of $S_n$ corresponding to the trivial representation has all entries positive, and by orthogonality clearly it is the only one like this.
Is it true that for $n\gg 0$, ...
- 18.9k
1
vote
0
answers
40
views
Minimum number of elements to fill constrained sets
I'm a computer scientist who encountered an interesting class of set theory problems in the wild, and was wondering if there are canonical tools to handle or reason about them. If these problems are ...
2
votes
0
answers
286
views
Distribution of $\frac{(\sin(n))^2}{2^n}$ in dyadic intervals?
Good morning all,
I was wondering what kind of methods could help in order to tackle the following problem :
Define the set $A = \left\{ \frac{(\sin(n))^2}{2^n}\right\}$ for $n$ integer. So A is a ...
- 21
11
votes
1
answer
438
views
Equality of two $q$-series. Proof?
Recall the notation $(z;q)_n=(1-z)(1-zq)(1-zq^2)\cdots(1-zq^{n-1})$.
My earlier MO question did not find enough interest or yield an answer. Perhaps the modulo $2$ part might have thrown people off. ...
- 38.3k
11
votes
1
answer
219
views
Infinite vertex-transitive graph where every automorphism has a fixed vertex
This is a follow-up to the question Connected vertex-transitive graph with the fixed-point property. In particular, it is based on a comment by user bof.
Let $G = (V,E)$ be a graph with $V$ infinite. ...
- 18.9k
0
votes
0
answers
72
views
Addition theorem for Schur function in multivariable
Working with the following problem Expansion in Schur function of negative binomial exponent
I need to find the expansion of
$$ s_{\lambda}(x_1 + y , x_2 +y, \ldots, x_n +y)$$
in terms of schur ...
- 631
3
votes
1
answer
226
views
Congruence modulo 2 for q-series
This quest arose from certain calculations with integer partitions (having distinct parts) and the corresponding values of their Dyson ranks.
I would like to ask:
QUESTION. Is this congruence true ...
- 38.3k
9
votes
3
answers
309
views
Is it possible that every edge in a 1-planar drawing with minimum number of crossings is crossed?
A graph is 1-planar is it has drawing in the plane so that each edge is crossed at most once. Here we also assume the drawing satisfies (1) no edge is self-crossed; (2) no two adjacent edges are ...
- 463
1
vote
0
answers
185
views
(Lower) homotopy groups from triangulations
Both cohomology and homotopy groups capture global topological information of a manifold $X$. It is interesting to ask if they can be computed from local data. A triangulation $T$ natural presentation ...
- 4,005
15
votes
4
answers
903
views
Possible values of the determinant for matrices with elements $\{1, 0, -1\}$
For matrices with elements $\{-1, 1\}$ it is known from here that the possible absolute values of determinants of $n \times n$, $n \leq 6$ matrices with entries $\{-1, 1\}$ are as follows:
...
- 341
1
vote
0
answers
65
views
Partitioning of a set family that avoids small intersections
Let $\mathcal{F}$ be the family of all $k$-element subsets of $[n]$. What is the smallest $\ell$ such that we can partition $\mathcal{F}$ into $\ell$ families $F_1,\dots,F_\ell$ with the property that ...
0
votes
0
answers
34
views
Problem about providing a good estimator in 2SLS
I am now studying the 2-stages least-squares method and have been curious about the following circumstances.
Suppose that I have $Y_i = X^{T}_{i}β +e_{i}$ with $\mathbb{E}(e_{i}X_{i}) ̸\ne 0$, that ...
- 9
2
votes
0
answers
94
views
Fusion rules for the Lie algebra $\frak{so}_{2n+1}$
For the Lie algebra $\mathfrak{so}_{2n+1}$ where can I find a description of the fusion rules of it fundamental representations? In more detail: For $\pi_i$ and $\pi_j$ two fundamental weights of $\...
- 393
0
votes
0
answers
102
views
Maximal $m \times 9n$ blocks of coloured beads, Part 1
Let $n$ be a large positive integer. We consider $m \times 9n$ arrays of beads satisfying the following conditions:
Each bead is coloured one of three colours, say black, white, and green;
The number ...
- 21.4k
1
vote
1
answer
116
views
The cap set tensor in Lovett (2019)
I hope this is appropriate for the site. I am reading the paper "The analytic rank of a tensor" [S. Lovett, Discrete Analysis (2019), #7, 10 pp.] and am a bit confused in one of the ...
- 581
6
votes
0
answers
207
views
Recursive runoff voting schemes
Background: I will below describe a generalization of the following voting systems (what is meant by “voting system” will be defined formally below) which are occasionally used in the real world:
“...
- 22.1k
1
vote
0
answers
54
views
Is there any previous study on the relationship between convexity and the order of points in the general position?
Let's assume $V =(v_1,v_2,v_3,… ,v_n)$ is a set points in a general-position. For each point $v_i$, let's list the points in the order we encounter as we rotate around a certain direction (say ...
- 11
2
votes
1
answer
199
views
The combinatorics of $(f \partial)^n$ in the noncommutative setting?
This is a noncommutative version of these three previous questions:
differential operator power coefficients
Сlosed formula for $(g\partial)^n$
A Leibniz-like formula for $(f(x) \frac{d}{dx})^n f(x)$?
...
- 5,661
15
votes
5
answers
1k
views
Longest increasing subsequence as measure of randomness
Although I am by no means an applied mathematician, I like to occasionally explain applications of the math I teach to real world problems. Right now I am teaching some students about longest ...
- 18.9k
1
vote
0
answers
130
views
Discretizing a differential operator which is a function of the derivative operator
Assume that $p(x)$ and $f(x)$ are sufficiently smooth functions and $D\equiv \frac{d}{dx}$. My question is concerned with the discretization of $p(x+D)f(x)$.
As an example, let $p(x)=x^{2}+2x$. Then ...
- 49
22
votes
2
answers
6k
views
$\mathbf{P} = \mathbf{NP}$, what's the problem?
Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$.
We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)...
- 3,011