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