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
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 $\...
  • 123
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. ...
  • 259
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 ...
  • 17.9k
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 ...
  • 4,172
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 ...
  • 323
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 ...
  • 17.7k
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 ...
  • 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$ ...
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 $...
-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 ...
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)$ ...
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$? ...
  • 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\...
-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 $\...
  • 18.1k
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 ...
  • 388
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. ...
  • 1
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 ...
  • 5,193

1
2 3 4 5
191