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: ...
Command Master's user avatar
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\}...
bof's user avatar
  • 11.5k
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 ...
user49822's user avatar
  • 2,033
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 ...
Chris H's user avatar
  • 1,854
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$: ...
gsitcia's user avatar
  • 136
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 $$\...
Drew Armstrong's user avatar
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-...
Stefan Forcey's user avatar
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$ ...
Aaron Meyerowitz's user avatar
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 ...
Jan Kyncl's user avatar
  • 5,931
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 ...
Louis Esperet's user avatar
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, ...
Ronnie Pavlov's user avatar
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 ...
Marcin Wrochna's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible