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)

0
votes
0answers
23 views

A graph constructed using non edge intersecting cliques

Suppose I have a graph $G=(V,E)$ which is the union of non edge intersecting cliques $K^{i_{1}},K^{i_{2}},.....,K^{i_{m}}$ where $1 \leq i_{j} \leq n$ for $j \in \{1,...,m\}$. I'm interested to know ...
4
votes
0answers
68 views

Need explicit formula for certain “$q$-numbers” involving gcd's

The question is motivated by yet another possible approach to a combinatorial problem formulated previously in "Special" meanders. I'm not giving details of the connection as I believe the ...
-4
votes
0answers
43 views

Cayley graph of dihedral group is isomorphic to which kind of graphs? [on hold]

Let D_{2n}= be dihedral group of order 2n. Also let D_{2n}= in which 1\ notin S=S^{-1}. In this case Cay(D_{2n}, S) is isomorphic to which kind of graphs? This is my conjecture that this graph is ...
7
votes
2answers
241 views

When is a sequence the sum of two Beatty sequences?

In other words, given a sequence $(s_n)$, how can we tell if there exist irrationals $u>1$ and $v>1$ such that $$s_n = \lfloor un\rfloor + \lfloor vn\rfloor$$ for every positive integer $n$? ...
1
vote
1answer
119 views

Counting matrices of special types

How many symmetric and non-symmetric $n\times n$ matrices with $0/1$ entries are there such that every row is distinct and every column is distinct? (I am looking for a proof as well). If only every ...
4
votes
1answer
137 views

Four Dimensional Rook Domination

Let $\gamma(G)$ denote the domination number of a graph, and $G\,\square\,H$ denote the cartesian product of two graphs. Then $K_8\,\square\, K_8$ is the rook graph, whose vertices are the squares of ...
3
votes
1answer
162 views

Largest symmetric matrix given rank

Let $\mathscr{M}[n,d]$ be collection of $n\times n$ symmetric matrices with real entries from $\{0,1\}$ such that every row/column is distinct with sum of every row/column being $d$. What is minimum ...
2
votes
1answer
41 views

Vanishing Restricted Isometric Constant

In compressed sensing, we are interested in the restricted isometry property. Suppose the design matrix is $n$ by $p$, consisting of $np$ iid $\mathcal{N}(0, 1/n)$ entries. Assume both $n$ and $p$ are ...
3
votes
1answer
141 views

higher dimensional analogue of EGZ theorem

The EGZ theorem states that any multiset of $2n-1$ integers has a subset of size $n$ the sum of whose elements is a multiple of $n$. Kemnitz-Reiher theorem is a 2-dimensional analogue of EGZ. Here is ...
-6
votes
0answers
71 views

A Paradox by a Variant of Von Neumann's coin toss [on hold]

All biased coins are fair. If I have a biased coin whose probability of heads is $p$, and keeps tossing it, and only stops when the number of heads equals tails, then each sequence I get has a ...
9
votes
0answers
83 views

Is there a nice formula for the “non-crossing substitution” of linear combinatorial species?

Background A linear species is a functor $$F : \mathrm{Lin} \to \mathrm{FinSet},$$ where $\mathrm{Lin}$ is the category of totally ordered sets and bijections and $\mathrm{FinSet}$ is the category ...
4
votes
0answers
113 views

inequality in a shape of inclusion exclusion formula

I have two inequalities to show, both of which describe some probabilities. First I know how to handle, and it follows from applying arithmetic-harmonic mean inequality: consider 9 numbers ...
5
votes
0answers
106 views

Extrapolation between longest increasing and longest alternating subsequences

The question When should we expect Tracy-Widom? motivated me to post the following question, in which I have been interested for a while. Let $f(n)$ be a function from the positive integers to ...
0
votes
0answers
46 views

Embedding of non-planar graphs

I'm interested in the proof that vertex cover is NP-complete for unit disk graphs. The paper where the proof can be found is the following ...
1
vote
0answers
95 views

Fundamental theorems of invariant theory, twisted by a representation

Let $V$ be a finite dimensional complex vector space and let $G = \mathrm{GL}(V)$. The first and second fundamental theorems of invariant theory for $V$ give generators and relations for the algebra ...
3
votes
0answers
58 views

Generalization of Sprague-Grundy Theorem

In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...
8
votes
3answers
622 views

Why does the bitxor function appear in Nim?

I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...
0
votes
0answers
57 views

Minimum rank of certain matrices

