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 $\...
- 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\...
- 41.4k
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 ...
- 1,205
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 ...
- 844
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 ...
- 408
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_{\...
- 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/...
- 63
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 ...
- 183
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)!...
- 58
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 ...
- 41.4k
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}...
- 748
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 ...
- 41.4k
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 ...
- 63
-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 ...
- 41.4k
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\...
- 41.4k
-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); ...
- 43
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$ ...
- 3,490
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