6
votes
Approximating distance on a finite graph with Hamming distance
Any such map $\pi$ can be treated as a distribution of partitions of the graph, where you uniformly sample $b \gets B$ and then split to partitions based on $\pi(v)(b)$. Your requirements are that:
...
5
votes
Accepted
Is the partition tiling relation transitive?
Counterexample. Consider the following partitions of $\omega$.
$P=\{\{0\},\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\dots\}$
$Q=\{\{0,1,2\},\{3,4\},\{5,6\},\dots\}$
$R=\{\{0,1\},\{2\},\{3\},\{4\},\{5\},\{6\}...
4
votes
Accepted
Is the group of translations of an affine plane always commutative?
Let $G$ be an arbitrary countably-infinite group. I claim that there is an affine plane $X$ such that $\operatorname{Trans}(X)$ contains a subgroup isomorphic to $G$.
By a back-and-forth argument one ...
3
votes
Accepted
The sum of the signs of conjugacy classes in the symmetric group S_n
We'll can prove this with Clifford theory and some counting, for the normal subgroup of $A_n$ in $S_n$. Let $\tau$ be a transposition in $S_n$.
Splitting into simple lemmas:
$r$ is the number of ...
2
votes
Accepted
Sufficient condition for linear separability of a boolean function on $n$ variables
The condition is not sufficient. This is a counterexample for $n=9$:
...
2
votes
A divisibility of q-binomial coefficients combinatorially
I have posted a paper about this problem to the arxiv:
Lattice Points and Rational q-Catalan Numbers
The paper contains some historical discussion. As I mention in Section 5, the first proof that $$\...
2
votes
Accepted
Counting hyperplane arrangements up to combinatorial equivalence, simple examples and history
Combinatorial types of hyperplane arrangements are called dissection types in the dissertation of L. Finschi: https://finschi.com/math/publ/2001-08-31_Finschi_A-Graph-Theoretical-Approach-for-...
2
votes
Asymptotics for Ramsey Theory
First, the short answer to the general question is that $\frac{A(n,d,k)}{\binom nk}$ is (nonstrictly) increasing in $n$, whence for $n\ge m$ we have
$$A(n,d,k)\ge\frac{A(m,d,k)}{\binom mk}\binom nk\ge\...
2
votes
Reference request for a subfamily of regular graphs
Not for $S_4$. In fact it would take $12$ colors so that every vertex had neighbors of distinct colors. But then there are $(12!)^2$ such colorings!
Because the graph is bipartite, each of the $6$ ...
2
votes
Accepted
Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?
Already in the plane there are arrangements such that the longest path in their dual covers roughly at most $2/3$ of the regions, therefore they are not Hamiltonian. The reason is that the dual graph ...
1
vote
Isometric path cover number of the 2 dimensional grid graph
I don't see how to prove $2n/3$ easily, but in case it is useful here is a simple idea in order to prove a lower bound of $(2-\sqrt{2})n> 0.58n$, beating the simple $n/2$ lower bound coming from ...
1
vote
Some questions about induced subgraphs of the directed hypercube graph
I thought this would be a full solution (i.e. showing (1) is $\sqrt{n}/2$), but in fact it only yields (1) is less than or equal to $\sqrt{n}/\sqrt{2}$. I'll still post it after all of the effort, ...
1
vote
Reference request for a subfamily of regular graphs
"Nice" graphs are covering graphs of reflexive cliques (looped complete graphs) ${K_n}^\circ$. Definitions of covering graphs and coverings (or locally bijective homomorphisms) often don't ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
co.combinatorics × 10648graph-theory × 2226
nt.number-theory × 1228
reference-request × 1031
pr.probability × 778
discrete-geometry × 586
rt.representation-theory × 508
linear-algebra × 493
gr.group-theory × 452
sequences-and-series × 386
enumerative-combinatorics × 380
permutations × 338
graph-colorings × 334
algorithms × 324
additive-combinatorics × 312
partitions × 289
polynomials × 285
ag.algebraic-geometry × 272
binomial-coefficients × 252
mg.metric-geometry × 238
convex-polytopes × 236
matrices × 235
computational-complexity × 223
generating-functions × 209
finite-groups × 181