Let $\mathscr{M}[n]$ be collection of $n\times n$ matrices with real entries from $\{0,1\}$ such that every row is distinct and every column is distinct. What is minimum real rank of matrices in ...
5
votes
1answer
124 views

partition of a convex set into squares

Let $P$ denote the perimeter function. It's not hard to prove that for any rectangle $R$ in $\mathbb{R}^2$, $R$ can be partitioned into a countable collection of squares $\{Q_k\}_{k=1}^{\infty}$ such ...
0
votes
0answers
35 views

On subset of items in ordered list would like to calculate cardinality of set of orderings grouped by kendall tau distance

Let's say I have an ordered list of length $n$ which I will denote $12\ldots n$. There are $n!$ ways to rearrange the items in this list. Take a subset of the items in the list $B\subset ...
2
votes
1answer
123 views

Expected value (probability) maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like $$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$ Here $f(k,x)$ is actually a probability coming from a ...
0
votes
0answers
54 views

Classic question on integer partitions (with distinct summands)

I guess that the following was solved sometime in the 18th century, but could not find a reference to it. I am interested in approximations to the following integer partition problem: Denote $R(N,L)$ ...
0
votes
0answers
33 views

Boundedness of product of matrix and {-1,1} vector [closed]

Could you help me with this problem? Let m, n be natural and let M be matrix mxn in which all columns have euclidean length 1. Prove that there exists a vector v of {-1, 1}^n so that Mv belongs to ...
3
votes
1answer
140 views

Products of relative prime numbers with least sum

Let $P(n)$ be the set of subsets $P$ of $\mathbb{N}$ with the properties All elements of $P$ are relative prime to each other. The product of all $k \in P$ is greater or equal to $n$. Now let ...
10
votes
0answers
230 views

Reference request: a combinatoric result [closed]

When I tried to construct a counterexample in my research, I encountered the following result, which should be true. Let $m=m(n)$ be a function that grows faster than $\sqrt n$, so $m(n) = ...
0
votes
0answers
84 views

A sum on a minimums conjecture

