# 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

0
votes

0
answers

27
views

### Bound for a sequence of vertices in a graph

I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be a $k$-regular directed graph with $n$ vertices without parallel edges. For a vertex $v\in G$, let $e_v$ denote the union of $\...

3
votes

2
answers

226
views

### Automatically generating combinatorial conjectures

It very often happens that one reduces a problem to a bunch of combinatorial data, and need to sift through this data for patterns, which form conjectures on which to do "real" mathematics. ...

5
votes

0
answers

86
views

### Goldberg-Seymour conjecture

I am wondering whether the graph theory community regards the Goldberg-Seymour conjecture as settled. According to https://en.wikipedia.org/wiki/Goldberg%E2%80%93Seymour_conjecture, "In 2019, an ...

0
votes

0
answers

27
views

### k-sharp and less than sharp integers

A portion of my post absorbs Steiner triples (hence Kirkman Theorem; there are strong connections with the ECC and simple finite groups). Thus specialists may have their field day here (no, I am not a ...

1
vote

1
answer

50
views

### Uniform hypergraphs with small edge intersections and propery ${\bf B}$

We say that a hypergraph $H=(V,E)$ has property ${\bf B}$ if there is $S\subseteq V$ such that for all $e\in E$ with $|e|\geq 2$ we have $$(e\cap S) \neq \emptyset \neq (e\cap (V\setminus S)).$$
If $k\...

8
votes

2
answers

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

1
vote

0
answers

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

8
votes

2
answers

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

2
votes

1
answer

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

0
answers

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

6
votes

0
answers

79
views

### Partial order on graphs induced by homomorphism counts

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_{\...

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

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

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

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

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

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

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

-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:}$$
$...

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

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

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

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

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

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

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

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

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

-1
votes

0
answers

109
views

### Bounds on the number of partitions of n into exactly k distinct parts?

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

5
votes

1
answer

224
views

### Counting points above lines

Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\...

3
votes

0
answers

131
views

### When is a wonderful compactification a toric variety?

Given a (projective) hyperplane arrangement $\mathcal{A}$ in $\mathbb{C}^n$, in which we assume the intersection of all hyperplanes is $0$, and a building set $G$, De Concini and Procesi define the ...

4
votes

2
answers

208
views

### Is this a known symmetry of lattice paths?

I recently came across the fact that NE lattice paths from $(0,0)$ to $(m,n)$ in aggregate pass through each row and column an equal number of times (which also has a corresponding binomial identity); ...

0
votes

0
answers

19
views

### vertices with least distance to subset of other vertices - Undirected Graph

Given an undirected graph $G=(V,E)$ where $V=\{v_1,v_2,...,v_n\}$ denotes the vertices and $E=\{e_1,e_2,...,e_m\}$ denotes edges. Moreover, there exists a nonnegative weight associated with each edge.
...

4
votes

2
answers

290
views

### Divisibility of Stirling numbers

It is well known that if $p$ is prime, Stirling numbers of the first and second kind, $s_1(p,k)$ and $s_2(p,k)$, are divisible by $p$ if $1<k\le p-1$ (Lagrange ; easiest is working in $\mathbb F_p$ ...

5
votes

2
answers

542
views

### The relation $x \sim g x g$ in groups

While thinking about item (2) in Standard or good names for relations between maps, I thought I'd look at the relation $x \sim g x g$ in groups.
Going through all small groups of order at most 64, it ...