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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
6answers
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
2answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
5answers
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
2answers
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
0answers
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
1answer
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.
...
