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

9,530 questions
Filter by
Sorted by
Tagged with
27 views

276 views

### Proofs of the Frobenius characteristic map

Let $\mathfrak{S}_n$ be the symmetric group on $n$ letters, $\mathsf{Rep}(\mathfrak{S}_n)$ be the abelian category of finite dimensional complex representations of $\mathfrak{S}_n$. A classical result ...
• 323
1 vote
88 views

### Independence number of a grid like graph

Given natural numbers $n$ and $k$, let $G_{n,k}$ denote the simple graph whose vertex set is $\{1,2,\ldots ,n\}$ and there is an edge between $i$ and $j$ when $|i-j|\leq k$. I am interested in the ...
• 1,205
720 views

### Minimum number of pairings that make all quadruples

Let $A$ be a set of cardinality $4n$. We define a pairing in $A$ to be a partition of $A$ into sets of cardinality $2$. What is the minimum number of pairings in $A$ such that every subset of $A$ of ...
60 views

### Strongly regular graphs with certain parameters

Does there exist a sequence of strongly regular graphs with parameters $(n,d,\lambda,\mu)$ (so every pair of adjacent vertices have $\lambda$ common neighbours, and every pair of non-adjacent ones ...
1 vote
38 views

### Chromatic number of 2-graph vs hypergraph of point-line incidences

Define the chromatic number $\chi(H)$ of a (hyper)graph $H$ as the smallest $k$ such that its vertices can be $k$-colored such that no (hyper)edge is monochromatic. Given a finite set of points $P$ in ...
• 17.7k
79 views

For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\... • 1,952 9 votes 1 answer 356 views ### Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence? I know the following problem is famous: For a given degree sequence$L$that is graphic, find an (efficient) algorithm to generate all of the nonisomorphic realizations of$L$. This algorithm is ... • 855 1 vote 1 answer 57 views ### Maximal number of$k$-subsets of an$n$-set such that any two subsets meet in at most$(k-2)$points I am interested in the maximal number of$k$-subsets of an$n$-set such that any two subsets meet in at most$(k-2)$points. I found that for$k=3$and$k=4$, we have the sequences http://oeis.org/... 2 votes 0 answers 146 views ### Approximate versions of Segre's Theorem Consider projective$2$-space over a finite field of odd prime characteristic$p$. We say a set of points,$A$, in this space is an arc if any line meets it in at most two points. We say that an arc ... • 11.4k 2 votes 0 answers 60 views ### Is the face poset of a compact intersection of cylinders and half-spaces shellable? Let the$n$-disk$D^n$be stratified hemispherically (so there are two 0-dimensional strata at the poles, two 1-dimensional strata for the prime meridian and the international date line, two 2-... • 53.6k 3 votes 1 answer 182 views ### Ramsey-like property with order condition I wonder if there are regular cardinals$\lambda$and$\kappa$such that$\kappa < \lambda \leq 2^\kappa$and such that, consistently, the following holds: Let$c: [\lambda]^2 \to \kappa$be such ... 3 votes 0 answers 55 views ### Research on lower bounds of sphericity of a graph I am looking for references that address lower bounds on the "sphericity" of a graph. For a finite point set in Euclidean$n$-space, if we connect each pair of points by a line segment ... 5 votes 1 answer 331 views ### Six people standing on earth Consider 6 people$p_i$,$i=1,\dots 6$, standing on a sphere$S^2$. We label the positions of these people by$p_i$again. Suppose no pair of these points$p_i$are antipodal. At each point$p_i$... • 311 2 votes 0 answers 40 views +100 ### What is the analogue of a Block-Cut Tree Decomposition in directed graphs? Let$G$be a connected, undirected graph. We define a block$B$to be a maximal$2$-connected induced subgraph in$G$. It is easy to see that any two distinct blocks are either disjoint or overlap at ... • 300 5 votes 0 answers 130 views ### What is this Ramsey problem Given positive integers,$n,m,r$, define$R((n,m);r)$to be the least$N$such that for any$r$-coloring$C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with$n$vertices and$m$... • 1,921 0 votes 1 answer 124 views ### Identity involving Stirling number of the second kind I'm looking for a citable reference for the following identity involving the Stirling numbers of the second kind$S(n, k)$stated in Equation (27): For$n \geq 2$, $$\sum_{m=1}^n S(n, m) (-1)^m (m-1)!... 1 vote 1 answer 116 views ### Largest part and length of a partition in play If \lambda=(\lambda_1\geq\lambda_2\geq\dots\geq\lambda_k)\vdash n is an integer partition of n then \lambda_1 is its largest part and k is its length, \ell(\lambda). Define the statistic ... • 39.3k -1 votes 0 answers 57 views ### What is the probability that after throwing n balls into k bins uniformly we will have a different number of balls in each bin? I want to know if it is possible to compute the following problem (Or at least give an estimation on the lower bound) : Given n balls and k bins where n>>k, we throw n balls into those ... 3 votes 1 answer 79 views ### Probabilistic method Alon and Spencer Azuma's inequality Theorem 7.5.2 states: Let v_1, \dots, v_n be vectors with \|v_i\| \leq 1. Let \epsilon_1, \dots, \epsilon_n \in \{-1, 1\} be independent with uniform probability and let X=\|\epsilon_1 v_1 + \... 1 vote 0 answers 112 views ### Closed-form solution of a particular linear program (Note: I asked a similar question at math.stackexchange but the present one is more precise.) I have a linear program of the form:$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$... • 402 1 vote 1 answer 105 views ### Name for the cell poset of the staircase partition Is there a standard name for the cell poset of the staircase partition (n,n-1,\dots,1), where, in English notation, a cell covers the adjacent cell in the row above and in the column to the right? ... • 5,193 1 vote 0 answers 114 views ### A possible cryptomorphism between closure operators and a suitable subclass of simplicial complexes Good evening to everybody. I'm writing a paper on the combinatorial properties of simplicial complexes and closure operators, but at a certain point I found a problem which seems hard to be solved. ... 1 vote 1 answer 60 views ### Can \omega be parity-separated with finitely many bijections? We say that a bijection \varphi:\omega\to\omega parity-separates a\neq b\in \omega if \varphi(a) is even and \varphi(b) is odd, or vice versa. Is there a finite set \Phi of bijections such ... 0 votes 1 answer 105 views ### How many combinations of magic square on a white Rubik's cube? A magic square is one in which the sum of the numbers in each row, column, and both main diagonals is the same. The numbers in the magic square can only be 1 to 9. a 3x3 magic square example: There ... 8 votes 1 answer 200 views ### For which n does a y-formed n-polyomino tile a n \times n \times n-cube? I got from my children as a gift a puzzle consisting of 25 y-shaped 5-polyominoes that form a 5 \times 5 \times 5-cube (see picture). I'm wondering for which n does a y-formed n-polyomino tile a ... • 3,916 2 votes 1 answer 116 views ### How many ways are there to pick n points on the finite affine plane (\Bbb F_q)^2 such that no three are collinear? How many ways are there to pick n points on the finite affine plane (\Bbb F_q)^2 such that no three are collinear? For example, how many ways can we pick 5 points on \Bbb F_{32}\times\Bbb F_{32}... 0 votes 0 answers 39 views ### Comparing spectral radius of two graphs using the entry of Perron vector Suppose we have a graph G. Let A be the adjacency matrix of G and x be the corresponding Perron vector. Let x = (x_1,x_2,\cdots,x_n)^t, where x_i corresponds to the vertex i \in V(G). We ... • 199 0 votes 0 answers 38 views ### Number of balanced-parentheses sequences on 2n bits as n grows large [migrated] The motivation to consider the sequences below comes from an efficient way to represent trees on n nodes using 2n bits. Let n\in\mathbb{N} be a positive integer. Let us call s\in\{0,1\}^{2n} a ... 0 votes 0 answers 165 views ### Covering discrete triangle with generalized knight jumps Consider for n\in\mathbb{N}, n\geq 6 the discrete triangle \nabla=\{(i,j)\in \{1,\ldots,n-1\}^2 \mid j\leq n-i\}. This is basically the lower "half" of a chess board if you cut it along ... -1 votes 0 answers 20 views ### Gaining points for posting [migrated] how do I earn 50 points to comment if I am not allowed to comment or post? So my problem is as described as far you can see. 1 vote 0 answers 79 views ### Subsequence such that c(a(n))=2^n Let a(n) be A060831, i.e., \sum\limits_{k=1}^{n}\operatorname{number of odd divisors of} k. Let$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$Let$$b(n,k)=2b(n,k-1)-2^{k-1}, b(n,0)=n$$Let c(n) ... • 1,887 30 votes 8 answers 2k views ### Examples of errors in computational combinatorics results I would like to collect examples of errors in published numerical results in computational combinatorics: where a result (typically a counting of some objects, or an extremal quantity within some ... 0 votes 0 answers 61 views ### Maximal number of times distance 1 can occur among n points in the plane [duplicate] For n\in\mathbb N, let f(n) be the maximal number of times distance 1 can occur among n points in the plane:$$ f(n) = \max_{ \{ x_1,\ldots,x_n \} \subset \mathbb R^2} \# \big \{ i<j : \| ... • 41.2k 5 votes 1 answer 156 views ### What is the name for an integer partition with bounded multiplicities? Is there a standard name for integer partitions$\lambda \in (\mathbb{Z}_{\geq 0})^n$,$\lambda_i \geq \lambda_{i+1}$, with multiplicities at most$k$, i.e.$\lambda_i > \lambda_{i+k}$for all$i$? ... • 1,452 3 votes 0 answers 145 views ### Cohomology rings of complex varieties and combinatorics It is a classical fact that the cohomology ring (with complex coefficients) of a complex smooth projective manifold is a bigraded algebra satisfying (1) Poincare duality; (2) hard Lefschetz theorem; (... • 19.7k 0 votes 0 answers 45 views ### How to compute the multiplicity of a strongly convex, rational, polyhedral cone$ \sigma $? In David Cox, John Little and Hal Schenck's book Toric Varieties page 302, Chapter 6, Section 4, Proposition 6.4.4, the authors state the following proposition. If$ \Sigma $is a simplicial fan of ... • 483 8 votes 1 answer 446 views ### Scheduling "parent talks" at school Real life motivation. In my younger son's class, there are$18$students. His teacher provided$18$time slots for the parents of each child to have a 30-minute conversation of their kid's progress in ... 1 vote 0 answers 68 views ### Shuffling$\omega$fairly for a fixed partition Let${\frak P}\subseteq {\cal P}(\omega)$be a partition such that every block$B\in {\frak P}$contains at least two integers. Is there a countable set${\cal F}$of bijections$\varphi:\omega\to\...
This is more of a follow-up on What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts? Rob's proof As Rob proved in his answer, I want some clarification ...