# 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.

7,207
questions

**1**

vote

**1**answer

53 views

### A different version of list coloring

Consider a non-regular bipartite graph $G$ . We consider list edge coloring the edges of the graph by giving lists of cardinality $max(deg(v_i),deg(v_j))+2$ for each edge $e=v_iv_j$ where $deg(v_i)$ ...

**1**

vote

**1**answer

60 views

### Reference request - parallel rectangles discrepancy theory

I've been reading about discrepancy theory and trying to understand some of the open problems in the field. Wikipedia has a list of some of the open problems, but the descriptions are terrible. In ...

**1**

vote

**1**answer

163 views

### Subset of $[\omega]^\omega$ that can be “colored” with $3$, but not $2$ colors

Let $[\omega]^\omega$ denote the set of infinite subsets of $\omega$.
Let $S\subseteq [\omega]^\omega$. We say that a map $c:\omega \to \{0,\ldots,n-1\}$ is a coloring for $S$ with $n$ colors if ...

**1**

vote

**2**answers

132 views

### Recurrence relation for the number of partitions of an integer 𝑛 with distinct summands

Let $Q(n)$ give the number of ways of writing the integer $n$ as a sum of positive integers without regard to order with the constraint that all integers in a given partition are distinct. Equation $(...

**0**

votes

**1**answer

57 views

### Ordered $m$-tuples with fixed number of changes

Given $1\leq k\leq m$, $2\leq d\leq c i\ln i$ and $2\leq i\leq c'\ln(mi\ln i)$ at some $c,c'>0$ how many sequences (lower and upper bounds) are of form $$z_1,\dots,z_m$$ on the condition that
$$0\...

**4**

votes

**1**answer

186 views

### On the sum $\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k}$

Let $n$ be a non-negative integer.
Does there always exist a polynomial $P_n(a,b)$ such that for all integers $a > b \geq n/2$ we have
$$
\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k} = \...

**2**

votes

**0**answers

33 views

### Complexity of computing the automorphism group of the subdivision of clique with leaves

