Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
2
votes
0answers
29 views
What is the best lower bound for 3-sunflowers?
A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = C $ for all $i \neq j$ for some fixed $C$. A well-known conjecture of Erdos and Rado says that in any $k$-uniform family of ...
0
votes
0answers
25 views
Characterizing and counting boolean functions with all influences 1/2
Is there a characterization of boolean functions $f:\{-1,1\}^n \longrightarrow \{-1,1\}$,
so that $\mathbf{Inf_i}[f]=\frac{1} {2}$, for all $1\leq i\leq n$? Is it known how many such functions there ...
3
votes
1answer
108 views
Existence of a certain subset of natural numbers
I was talking to a friend and the following set $S$ came up.
Let $f$ be some real valued function tending to infinity.
Let $S$ be a subset of natural numbers such that $|S \cap [1,N]| = N^{\delta}+ ...
3
votes
0answers
37 views
Matching in the Boolean Algebra
We consider the Boolean Algebra of the set $[n]=\{1,\dots,n\}$ and the matching $\psi$ from the $m+1$ subsets of $[n]$ into the $m$ subsets of $[n]$ for $(n+1)/2\leq m+1\leq n$, which is used to show ...
1
vote
0answers
131 views
A generalized urn-ball matching problem; Complicated combinatoric/probabilistic limit
I'm looking for a generalization to the urn-ball matching problem. As a reminder of what I've got in mind, here's the simple version:
Randomly assign (with replacement) $N$ balls to $M$ urns. ...
3
votes
1answer
67 views
Extremal graph theory for directed graphs
In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...
3
votes
0answers
41 views
Reference for Frobenius’s proof of Schur’s finite version of the Rogers - Ramanujan identities
In his paper “Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche” I. Schur has stated that Frobenius has communicated to him a simple direct proof of his finite version of the ...
-1
votes
0answers
23 views
departure time/overlap algorithm [on hold]
i'm looking for "departure time/overlap algorithm" or any other idea.
Suppose you have n trains and each one has a performance profile(how much electricity they need at the current time while driving ...
0
votes
0answers
82 views
Error term in formula for products of necklaces
Let us consider the $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$, where the number of fixed necklaces of length n composed of a types of beads $N(n,a)$ can be calculated via totient function: ...
0
votes
0answers
31 views
Single element extensions of subspace arrangement over finite field
Matroids have single element extensions found by Crapo[2] to create ground set size $n+1$ matroids from ground set size $n$ matroids. Do subspace arrangements over a finite field $\mathbb{F}_q$ have ...
0
votes
0answers
116 views
Conjecture relating differential equation and sum of a function over partitions
The following is an addition to A function from partitions to natural numbers - is it familiar?; the function $f(\lambda)$ as defined there, when summed over all partitions of n, gives an unexpected ...
1
vote
1answer
202 views
An infinite product: combinatorial interpretation
It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product
...
1
vote
0answers
51 views
Bases of a matroid such that their complement is an independent set
Let $M$ be some matroid on $[n]$ with set of bases $\mathcal{B}$. I am interested in the subset $\mathcal{B}' \subseteq \mathcal{B}$ of bases $b \in \mathcal{B}$ with the property that $[n] \setminus ...
7
votes
4answers
275 views
Extremal examples for a folklore lemma on subgraphs of large minimum degree
It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...
0
votes
0answers
60 views
Generalized Leibniz rule for higher derivative of multiple factors [closed]
Is there a "nice" general formula that expresses the following (formal) derivative
$$\frac{d^n}{dx^n} \prod_{i=1}^N a_i(x)$$
"in terms of" the higher derivatives $a_{\nu}^{(k)}$ of each $a_{\nu}$?
4
votes
1answer
95 views
Generalized permutahedron and random polytopes
The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
1
vote
1answer
119 views
Degree Sequence Problem on $k$-Partite Graphs
The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees ...
8
votes
3answers
267 views
A strengthening of Frankl's union-closed conjecture?
Frankl's union-closed conjecture states that if $F$ is a finite union-closed family of sets (i.e. a family that is closed under taking unions), then there must be an element that belongs to at least ...
2
votes
1answer
108 views
Calculating the probability that all possible length $r$ subwords exists in a string, with or without overlaps allowed
Let $S$ be a length $L$ string, where each character in the string is chosen with uniform random probability over an alphabet with $q$ characters. For example, a binary string would imply $q = 2$, a ...
1
vote
0answers
88 views
Combinatorial design for minimization problem over binary strings
Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
1
vote
0answers
41 views
On generating Euler Square of index q, q-1 (where q is any prime power)
Can somebody help me in generating Euler Square of index q, q-1 (where q is any prime power). Also, kidly tell me if there is any code availeble for generating the stated Euler Square. The details of ...
0
votes
0answers
47 views
Find minimal set of progressions which intersections, unions or negations covers given set
Given an integer $N$ and a set of integers in $[1; N]$. Find a minimal set of integer arithmetical progressions such as given set can be covered using operations $A \cap B$, $A \cup B$ and $\overline ...
-1
votes
0answers
42 views
Feature relationship based class separability [closed]
I am a computer science guy, not a mathematician so kindly excuse me if there is any ridiculous error in my problem description.
I have two clusters $C_1$ and $C_2$ in a feature space spanned by $k$ ...
-2
votes
0answers
92 views
Paths on a Rubik's cube [migrated]
Here is the Question i'm trying to solve:
An ant is initially positioned at one corner of the Rubik's cube and wishes to go to the farthest corner of the block from its initial position. Assuming ...
3
votes
0answers
82 views
Number cubes with consecutive line sums
This is barely of research interest, but I'd classify it as a curiosity with connections to combinatorics.
The problem is to place integers in an $n \times n \times n$ array so that all $3n^2$ line ...
2
votes
1answer
84 views
Hitting sets (aka covers aka transversals) of Steiner triple systems
Does there exist a constant $c$ so that the lines of every Steiner
triple system on $v$ points can be covered by $cv$ points?
That is if $D \in STS(v)$ with point set $T=\{1,2,\ldots,v\}$ then ...
7
votes
1answer
235 views
The Simultaneous Conjugacy Problem in the symmetric group $S_N$
We are interested in the following notions in the case $G=S_N$, the symmetric group on
$\{1,\dots,N\}$.
Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define
...
2
votes
1answer
75 views
Computational complexity of deciding isomorphism of rational polyhedral cones
Let $C,C'$ be rational polyhedral cones in $\mathbb R^n$ both with non-empty interior. Rational means they are generated by vectors with rational entries. One says that $C,C'$ are isomorphic if there ...
0
votes
0answers
105 views
Base-signed harmonic series
This question is directly related to this question by Douglas Zare.
The harmonic sequence
$$s = 1 - \frac{1}{2} - \frac{1}{3} + \frac{1}{4} - \frac{1}{5} + \frac{1}{6}+\frac{1}{7}-\frac{1}{8} - ... ...
4
votes
1answer
290 views
Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality
The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
2
votes
1answer
95 views
Conjecture of a subset of Wang tile which might be decidable
From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:
The left color and ...
2
votes
1answer
216 views
A variant of Kruskal's theorem
For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of ...
34
votes
6answers
2k views
Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime
This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...
19
votes
0answers
228 views
Which region in the plane with a given area has the most domino tilings?
I just finished teaching a class in combinatorics in which I included a fairly easy upper bound on the number of domino tilings of a region in the plane as a function of its area. So this led to ...
1
vote
1answer
105 views
Assigning unique binary strings to the squares of a chessboard s.t. inter-string Hamming distances are the same as inter-square Manhattan distances
Consider a chessboard with $(n_1 \times n_2)$ squares, where we would like to assign a unique binary string, of some length $L$, to each square s.t. the Hamming distance between the strings ...
3
votes
2answers
115 views
Definition of the Moebius Ladder Graph
I found two different definitions of the Moebius Ladder Graph, whose essential difference is, whether the smallest one shall be $K_4$ or $K_{3,3}$.
according to Wikipedia ...
2
votes
2answers
111 views
Which graphs generate a matroidal independence complex?
The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$.
Now, if $G$ is a well-covered graph (where all maximal ...
0
votes
0answers
39 views
Almost symmetric route in digraphs
Let $D=(V,E)$ be a digraph. A route of length $k$ in $D$ is a pair $L=(S,\sigma)$, where $S=(s_1,s_2,\dots,s_{k+1})$ is a sequence of $k+1$ elements of $V$, and ...
14
votes
1answer
1k views
What have simplicial complexes ever done for graph theory?
(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...)
Are there examples of results in "classical" [*] graph theory that have
been achieved by using simplicial ...
1
vote
0answers
84 views
Arctic Circle Theorems and the Wave Equation
I've seen the following remark in a number of papers but don't know what to make of it. In this paper by Cohn, Elkies and Propp, it is mentioned that the normalized average Height function ...
17
votes
3answers
2k views
Where in mathematics do these polynomials appear?
Does anyone recognize the following sequence of polynomials?
$f_0(x) = x-1$
$f_1(x) = x^2-x$
$f_2(x) = x^4-2x^2+x$
$f_3(x) = x^8-3x^4+3x^2-x$
$f_4(x) = x^{16}-4x^8+6x^4-4x^2+x$
$\vdots$
The ...
2
votes
1answer
65 views
Point-Hyperplane incidence in finite projective spaces
Let $P$ be a finite projective space of order $q$ and dimension $d$. I am interested in finding the least $k$ such that for any set $S$ of $k$ points of $P$, and for any set $S'$ of $k$ hyperplanes of ...
1
vote
1answer
97 views
The edge chromatic number and pefectness of inflation of cubic graph
The inflation of graph $G$ is a graph $I(G)$
which is obtained by replacing each vertex $x$ by a complete graph
$K_{\deg(x)}$ and joining each edge to a different vertex of $K_{\deg(x)}$.
Let $G$ ...
3
votes
0answers
111 views
Is Euler-characteristic of a simplicial complex on $n$ vertices and $f$ facets at most $n^{O(\log f)}$?
(Definition: Facet = Maximal Face)
This question is a continuation of the previous one that I had asked a couple of years ago: Is Euler characteristic of a simplicial complex upper bounded by a ...
2
votes
1answer
79 views
On a conjecture by Hibi regarding h-vectors
For integral polytopes, it is conjectured (T. Hibi), that if the $h^*$-vector is symmetric, then it is also unimodal (increasing, then non-decreasing).
A non-integral polytope do not, in general, ...
4
votes
1answer
165 views
Do graphs with large number of paths contain large chain minor?
Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.
Note that the number of paths between two endpoints of a $k$-chain is $2^k.$
Question: Let ...
4
votes
2answers
152 views
Joint probability distribution as functions
Suppose $X$ and $Y$ are correlated random variables in a finite set ${\mathcal A}$, and let $f, g$ be functions that map elements from ${\mathcal A}$ to ${\mathcal B}$ for some finite set ${\mathcal ...
2
votes
2answers
760 views
Number of 1 in binary representation of n
Let $1(n)$ be the number of digits $1$ in binary representation of number $n$.
For example, $13=1101_2$ so $1(13)=3\\$
Is there explicit form of $\,\,\sum{1(i)x^i} $?
I checked OEIS and didn't find ...
1
vote
0answers
100 views
Knight's metric: ellipse and parabola
Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...
3
votes
0answers
103 views
What is the combinatorial data classifying non-normal affine toric varieties?
Recall that a toric variety is a variety $V$ containing an open dense algebraic torus. Here an algebraic torus means a finite product of copies of the multiplicative group of the ground field (which I ...
