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.
10,516
questions
3
votes
1
answer
309
views
Problem related to Frobenius coin problem
Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ good if,
for any $r,s,u,...
5
votes
1
answer
2k
views
A generalized theorem of Hall's marriage theorem
We all know Hall's marriage theorem as following:
A bipartite graph $G$ with bipartition $\{ A,B \}$ contains a matching of $A$ if and only if $|N(S)|\geq |S|$ for all $S\subseteq A$.
And I am ...
0
votes
1
answer
220
views
Maximal induced cycles on $n$-clique graphs
For any set $X$ we set $[X]^2 = \big\{\{a,b\}: a, b\in X\text{ and } a\neq b\big\}$.
We say a simple undirected graph $G=(V,E)$ is an $n$-clique graph if there are $S_1,\ldots,S_n\subseteq V$ such ...
1
vote
0
answers
116
views
Consecutive integers divisible by consecutive small numbers
Given $n$, what is the largest set of consecutive integers in $[n,2n]$ can we have so that each integer is divisible by a distinct element from $[\log n,2\log n]$ (no partiular order)? So apriori I am ...
5
votes
1
answer
442
views
Asymptotic enumeration of magic squares
An order-$n$ magic square is an $n \times n$ matrix over the numbers $\{1, ... ,n^2\}$, each appearing exactly once, whose row and column sums are all equal. Sometimes the sums of the diagonals are ...
6
votes
0
answers
116
views
Chromatic numbers for coloring-constrained graphs
I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...
3
votes
1
answer
281
views
Can a length n distributive lattice be embedded into Bn?
Let $\mathcal{L}$ be a finite distributive lattice, then it is known that it can be embedded into a finite boolean lattice (see theorem 8.5. p91 in this note).
Let $n$ be the length of $\mathcal{...
1
vote
0
answers
70
views
Planar triangulations for which all distinct 4-colorings consist of exactly 6 Kempe chains
Are there any internally 6-connected planar triangulations other than the icosahedron all of whose distinct 4-colorings consist of exactly 6 Kempe chains, one for each of the 6 color-pairs?
Addendum: ...
4
votes
1
answer
159
views
Show existence maximal clique of order $s$ in an multigraph where each vertex is colored with a set of colors
You are given a multigraph $G$ with $n$ vertices as follows:
$V := (v_1, v_2, \dots ,v_n)$
$C := \{c_1, c_2, \dots\}$, be an infinite set of colors.
$f: V \rightarrow \mathbb{P}_{\le m}(C) $, a ...
1
vote
0
answers
39
views
Colorful Neighborhoods
Given:
$G:=\{V= \{v_1,\ ...\ v_n\},E\subset V\times V\}, n<\infty$, a symmetric complete, simple graph
$w:=\ \ E \ni e_{ij}\mapsto \mathbb{R}^+$, a weight function for the edges of $G$
$K:=\{c_1,\ ....
1
vote
1
answer
344
views
The number of good partitions
This was also posted in stackexchange. However, I have no idea how difficult it is. All hints or references are appreciated!
Consider a set $S$ of $n$ red balls and $m$ blue balls. It is well known ...
2
votes
1
answer
154
views
Partitioning the vertex set of a planar bipartite graph into a tree and an independent set
Let $G = (V, E)$ be a planar bipartite graph such that there is a partition $(V1, V2)$ of $V$ where $V1$ induces a tree and $V2$ induces an independent set.
Is there a characterization of such ...
3
votes
1
answer
182
views
Exact statistics in the Frobenius coin problem
The Frobenius coin problem guarantees that if $(a,b)=1$, then
$$ax+by$$ does not represent exactly $\frac{(a-1)(b-1)}2$ numbers all below $g(a,b)=ab-a-b$ if $x,y\geq0$ holds.
Assume $m\in[0,ab-a-b]$ ...
4
votes
0
answers
104
views
Weighted maximal number of disjoint singly-generated ideals in the divisibility poset for $\{1,2,\ldots,n\}$
In the mathoverflow question here the asymptotic growth of antichains in the divisibility poset ${\cal P}_n$ of the set of natural numbers $\{1,\ldots,n\}$ is considered. I have a somewhat dual ...
33
votes
1
answer
1k
views
What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?
It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:
$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$
$a$ is an ...
8
votes
1
answer
174
views
Equalizing Geometric means of Graph Cycles
Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...
2
votes
3
answers
858
views
The number of submodules of $\mathbb{Z}_q^n$
Observe $\mathbb{Z}_q^n = \mathbb{Z}_q \times \cdots \times\mathbb{Z}_q$ as a module over $\mathbb{Z}_q\equiv\mathbb{Z}/q\mathbb{Z}$, for general $q$.
I am interested in the following questions:
How ...
9
votes
1
answer
207
views
A Graph-Theory Related Question
Let $n$ be a positive integer and partition a grid of $4n$ by $4n$ unit squares into $4n^2$ squares of sidelength $2$. (The squares with sidelength $2$ have all of their sides on the gridlines of the $...
4
votes
2
answers
352
views
A property of uncountable almost disjoint families
Let $\mathcal{A}$ be an uncountable almost disjoint family (not necessarily maximal) of infinite subsets of $\mathbb{N}$. Denote by $\mathcal{A}_{\subseteq}=\{ B\subseteq\mathbb{N}:|B|=\omega \wedge \...
9
votes
0
answers
289
views
Weighted sum of the Simsun (Andre) permutations
Let $ c_{n,k} $ be the Simsun permutations$^1$ defined by the following relations: $\displaystyle c_{n,0} = 1, \hspace{0.1cm} (n \ge 1);$
$$ c_{n,k} = (k+1) c_{n-1,k} +(n-2k+1) c_{n-1,k-1}, \hspace{0....
9
votes
0
answers
294
views
An abstract zero-sum problem
I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ...
6
votes
1
answer
506
views
Eigenvalue inequality for regular graphs
I recently proved an inequality relating some of the eigenvalues of a regular graph with each other, and I was wondering if it is already known. I was unable to find it online, and a quick skim ...
7
votes
1
answer
944
views
Algorithm to count the number of perfect matchings in non planar graph
I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...
2
votes
0
answers
137
views
Number of multipartite partitions with odd components
For some positive integer $r$, by an $r$-vector I will mean an $r$-tuple $(a_1,a_2,\dots,a_r)$ with $a_1,\dots,a_r$ nonnegative integers not all zero, and I will call it odd if $a_1,\dots,a_r$ are all ...
8
votes
1
answer
1k
views
A remarkable sum over partitions
While studying some seemingly unrelated topological questions, I have experimentally discovered what appears (to me) to be a remarkable sum over partitions. I was wondering if anyone knows how to ...
4
votes
0
answers
187
views
Fibers of torus equivariant moment maps
Given a closed (possibly singular) projective variety $V$ with a symplectic structure and a torus action, there is a moment map
$\mu: V \rightarrow Lie(T)^*$. Note that the dimension of $T$ could be ...
2
votes
0
answers
114
views
Zero-one links: how many, and how to produce?
For $m \geq 1$, define a link to be a zero-one word $w=d_0d_1 \ldots d_k$, where $d_0=0$ and $k=2^m-1$ , such that the words
$$ w_0=0^{m-1}d_0, w_1=w_0d_1, w_2=w_1d_2, \ldots, w_k = w_{k-1}d_k $$
...
7
votes
1
answer
222
views
Unusual isoperimetry and maximizing the measure of unions of translates of a set
Let me state a standard result first. Let a $A\subset \mathbb{R}^d$ be a set of fixed volume. Define $A_t$ to be the set of all points at distance at most $t$ from $A$. Then the volume of $A_t$ is ...
4
votes
2
answers
308
views
What are bounds for the number of monotone functions $M:P\rightarrow T$ where $P$ is a finite poset and $T$ is a finite totally ordered set?
For the case where $P=\{0,1\}^n$ and $T=\{0,1\}$ the number of such functions is called the $n$-th Dedekind number and I discovered that there is large literature on determining bounds for these ...
16
votes
1
answer
3k
views
Where did the term "additive energy" originate?
A fundamental object in modern additive combinatorics and harmonic analysis is additive energy. Given a subset $A$ of (say) an abelian group $G$ the additive energy of $A$ is defined to be the ...
5
votes
1
answer
304
views
Coefficients of Ehrhart polynomials, in the binomial-coefficient basis
Let $P$ be the convex hull of a finite set of points in $\mathbb Z^d$, and $p(n) = \#\{nP \cap \mathbb Z^d\}$ be its Ehrhart polynomial, which is also the Hilbert polynomial of the corresponding ...
3
votes
1
answer
463
views
Generating function for number of different tessellation checkered rectangle
Let $R_n$ be checkered rectangle sized $n \times 4, n \ge 1$.
Let $a_n$ be number of different $R_n$ tiling with rectangles sized $1 \times 3$.
$\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $...
5
votes
0
answers
135
views
What is the maximal convex hull in $\mathbb R^3$ of a tree with fixed total length?
Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the ...
5
votes
1
answer
710
views
Is there a name for this fast growing function?
Define $F(n,i)=\prod_{j=1}^nj^{j^i}$. $F(n,0)=n!$ is just the standard factorial, whereas $F(n,1)$ is the so-called hyperfactorial.
Is there a term for $F(n,i)$?
How fast do these grow?
Is the ...
11
votes
0
answers
234
views
Coefficients of universal Schubert polynomials
Let $e_i^j$ be the elementary symmetric polynomial in $x_1,x_2,\ldots,x_j$. Then the ordinary Schubert polynomial has an expansion of the form
$$S_u(x)=\sum_{i_1,i_2,\ldots,i_n}{a^{i_1,i_2,\ldots,i_n}...
14
votes
0
answers
253
views
Is combinatorial automorphism of symmetric convex polytope always antipodal?
The question is formulated in the title. More precisely, if $P$ is an origin-symmetric convex polytope in $\mathbb{R}^d$, and $f$ is a bijective transform of the set of the vertices of $P$, which ...
1
vote
0
answers
123
views
The smallest disk containing all cirular arcs
In a comment to my recent question about covering segments by a disk, Gerhard Paseman has suggested a generalisation: replacing the segments of the original $n$-gon by a simple closed (say, convex) ...
4
votes
1
answer
158
views
Conceptual explanation for multiplicativity of theta generalization of extreme characters of U(infty)
A character of $U(\infty)$ is a continuous, positive definite class function $\chi: U(\infty) \longrightarrow \mathbb{C}$, which is normalized by $\chi(e) = 1$. Observe that the set of characters of $...
13
votes
1
answer
252
views
Graphs with a coloring that majorizes all other colorings
By a coloring of a graph $G = (V,E)$ I mean a map $\kappa:V\to\mathbb{N}$ such that $\kappa(u)\ne \kappa(v)$ whenever $u$ and $v$ are adjacent. (Sometimes this is called a proper coloring but I am ...
3
votes
1
answer
738
views
A version of the Weak Regularity Lemma
Definitions: Given a graph $G$ and $S$, $T \subseteq V(G)$, let $e_G(S, T)$ denote the number of edges of $G$ with one endpoint in $S$ and the other in $T$ and let
$$d_G(S, T) := \frac{e_G(S, T)}{\...
2
votes
1
answer
454
views
Alternating sign binomial identity [closed]
I recently noticed that for a triple of integers $k \geq 2$, $k \geq m \geq t \geq 1$, the following identity seems to hold
$\sum_{j=0}^{m-t} (-1)^{m-t-j}{k \choose j}{m-1-j \choose t-1}={k-t \choose ...
10
votes
1
answer
722
views
Demazure product in Coxeter and Artin groups
As a follow-up of Allen's question Coxeter exchanges in non-reduced words, I wonder whether it is known that the Demazure product is well-defined in Artin groups. This is:
Let $(W,S)$ be a Coxeter ...
0
votes
0
answers
1k
views
Partial sum of binomial coefficients
For some integer $z \ge 2$ and large integer $n$ and $ t=\lceil \log n\rceil $, what is an approximate value for the following partial binomial sum?
$$ \sum_{i=0}^{n-t} \binom{n}{i}z^i .$$
Another ...
6
votes
1
answer
380
views
A property of the derivatives of a function
Suppose that $f,g_1,g_2,\dots$ are functions from $\mathbb{R}$ to $\mathbb{R}$ such that $f'=f\,g_1$ and $g'_j=g_j^2-g_j g_{j+1}$. Here and in what follows, $j$ is any natural number. Then, by ...
12
votes
0
answers
215
views
Do the Laver tables converge to the Sierpinski triangle with a line segment sticking out in the hyperspace topology?
Let $(\{1,...,2^{n}\},*_{n})$ denote the $n$-th Laver table.
Let
$$C_{n}=\{(\frac{x}{2^{n}},\frac{x*_{n}y}{2^{n}})|x,y\in\{1,2,3,...,2^{n}\}\}$$
for all $n\in\mathbb{N}$.
Then since $C_{n}$ is a ...
7
votes
1
answer
199
views
Are the primary parallelotopes classified? (equivalently, Voronoi cells of lattices)
A primary parallelohedron is a polyhedron that can fill space with infinite translated copies.
It is known (e.g., Coxeter, H. S. M. Regular Polytopes, 3rd ed. New York: Dover, pp. 29-30, 1973; or, ...
11
votes
2
answers
685
views
Pursuit-Evasion type game on graph ("Flyswatter game")
An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...
15
votes
2
answers
497
views
Coxeter exchanges in non-reduced words
Let $Q$ be a word in the generators of some Coxeter group, and consider a subword $R$ (not necessarily reduced, though I might want $Q$ to be).
Define the greedy or Demazure product of $R$ as follows: ...
1
vote
2
answers
191
views
The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)
In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$).
This is what I observed from some books (e.g. "Combinatorial ...