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
52 views

What are constructions for induced $C_5$-free graphs?

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, ...
0
votes
2answers
102 views

Worst case difference in rank by column-row swapping

Given a matrix $m\in\{-1,+1\}^{n\times n}$. Consider $m^\sigma$ to be collection of all matrices obtained from $m$ by permuting rows and columns. Consider $\mathscr{M}[m^\sigma]$ to be collection of ...
6
votes
1answer
85 views

Counting equivalence relations with marked classes

The number of equivalence relations on a set of $n$ elements is the Bell number $B_n$. If we wish to count the number of equivalence classes on a set of $n$ elements where one of the classes is ...
4
votes
0answers
57 views

Prove or disprove a claim about covering a polytope by convex polytopes in a certain way

Here is the claim: Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes ...
0
votes
0answers
37 views

3D matching modification

Consider all instances of the $3D$ matching problem where all edges that intersect-intersect in "exactly" one vertex (1-edge intersection). Consider all instances of the $3D$ matching problem where ...
10
votes
6answers
822 views

Algorithms for calculating R(5,5) and R(6,6)

Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said: Suppose aliens invade the earth and threaten to obliterate it in a year's time unless ...
2
votes
2answers
192 views

binomial/factorial identity mod p

In trying to determine the spectrum of a well-known ergodic transformation, I came up with the following useful (for me) result. Let $p$ be a prime and $a$ a positive integer. Then for $M$ a positive ...
3
votes
1answer
69 views

$P_3$-factors for 3-regular, 3-connected cubic graphs

Suppose that $G=(V,E)$ is a simple graph. We know if $G$ is 3-regular, 3-connected and $|V|=4k$ for some $k\in \mathbb{N}$, then $G$ has a $P_4$-factor. Question. Let $G=(V,E)$ be 3-regular, ...
2
votes
2answers
166 views

Simultaneous lcms

Suppose that we have some finite number of $k$-tuples then we define the lcm of two of these tuples to be the tuple of lcms of the co-ordinates. E.g. $[(9, 10), (5, 18)] = ([9, 5], [10, 18]) = (45, ...
14
votes
0answers
271 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
55 views

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

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
260 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
169 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 ...
5
votes
2answers
220 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
169 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
42 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
144 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
78 views

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

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
94 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
128 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
119 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 ...
1
vote
0answers
100 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 ...
4
votes
0answers
89 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
632 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
129 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
38 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
125 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
57 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)$ ...
3
votes
1answer
142 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
233 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
85 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
90 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
112 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
115 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
51 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
169 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
307 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
369 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
37 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
129 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
97 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
122 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
189 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
291 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
74 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\}$ ...