Related to graph isomorphism.
Consider the graph transformation $G$ to $G'$.
Make a clique of $V(G)$ and subdivide each edge once, i.e.
replace edge $(u,v)$ with path $(u,S_{uv},v)$.
For all edges $(...

**5**

votes

**0**answers

159 views

### Cardinals realizable by the chromatic number of a regular hypergraph

For any set $X$ and cardinal $\kappa$, we denote by $[X]^\kappa$ the collection of subsets of $X$ having cardinality $\kappa$.
If $H=(V,E)$ is a hypergraph, and $\kappa$ is a cardinal, we say that a ...

**1**

vote

**0**answers

64 views

### Total Coloring of a graph with $\Delta\ge\frac{n}{2}$

Consider an even vertex transitive graph $G$, which is not complete, with order $n$ and degree $k$ greater than or equal to half the order. By Hajnal-Szemeredi theorem, we could partition the ...

**5**

votes

**0**answers

382 views

### How to compute the volume of a region transformed by a matrix?

This is a rewrite of the OP's question to emphasize what I think are the research level issues here.
Let $\mathscr{R}$ be a bounded convex body in $\mathbb{R}^n$ and let $H : \mathbb{R}^n \to \mathbb{...

**1**

vote

**1**answer

70 views

### What is the minimal possible size of a subset of this semigroup satisfying the following conditions?

Suppose $A$ is some set. Let's define a pair semigroup over $A$ as $P[A] = (A\times A \cup \{0\}, \circ)$, where the $\circ$ operation is defined by the following two identities:
$\forall a \in P[A]$ ...

**10**

votes

**2**answers

210 views

### The $r$-dimensional volume of the Minkowski sum of $n$ ($n\geq r$) line sets

Let $n$ line sets be $\mathcal{S}_i=\{a\mathbf{h}_i:0 \le a \le 1\}$, for $1 \le i \le n$, where $\{\mathbf{h}_1,\cdots,\mathbf{h}_n\}$ is a vector group of rank $r$ in the $r$-dimensional Euclidean ...

**6**

votes

**2**answers

303 views

### Division of space by hyper-planes

It is a well known and lovely result that the maximum number of regions that $\mathbb R^{k}$ (with $k$ positive) can be divided into by $n$ hyperplanes is given by
$$1+n+\binom{n}{2}+\cdots+\binom{n}{...

**3**

votes

**1**answer

78 views

### What number of colorings can guarantee that for every k-element subset there exists a coloring assigns different colors for elements from this subset?

Let $M(n, k)$ be a minimal number $m$ such that there exists set $C$ ($|C|=m$) of colorings of n-element set $[n]$ with $k$ colors such that for every $k$-element subset $K$ of $[n]$ there exists ...

**2**

votes

**1**answer

99 views

### Number of orthants intersected by a convex hull

I'm trying to figure out the following problem:
Let $x_1,\ldots,x_k\in\mathbb{R}^n$ be some points for some $k<n$. Let $\mbox{conv} (x_1,\ldots,x_k)$ be their convex hull. I'm looking for a tight (...

**9**

votes

**1**answer

93 views

### Does every $C_4$-free bipartite graph lies in some finite projective plane?

A projective plane $Π$ is a 3-tuple $(P,L,I)$ where $P$ and $L$ are sets, and $I$ is a relation between $P$ and $L$, such that:
For every two elements $p_1$, $p_2\in P$, there exists a unique ...

**30**

votes

**1**answer

1k views

### Updates to Stanley's 1999 survey of positivity problems in algebraic combinatorics?

[I am a co-moderator of the recently started Open Problems in Algebraic Combinatorics blog and as a result starting doing some searching for existing surveys of open problems in algebraic ...

**2**

votes

**0**answers

61 views

### Contractions of hyper-cubes and how many of them

Contraction here means edge contraction with loop and multiple edges removed. For instant, there are four contractions (up to isomorphism) of the square ($Q_2$), namely a i) a single vertex, ii) an ...

**2**

votes

**1**answer

199 views

### Triangling the triangle

Is it possible to tile an equilateral integer-sided triangle with smaller equilateral integer-sided triangles, with no congruent triangles touching? This has been answered in the negative for the case ...

**1**

vote

**1**answer

98 views

### A combinatorial identity on even spanning subgraphs in the Erdös-Renyi random graph with relations to the Ising model

Let $x \in \lbrack 0,1 \rbrack$. Then for any finite graph $G$ consider the Erdös-Renyi random graph where we independently keep each of the edges with probability $x$. Denote the corresponding ...

**5**

votes

**6**answers

433 views

### Important combinatorial and algebraic interpretations of the coefficients in the polynomial $[n]!_q = (1+q)(1+q+q^2) \ldots (1+q+\cdots + q^{n-1})$

What are some important combinatorial and algebraic interpretations of the coefficients in the polynomial
$$[n]!_q = (1+q)(1+q+q^2) \ldots (1+q+\cdots + q^{n-1})?$$
As motivation, I will give ...

**2**

votes

**2**answers

137 views

### Independence depth of linearly dependent random variables

Suppose, $\Xi$ is a collection of random variables. We call $\Xi$ $k$-independent, iff any $k$ distinct elements of $\Xi$ are mutually independent. For example, $2$-independence is pairwise ...

**3**

votes

**1**answer

195 views

### Algorithm to generate free unlabelled trees uniformly at random

I am writing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf. This paper defines the procedure ...

**4**

votes

**2**answers

202 views

### Population of P people, where each person knows K others, how many people mutually know each other

If you have a population of $P$ people, where each person knows $K$ others within the population (does not have to be mutual, i.e., if I know you, you don't necessarily know me), and $1<K<P$, ...

**0**

votes

**1**answer

98 views

### Coupling between two distributions

Consider $s = \Theta(n^{\delta})$ for a $\delta\in (0,1)$ and let $p\in (0,1)$ with $m = \lfloor pn\rfloor$. Consider the random variable $Y$ which chooses $m$ elements from $\{1,\ldots,n\}$ such that ...

**5**

votes

**1**answer

165 views

### Do 1-additive maps admit tensor products?

Let $\mathcal{F}$ be a set algebra (or a Boolean algebra). Following Kalton, let me call a function $f\colon \mathcal{F}\to \mathbb R$ $\delta$-additive ($\delta \geqslant 0$), whenever $f(\varnothing)...

**1**

vote

**1**answer

88 views

### Calculating the values of a generalization of binomials to permutations

let $$\Pi\binom{n}{k}:=\mathrm{card}\left( \left\lbrace \lbrace \Pi_1^n\,\cdots\,\Pi_k^n\rbrace\,|\,0\leq \pi_{r,c}\in\sum_{i=1}^k\Pi_i^n\ni\pi_{r,c}\leq 1\right\rbrace\right)$$ be the number of sets ...

**2**

votes

**0**answers

43 views

### Natural class of QF-2 quiver algebras giving a categorification of maps

For several combinatorial objects (for example Dyck paths, subsets, integer compositions...) there is some nice "categorification" of them via quivers. That is there is a bijection from those ...

**7**

votes

**2**answers

264 views

### Counting nilpotent self-maps of $\{1,\dots,n\}$ with image of a given cardinal

Let $\mathcal{C}_n$ be the monoid of self-maps $\alpha$ of $\{1\dots,n\}$ that are order-preserving ($\forall x,y$, $x\le y$ $\Rightarrow$ $\alpha(x)\le\alpha(y)$ and decreasing ($\forall x$, $\alpha(...

**11**

votes

**0**answers

277 views

### Arithmetic progressions in stopping time of Collatz sequences

Inspired by the question here, we did a few more simulations of numbers of some specific forms and noticed a pattern.
We consider the original $3n+1$ transform where we divide by $2$ if it's even and ...

**3**

votes

**2**answers

152 views

### On a certain proportion concerning sets and permutations

Let $X$ be a finite set and let $f$ and $g$ be permutations with $f\ne g\ne f^{-1}$.
Can you show that the proportion of subsets $S$ with $|S\cap f(S)|=|S\cap g(S) |$ is at most $3/4$?
In other words
...

**1**

vote

**1**answer

65 views

### Reduction graph to planar bounded treewidth graph

We got reduction graph to planar bounded treewidth graph,
but this is unlikely to be true.
Let $H$, the planarizing gadget, be planar graph with four
distinguished vertices $u,u',v,v'$ on the outer ...

**4**

votes

**1**answer

102 views

### Reference request: transition equations for double Schubert polynomials

For $w$ a permutation, the associated (ordinary) Schubert polynomial $\mathfrak{S}_w(\textbf{x})$ is a multivariate polynomial that represents for the cohomology class of the Schubert variety $X_w$ in ...

**3**

votes

**1**answer

191 views

### Is following function a metric on the set of isomorphism classes of graphs with countably many vertices?

Suppose $\Gamma_1(V_1, E_1)$ and $\Gamma_2(V_2, E_2)$ are simple graphs with countably many vertices. And suppose $A_1$ and $A_2$ are initially empty sets. Suppose two players play the following game: ...

**0**

votes

**0**answers

56 views

### The order of minor in the total graph of a graph

Does the total graph of a regular finite graph with maximum degree $\Delta$ have a $K_{\Delta+2}$ minor?
I think no. It has a clique of order $\Delta+1$. But, I dont think that deleting a few edges ...

**3**

votes

**0**answers

171 views

### Intuitive, elementary intros to Hopf algebras/monoids

Motivation:
I'm interested in understanding the role that noncrossing partitions play in Hopf algebras/monoids (HAs) as the components of the power series of the compositional inverse of formal ...

**0**

votes

**0**answers

43 views

### Reference Request - Enumerative Results on Submodular Set Functions

I have been wondering whether there are papers that deal with submodular set functions from an enumerative point of view, whether it be to determine or bound from above or below the number of ...

**0**

votes

**0**answers

71 views

### Counting multiples in short intervals

Has anyone seen a problem like this in the literature? There are likely more generalized versions in sieve theory, which I am willing to tackle, but I would prefer a more elementary approach if ...

**1**

vote

**0**answers

78 views

### How many residue classes mod $p$ does the image of a polynomial with integer coefficients occupy? (Status of a question of Chowla)

In his 1952 AMS Bulletin article "The Riemann zeta and allied functions" Chowla asks the following:
Given a polynomial $f$ with integer coefficients, how many residue classes mod $p$ does its image ...

**5**

votes

**1**answer

205 views

### Global dimension 2 Nakayama algebras , 321-avoiding permutations and Fibonacci combinatorics

A $n$-LNakayama algebra (for $n \geq 2$) is a list $[c_0,c_1,...,c_{n-1}]$ with $c_{n-1}=1$, $c_i \geq 2$ for $i \neq n-1$ and $c_i -1 \leq c_{i+1}$ for all $i$.
They are in bijection with Dyck paths, ...

**1**

vote

**1**answer

351 views

### How typical are integer isometries on a hypercube? Littlewood-Offord problem for Bernoulli Gram matrices

Let $m\geq 3$ be fixed and $n\to\infty$. Consider $v=(v_j)_{j\leq m}$ with $v_1,\ldots,v_m\in \{-1,+1\}^n$. Let:
$N_I(v)$ be the number of sequences $u_1,\ldots,u_m\in \{-1,+1\}^n$ isometric to $v$ ...

**2**

votes

**0**answers

95 views

### When an isometry is a hypercube symmetry?

Suppose that sequences $v_1,\ldots,v_m\in \{-1,+1\}^n$ and $u_1,\ldots,u_m\in \{-1,+1\}^n$ are isometric in $\mathbb{R}^n$, i.e. $u_j=Qv_j$ for some orthogonal matrix $Q$. What is the largest $m$ such ...

**1**

vote

**0**answers

79 views

### Bender-Knuth involution on $SSYT(\lambda, [n])$

Denote by $SSYT(\lambda, [n])$ the set of all semi-standard Young tableaux of shape lambda with entries in $[n]=\{1, \ldots, n\}$. Denote by $SSYT(\lambda, \infty)$ the set of all semi-standard Young ...

**-6**

votes

**1**answer

307 views

### Is Green-Tao's theorem a consequence of Van der Waerden theorem?

Wanting to learn a bit about Ramsey's theory, I read the corresponding article on Wikipedia and stumbled upon this:
"Le théorème de van der Waerden[2] : pour tous entiers c et n, il existe un entier[...

**7**

votes

**0**answers

201 views

### Corners theorem in finite fields

The corners theorem of Ajtai and Szemerédi states that if $A\subseteq[N]^2$ is corner-free, i.e. there are no $x,y,h\in\mathbb{N}$ with all of $(x,y),(x+h,y),(x,y+h)$ in $A$, then $|A|=o(N^2)$. The ...

**6**

votes

**0**answers

177 views

### Two conjectural series for $\pi$ involving the central trinomial coefficients

For each $n=0,1,2,\ldots$, the central trinomial coefficient $T_n$ is defined as the coefficient of $x^n$ in the expansion of $(x^2+x+1)^n$. It is easy to see that $T_n=\sum_{k=0}^{\lfloor n/2\rfloor}\...

**3**

votes

**5**answers

320 views

### Non-trivial alternating sums of binomial coefficients

Consider a binary vector $a_0, a_1,\,\dots\,, a_n$ and an equation
$$\sum_{i=0}^n a_i \cdot (-1)^i {n \choose i} = 0.$$
You can satisfy this trivially when
1) all $a_i$ are 0, or
2) all $a_i$ are ...

**10**

votes

**2**answers

439 views

### Does the basis graph of a matroid determine it?

Let $M$ be a matroid with set of basis $\mathcal{B}$. The basis graph of $M$ is a graph with set of vertices $\mathcal{B}$ and edges $(B,B')$ always that $B$ and $B'$ differ (as sets) by exactly one ...

**4**

votes

**0**answers

166 views

### A conjecture on the cardinality of minimal mediated sequences

For a sequence of integer numbers $A=\{0,q_1,\ldots,q_m,p\}$ (arranged from small to large), if every $q_i$ is an average of two distinct numbers in $A$, then we say $A$ is a mediated sequence.
...

**2**

votes

**1**answer

85 views

### weak piecewise syndetic property for positive upper banach density set

I wonder if a set of integers $A$ given by an increasing sequence of integers $A=(a_k)_k$ with positive upper density
$\limsup_n\frac{\sharp A\cap [0,n]}{n}>0$ satisfies the following property.
...