Prove or disprove: $$m(n,k,s)=\sum_{a_1=1}^n \sum_{a_2=1}^n \cdots \sum_{a_k=1}^n \min(a_1, a_2,\cdots, a_k)^s =$$ $$ \sum _{i=0}^{k-1} \frac{(-1)^i}{i!} F(n,i+s) \sum _{j=0}^{k-1} \frac{\partial ...
2
votes
1answer
88 views

Probability of Hamming weight

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick ${n^t}$ random vectors $\{v_i\}_{i=1}^{{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$. Denote $v_j\cap v_j$ to be ...
4
votes
1answer
106 views

Motzkin polynomials and enumeration of chord diagrams

On page 12 of the paper Enumeration of chord diagrams on many intervals and their non-orientable analogs" by Alexeev, Andersen, Penner, and Zograf is a list of polynomials which are a refinement of ...
4
votes
0answers
113 views

Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...
2
votes
0answers
49 views

Vanishing of finite difference operators by composition under a cyclic condition

Consider $n$ finite difference operators $D_1, \ldots, D_n$ acting on real-valued functions $f_1 (y), \ldots , f_n (y)$ of a variable $y$, with the following properties: (i) $D_i f_i (y) = 0$ for ...
12
votes
1answer
166 views

Asymptotics of coefficients of implicitely defined generating function

I have two integer sequences $\{a_n\}_{n=0}^\infty$ and $\{b_n\}_{n=0}^\infty$. Explicit formulas for the $a_n$ are known and their asymptotic growth is fully understood. My wish is to also understand ...
10
votes
0answers
300 views

Combinatorial results by Poincaré duality

For the n-dimensional Torus, the k-th homology group (with integer coefficients) is isomorphic to the direct sum of $n \choose k$ copies of $\mathbb{Z}$. Poincaré duality thus gives us a somewhat ...
6
votes
2answers
322 views

Embedding of planar graphs

I've recently come across the following lemma. Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...
2
votes
0answers
36 views

Catalogs/numbers/constructions of non-isomorphic conference matrices

I am interested in complete catalogs of non-isomorphic conference matrices, similar to those of Hadamard matrices. Do such catalogs exist? If yes, then where could they be found, and what is an ...
0
votes
1answer
43 views

Extracting path information for a directed acyclic graph

For a research problem I am tackling, I have a directed acyclic graph $G(V,E)$. With every node in $V$, I have a variable $y$ associated. Now, given two nodes $i$ and $j$, I would like to have the sum ...
2
votes
0answers
52 views

Linear intersection number of a product of graphs

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties: for $e\in L$ we have $|e|\geq 2$; if $e_1\neq e_2 \in L$ then ...
2
votes
1answer
128 views

Number of lines of symmetry of a set of lattice points

Given some finite $S\subseteq\mathbb R^2$, it is clearly possible for $S$ to have arbitrarily many lines of symmetry. However, it is not very clear if the same is necessarily true for subsets of ...
3
votes
0answers
96 views

“Standard” notation for symmetric functions?

Here is what I encountered in the paper "The Optimal Lattice Quantizer in Three dimensions" by Barnes and Sloane. Here is the setup: Let $\Lambda$ be a lattice in $\mathbb{R}^3$. Around each ...
1
vote
1answer
121 views

Selecting columns of a set of boolean matrices with constraint on the ones in each row

I've come up with the following question in my research: Let $S$ be a finite set of $n \times n$ matrices with elements 0 or 1. denote $n_i$ as the total number of 1's in the $i$th row of all matrices ...
8
votes
1answer
185 views

Cheeger Numbers for 3-regular Graphs

A student wanted a challenging Graph Theory programming project and I had him try to determine the maximum value of the Cheeger number (isoperimetric number) among all 3-regular graphs of order $n$, ...
3
votes
2answers
289 views

Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?

Given $n$ and $t$ lengths $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$, of directed diagonals within an $n$-gon such that $l_1+\cdots+l_t\neq 0 \pmod n)$. Does it exist a directed path within ...
0
votes
0answers
58 views

How often does a one-dimensional lazy random walk end at the origin? [migrated]

This seems like it's probably a solved problem, but I don't seem to be googling the right keywords. I want to know the probability that a lazy random walk on $\mathbb{Z}$ ends where it started. To be ...
4
votes
1answer
70 views

How to realize any non-crossing matching as $\mathrm{Re}[p(z)]=0$

Asymptotically any polynomial is $p(z) = z^n + O(z^{n-1})$. Therefore $\mathrm{Re}[p(z)]= r^n \cos(2\pi i \theta)$ which vanishes at $\theta = \frac{(k+ \frac{1}{2})\pi}{n}$. Those $2n$ line ...
4
votes
0answers
92 views

Counting vertex-permutations of a finite tree which rip all edges

Given a finite tree $T$ with $n$ vertices labelled $1,\dots,n$, we say that a permutation $\sigma$ of $1,\dots,n$ rips all edges if $\{\sigma(i),\sigma(j)\}$ is never an edge for every edge $\{i,j\}$ ...
2
votes
1answer
90 views

Maximal neighbour-full partition of $\{0,1\}^n$

What is the largest complete minor of the $n$-dimensional hypercube? (which we call $k(n)$) Alternatively, what is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that ...
1
vote
0answers
92 views

Evaluation of Macdonald Polynomials at $x_1=x_2=…=x_n = h$

This question is related to my previous question (here). Let $P_\lambda$(q,t) be the Macdonald polynomials with partition $\lambda$. Let $\Lambda$ denote the ring of symmetric functions over the ...
3
votes
0answers
82 views

A “nice” Orthogonal Basis for Translation Invariant Symmetric Polynomials

It is going to be a rather long question, so I will first state it and then try to explain and motivate it. Take $\Lambda_n $ as the graded ring of symmetric polynomials of a field $F$ in $n$ ...
35
votes
0answers
1k views

How to prove this polynomial always has integer values at all integers?

Let $m$ be any positive integer. $$ P_m(x)=\sum_{i=0}^{m}\sum_{j=0}^{m}{x+j\choose j}{x-1\choose j}{j\choose i}{m\choose i}{i\choose m-j}\frac{3}{(2i-1)(2j+1)(2m-2i-1)}. $$ Question: $P_m(x)$ always ...
10
votes
2answers
885 views

A new generalisation of Fermat's little theorem?

I would like to share a personal result, which I interpret as a "generalisation of Fermat's little theorem". I know that there exist already several generalisations (e.g. Euler's) but I would like to ...
3
votes
0answers
121 views

Algebraic integers with conjugates of fixed norm

Let $n$ be a positive integer and let $Q_n^d$ be the set of algebraic integers $\zeta$ which live in a degree $d$ extension of the rationals and such that any Galois-conjugate $\zeta^\sigma$ of ...