Skip to main content
MathOverflow

Questions tagged [co.combinatorics]

Ask Question

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

11,584 questions
Newest Active Bountied Unanswered
11 votes
0 answers
232 views

In a $p\times p$ grid with $p$ prime, trivial polyomino tilings: $1\times p$ rows, $p\times1$ columns, $p\times p$ square. Question. Do there exist non-trivial connected polyominoes (size $k$ where $k$...
Son Hoang's user avatar
  • 121
7 votes
1 answer
461 views

(I have asked the same question on Mathematics Stack Exchange. But, while I got some interesting comments, I did not get an answer to the question, which is about bibliography.) I am looking for ...
kehagiat's user avatar
  • 155
1 vote
0 answers
81 views

$\newcommand{\one}{f}$ Let $C_p$ be the cyclic group of prime order $p$. For an integer $m\ge 0$ and a subset $A\subset C_p$, denote by $\one$ the indicator function of $A$ and define $$ L_m(g):=\sum_{...
Seva's user avatar
  • 23.5k
3 votes
0 answers
91 views

First some abstract definition that generalise some notions from Rowmotion and Echelonmotion: Definition 1: Let $M$ be an $n \times n$ lower triangular integer matrix with entries in $\{0,1\}$ and ...
Mare's user avatar
  • 28.2k
2 votes
2 answers
149 views

Let $X_1,\dots,X_n$ random variables taking values $-1,1$. Since $X_i^2=1$ we have $$ k(X_1,X_1)\,=\,E[X_1^2]-E[X_1]^2\,=\,1-k(X_1)^2$$ and more in general one can express the cumulant where every ...
tituf's user avatar
  • 405
1 vote
0 answers
67 views

Background and motivation. Let $G$ be a tree, let $M$ be a matching of $G$, and let $k = 1,\dots,\nu(G)$, where $\nu(G)$ denotes the matching number of $G$, i.e. the maximum cardinality of a set of ...
Chess's user avatar
  • 1,404
6 votes
0 answers
213 views

I first noticed a interesting phenomenon. Let $R$ be an integral domain, $I$ and $J$ two ideals of $R$. Then we have two exact sequences: $0\to (I+J)/J\to R/J\to R/(I+J)\to 0$ $0\to I\cap J/IJ\to I/IJ\...
Censi LI's user avatar
  • 473
5 votes
0 answers
104 views

Consider graph which is skeleton of the permutohedron (Cayley graph for neigbour transpositions of $S_n$) or - second option - Johnson graph (which is Schreier coset graph for $S_n/(S_k \times S_{n-k})...
Alexander Chervov's user avatar
  • 26.4k
6 votes
0 answers
113 views

Consider a convex polytope in dimension $d$ whose vertices are $n$ binary vectors $V \in \{0,1\}^{d}$ (that is each entry in the vector is 0 or 1). What is an upper bound on the number of facets of ...
user32079877's user avatar
  • 61
18 votes
6 answers
1k views

I have a fixed $n \times n$ matrix $M$ whose entries are all either $0$ or $1$. I want to compute the product $Mv$ for various vectors $v \in \mathbb{R}^n$ (or over other fields/rings and abstract ...
max_herman's user avatar
  • 380
2 votes
1 answer
250 views

Given a simple graph $G=(V,E)$ define a convex polytope $$P_G:=\{x\in\mathbb{R}_{\ge 0}^V:x_S\le|\partial_GS|\text{ for all }S\subset V\text{ such that }|S|\le\frac{1}{2}|V|\}$$ (here $x_S:=\sum\...
jinni's user avatar
  • 121
3 votes
0 answers
103 views

The following arose in a project about design enumeration. Let $V=\{1,2,\ldots,v\}$. For any $r$, $\binom Vr$ denotes set of all $r$-subsets of $V$. There is a real number $\theta_e$ for each $e\in\...
Brendan McKay's user avatar
  • 38.4k
2 votes
2 answers
155 views

By a polyhedral complex, I mean a collection of polytopes $\mathscr{P}$ in $\mathbb{R}^n$ such that if $P\in \mathscr{P}$ then all of the faces of $P$ are in $\mathscr{P}$, and if $P,Q \in \mathscr{P}...
cacha's user avatar
  • 759
4 votes
1 answer
306 views

Let $f(n,m)$ be a function such that $$ f(n,m) = mf(n-1,m) + 1, \\ f(0,m) = 1. $$ $T(n,m)$ be a coefficients such that $$ T(n,m) = n! \sum\limits_{k=1}^{n} \frac{m^{k-1} n^{n-k-1}}{(n-k)!}. $$ See ...
Notamathematician's user avatar
  • 347
0 votes
0 answers
23 views

Let 𝐹 be a family of subsets of [ 𝑛 ] such that for any two distinct sets 𝐴 , 𝐵 ∈ 𝐹 , we have ∣ 𝐴 ∩ 𝐵 ∣ ≤ 𝑘 . For fixed 𝑘 , what is known about the maximum possible size of such a family as 𝑛...
LLMATHS's user avatar
  • 63

15 30 50 per page
1
2 3 4 5
…
773