Tagged Questions

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)

1
vote
0answers
26 views

Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally: Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...
1
vote
2answers
73 views

Koebe–Andreev–Thurston theorem - where can I find a proof?

Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
11
votes
3answers
268 views

Conjecture regarding closest point inside a discrete ball to a line

I'm a PhD student in image processing, where I've stumbled into a problem that seems to be essentially number theory. I've hunted around online and while I've found many results on similar problems, ...
-1
votes
0answers
51 views

A combinatorial and number theoretical problem [on hold]

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1. For example,N=10 and the positive integers are ...
2
votes
1answer
90 views

A perfect $(n,k)$ shuffle function

Suppose you have a deck of $n$ cards; e.g., $n{=}12$: $$ (1,2,3,4,5,6,7,8,9,10,11,12) \;. $$ Cut the deck into $k$ equal-sized pieces, where $k|n$; e.g., for $k{=}4$, the $12$ cards are partitioned ...
3
votes
0answers
66 views

Partitions with each part dividing the original number

I have a question on partitions that I have not seen being discussed. It deals with those related to divisors. My definition of partitions I am working with is as follow: a sequence of weakly ...
-1
votes
0answers
32 views

How can i simplify the sum of modified partial bell polynomials [on hold]

I am trying to prove my conjecture that uses partial bell polynomials as well as modified partial bell polynomials. Putting these bell polynomials into a workable form is a huge problem for me. The ...
0
votes
0answers
54 views

Reduction argument from a general vertex set V(G) to a prime power in Prof. Keevash's proof on the Existence of Designs

The proof flow of the paper "On the Existence of Designs" by Prof. Keevash as I understand it is the following: -- Reduction from the general case to $V = \mathbb{F}_{p^a}$ (Lemma 6.3) -- Covering ...
0
votes
1answer
36 views

Minimal hypergraphs with respect to separation

Let $H = (V, E)$ be a hypergraph, that is $V$ is a set and $E \subseteq \mathcal{P}(V)$. We say that $H$ is $T_1$ if for $v\neq w$ there are $e_v, e_w \in E$ such that $v\in e_v, w\notin e_v, w\in ...
0
votes
0answers
91 views

A question about the duality principle

Suppose $X$ and $Y$ are finite sets and $K:X\times Y\to \mathbb R$ is some function. We get an integral transform from the space of real functions on $X$ to real functions on $Y$ given by ...
0
votes
0answers
71 views

independent subset problems [on hold]

I'm interested in the following which i suspect is probably a well studied problem. Given a set $N=\{1,2,...,n\}$ and $M=\{1,2,...,m\}$ consider a map $$f:N\rightarrow 2^{M}$$ (elements of $N$ to ...
9
votes
2answers
236 views

Is there any relationship between the topologies of the clique complex and the independence complex?

Let $G$ be a simple graph on a finite vertex set. The clique complex $X(G)$ is the simplicial complex whose faces are complete subgraphs of $G$, and the independence complex $I(G)$ is the simplicial ...
25
votes
1answer
538 views

“Nyldon words”: understanding a class of words factorizing the free monoid increasingly

BACKGROUND. Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor ...
5
votes
2answers
161 views

Decomposing polyhedral cones into “direct sums” and a polynomial

This question consists of two parts. I'm not breaking it up into two separate ones because posing the second question would essentially require me two rewrite the first one. Also, to some extent, the ...
1
vote
1answer
101 views

NP hard problems on UD graphs

I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard. ...
8
votes
2answers
363 views

Infected square

I saw the following problem in Mathematical Puzzles from Peter Winkler (very good book, by the way): imagine you infect k cases of a chessboard nxn and the infection spreads to a case if it has at ...
10
votes
0answers
112 views

Polytopes with few vertices and few facets

I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...
6
votes
1answer
174 views

Origin of the numbers game

The numbers game is a (one-player) game played on a finite graph with an initial assignment of numbers to its vertices, studied by Alon, Bj\"orner, Brenti, Donnelly, Eriksson, Krasikov, Mozes, Peres, ...
0
votes
1answer
156 views

