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
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 ...
user avatar
  • 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)....
user avatar
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)....
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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_{\...
user avatar
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 ...
user avatar
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 ...
user avatar
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)...
user avatar
  • 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 ...
user avatar
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(\...
user avatar
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 ...
user avatar
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=...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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+\...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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_\...
user avatar
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$, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $\...
user avatar
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 ...
user avatar
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 ...
user avatar
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: “...
user avatar
  • 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 ...
user avatar
  • 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)$? ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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)...
user avatar
  • 3,011