Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

9
votes
0answers
180 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}, ...
8
votes
0answers
175 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
1answer
175 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 ...
3
votes
1answer
146 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
0answers
87 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 ...
5
votes
1answer
250 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 ...
3
votes
0answers
74 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
0answers
99 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
1answer
192 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 ...
3
votes
2answers
92 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 ...
12
votes
1answer
737 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 ...
4
votes
1answer
120 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 ...
4
votes
1answer
268 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
0answers
68 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 ...
3
votes
1answer
342 views

Is there a name for this fast growing functions?

Define $F(n,i)=\prod_{j=1}^nj^{j^i}$. $F(n,0)=n!$. $F(n,1)$ is hyperfactorial. Is there a term for $F(n,i)$? How fast do these grow? Is growth rate $2^{\frac{c_in^{i+1}\log_2n}{i+1}}$ with some ...
12
votes
0answers
140 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 ...
11
votes
0answers
152 views

Is combinatorial automorphism of symmetric convex polytope always odd?

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 ...
0
votes
0answers
107 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) ...
2
votes
1answer
106 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 ...
12
votes
1answer
157 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 ...
1
vote
0answers
79 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, ...
2
votes
1answer
136 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 ...
4
votes
1answer
151 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
0answers
81 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
1answer
341 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
0answers
159 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 ...
5
votes
1answer
131 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
2answers
347 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 ...
13
votes
2answers
312 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 ...
0
votes
1answer
76 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 ...
3
votes
1answer
78 views

Probabilistic many-to-one matching

Let $p<1$ be a constant. Consider two sets $A,B$ with $n$ and $nf(n)$ vertices, respectively, where $f(n)$ is an integer. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears ...
2
votes
2answers
128 views

Matching with probabilistic edges

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...
1
vote
0answers
99 views

Lower bound on the value $\textbf{1}^Tx$ such as $Ax\geq b$

The problem may be formulated as follows: We are given a set of $m$ positive numbers $\{b_1,...,b_m\}$ and a set of $n$ positive numbers $\{v_1,...,v_n\}$. We have $v_j\leq K$, $j=1,...,n$, for a ...
5
votes
4answers
192 views

Selecting subsets with size $\frac{n}{2}$ covering every pair of the elements

Given a set $S$ of $n$ elements. Let $T$ be the set of all subsets of $S$, with size $\frac{n}{2}$ ($n$ is even). We want to select a subset $T'$ of $T$, with the property that for any pair of the ...
4
votes
2answers
170 views

Volume of the convex hull of the set of all graphic sequences of a given length

Consider the set of all graphic sequences with $n$ elements as a subset of $\mathbb{R}^{n}$, namely let $$D(n)=\{(d_{1},\dots,d_{n})\in\mathbb{Z}_{+}^{n}:d_{1}\geq\dots\geq d_{n},\ ...
7
votes
1answer
265 views

Linear relations among permutation matrices

Given a permutation $\sigma\in S_n$, let $P_\sigma$ denote the corresponding $n\times n$ permutation matrix. It is easy to see that for $n=3$, there is only one linear relation up to scaling given by ...
1
vote
1answer
94 views

Eulerian graphs with prescribed number of edges

Under what conditions there exists an $n$-vertex eulerian graph with $m$ edges for $1\leq m\leq\frac{n(n-1)}{2}$?
8
votes
1answer
173 views

Expansion in strongly regular graphs

Have you seen the following statement proven anywhere? Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ ...
8
votes
0answers
161 views

Partition regularity in the squares

A linear equation $c_1x_1 + \cdots + c_sx_s = 0$ is partition regular if for every partition of the natural numbers into colour classes $A_1, \ldots, A_r$, there is a solution to the equation in which ...
11
votes
1answer
285 views

Travelling salesman: can the furthest-neighbour algorithm beat the nearest-neighbour?

This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route ...
9
votes
3answers
256 views

Labeling edges of an icosahedron with sum constraints

The question is inspired by this previous MO question. There it was shown that it's possible to label the edges of a cube by the numbers $\{1,2,\ldots,6,8,9, \ldots, 13\}$ in such a way that: Three ...
3
votes
1answer
372 views

Game on a string

I am interested if one can design an efficient (polynomial) algorithm telling whether the first player has a winning strategy for a game described below. The board is a string consisting of only ...
6
votes
0answers
96 views

Inequality among domino tilings of large triomino shapes

Inspired by this question, which asks for what shape maximizes the number of domino tilings, I want to ask the following seemingly simpler question, which I have been thinking about for a while: ...
15
votes
5answers
587 views

The smallest disk containing all sides of an $n$-gon

Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect. What is the ...
14
votes
2answers
564 views

A conjecture about $\lfloor n!\cdot q/e\rfloor-\,!n\cdot q$

I was thinking about this question asked at Math.SE, when I came up with the following conjecture. For every $q\in\mathbb Q$ consider a sequence $s_n^{(q)}$ (terms within the sequence are indexed by ...
3
votes
1answer
102 views

Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible

A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. ...
0
votes
1answer
107 views

An asymptotic intersection problem

Given a set of $n\in\Bbb N$ integers $\mathcal S$ and $\mathsf s,\mathsf t\in\big(0,1\big)$, suppose we choose two sets: $$\mathcal S_{\mathsf{1}}\subseteq\mathcal S$$ $$\mathcal ...
0
votes
0answers
39 views

Is the laplacian spectral radius of a directed grpah a non-decreasing function?

Given a directed graph G and its respective laplacian matrix $L = D-A$ where $A$ is the adjacency matrix ($A_{ij}=1$ if there is a link from $j$ to $i$ and $A_{ij}=0$ otherwise) and D is the diagonal ...
5
votes
1answer
222 views

$(n-2)$-blocking sets in $AG(n,2)$

Let's define $k$-blocking set in affine space $AG(n,q)$ a set that meets every coset (translate of subspace) of dimension $k$. I have seen a lot work related to minimal $(n-1)$-blockings set. ...
4
votes
2answers
310 views

Can you simplify (or approximate) $\sum_{n=0}^{N-1}\begin{pmatrix}N-1\\n\end{pmatrix}\frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}$?

Let $\begin{pmatrix}x\\y\end{pmatrix}$ be the binomial coefficient. I am trying to get a better understanding of the sum \begin{equation} ...