Closed form of the sum involving product of 4 binomial coefficients [closed]

I'm trying to find closed form of the expression: $$\sum_{k\in\mathbb{N}}{{a \choose k}{b \choose k}{a \choose c-k}{b \choose c-k}},$$ where $a,b,c\in \mathbb{N}$, and ${x \choose y}=0$ for $y>x$ ...
1
vote
1answer
61 views

Regular unimodular triangulation for a certain simplex

Consider an $n$-simplex with vertices given by $(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers, and $i=0,1,\dots,n+1$. Does this simplex admit a regular, ...
3
votes
1answer
72 views

Stable equilibria of points on the 2-sphere

Suppose $n$ points lie on the sphere $S^2=\{x\in\mathbb{R}^3\mid \|x\|=1\}$ and are subjected to a repulsive acceleration that pushes away a point from each other point with an intensity proportional ...
13
votes
9answers
1k views

Combinatorial Databases

At one point, I remember being excited by seeing the website Encyclopedia of Combinatorial Structures as an extension of Sloane's Online Integer Sequence Database site. Unfortunately, the site (ECS) ...
8
votes
0answers
141 views

Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...
0
votes
0answers
197 views

A hard combinatorial identity

I asked this questions on the http://math.stackexchange.com/questions/1016713/ But I don't get answer. I try to prove the following hypothesis $$\sum_{i=0}^{min\{k, n-1\}}(-1)^i { n+i-1 \choose ...
0
votes
0answers
77 views

Does the weak Hadwiger conjecture imply the Hadwiger conjecture?

For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements: (H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$. ...
0
votes
0answers
84 views

Proof of Faà di Bruno's formula with convolution identity

Faa di bruno's formula can be expressed as follows $$ \frac{d^n}{dx^n}[f(g(x))] = \sum_{k=1}^{n}f^{(k)}(g(x)) B_{n,k}(g'(x),....,g^{(n-k+1)}(x)) $$ On this Wikipedia page, there is a convolution ...
-1
votes
1answer
63 views

Combinatorial Interpretation of Generalized Stirling numbers

I know the combinatorial interpretation of first, and second order Stirling numbers (#of k cycles of n items, and #of partitions n items into k subsets). Is there an interpretation for the generalized ...
-2
votes
0answers
85 views

Calculation of Shannon and Simpson Index as a function of time [closed]

Suppose a_i(t) for i=1,2,...,n, represents species density at time t As the system evolves, smaller a_i's, than a critical value, get still smaller and ultimately vanish while the others keep ...
1
vote
0answers
31 views

Distributing partially known data between n parties

Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ ...
2
votes
1answer
82 views

irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...
0
votes
0answers
83 views

Best possible concentration inequality in high dimensions

Let $X_1,\ldots,X_n$ be independent random variables in $\mathbb{R}^d$ with $EX_i=0$ and $||X_i||_{2}\leq 1$. What is the best known exponential upper bound for $$P(||X_1+\cdots+X_n||_{2}>x)?$$ In ...
12
votes
0answers
160 views

Coloring the edges of a torus graph

Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most ...
2
votes
1answer
118 views

A property of monomials in a Schubert polynomial

I came across a property of monomials in a Schubert polynomial in Lascoux's book: http://www-igm.univ-mlv.fr/~al/ARTICLES/CoursYGKM.pdf page 62, footnote 4. The property is as follows. Let us ...
12
votes
1answer
185 views

Number of orders of $k$-sums of $n$-numbers

Suppose we have a $n$-element set $S$. Denote the set of its $k$-element subsets by $K$ ($|K|=\binom{n}{k}$). If the elements of $S$ are real numbers then to each $k$-element subset we can associate ...
2
votes
1answer
159 views

Random walks with exponential decreasing steps

Let $g$ be the golden number (or another algebraic integer in $(0,1)$ that fullfills an equation with coefficients $\pm 1$). Consider the random walk on $\mathbb{R}$ starting with $0$ and walking ...
10
votes
2answers
363 views

Number of paths through infinite trees with given “growth rates”

(Preface: This may be a naive or easy question for experts....) Consider an infinite tree, rooted on the left, where each node has two children; the number of nodes at each level (distance from the ...
0
votes
1answer
88 views

All $2$-designs arising from the action of the affine linear group on the field of prime order

Let $p$ be a prime and $\mathbb{Z}_p$ denote as usual the field of order $p$. Let $AL(p)$ be the affine linear group $\{x\mapsto ax+b \;|\; a\in \mathbb{Z}_p\setminus \{0\}, b\in\mathbb{Z}_p\}$. For a ...
5
votes
1answer
135 views

Combinatorial proof of the Cauchy identity for double Schubert polynomials

The Cauchy identity for double Schubert polynomials states $$ \mathfrak{S}_w(x;-y) = \sum_{\substack{u,v \in S_n \\ w=v^{-1}u \\ l(w) = l(v) + l(u)}} \mathfrak{S}_u(x)\mathfrak{S}_v(y).$$ Is there a ...
2
votes
0answers
161 views

Minimizing $\{0,1\}$-sequence permutations

Explanation: For a given bit sequence $f$, reposition the bits as to minimize $G$ which can be thought of as a measure of how poorly proportional $f$ is to each of its subsequences. Let $p \in ...
6
votes
2answers
223 views

Counting valid coordinates

We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in ...
5
votes
1answer
176 views

Bijective proof of an Abel-Hurwitz-type identity

Can anyone sketch for me a bijective proof of the fact that the number of spanning trees of the complete graph on $n$ vertices, $K_n$ (given by the formula $ t_n = n^{n-2}$), satisfies $ t_n = ...
2
votes
1answer
103 views

Maximum number of hyperedges on a hypergraph without a spanning tree

Although every connected graph has a spanning tree, the same is not true for hypergraphs: consider the hypergraph on 4 vertices with all possible edges of size 3. You need to pick at least two edges ...
11
votes
0answers
93 views

On some special spanning trees of grid graphs

I would like to know if there are existing results on the following objects: spanning trees of a grid graph, with no corridor where a corridor is a vertex having exactly two neighbors, on ...
1
vote
1answer
134 views

Probability of each edge in K-clique [closed]

For $c \in R$ and $k \in N$, $k \geq 3$ let $p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$. I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...
0
votes
1answer
68 views

Using upper bound information in graph search

I am using A* (A-Star) to search a graph. A* algorithm takes advantage of the information $h(x)$, which is a lower bound of the distance between a vertex $x$ and the destination vertex. In other ...
4
votes
1answer
267 views

The formula for a perhaps basic identity (move from stackexchange)

The following question is moved from math stackexchange. It seems that this is not a popular question, but I really want to know the answer so I moved it to here. The question reads as follows. We ...
1
vote
0answers
116 views

Simultaneous vanishing of convolutions of Mertens function with itself

By Landau's theorem on Dirichlet series, we know that all the step functions ($k\geq 1$) $$M_k(x)=\frac{1}{2\pi i}\int^{2+i\infty}_{2-i\infty}\frac{x^sds}{\zeta^k(s)s}=\sum_{n\leq ...
7
votes
5answers
433 views

Bound on sum of complex summands involving binomial coefficients

I am trying to find the asymptotic behavior of the sum: $$ \sum^n_{i=0} \begin{pmatrix} 2n \\ i \end{pmatrix} x^i y^{2n-i}$$ as $n\rightarrow\infty$. Here $x$, $y$ are complex numbers and I have ...
5
votes
0answers
151 views

The sum of all the elements of every non empty subset of $A$ is not a multiple of $n$

Let $N=\{1,2,\ldots ,n\},n>1$. We wish to construct a set $A\subseteq N$ with the property: The sum of all the elements of every non empty subset of $A$ is not a multiple of $n$. ...
1
vote
1answer
202 views

Probability of connected graph on torus

Let $G = (V, E)$ be a graph on n vertices constructed in the following way: Each vertex $v \in V$ is positioned uniform randomly in $[0, 1] × [0, 1]$. Connect two vertices $u, v \in V$ if $d(v,u) ≤ ...