Problem pages index
The list of problems which have appeared on my homepage and were subsequently
"put out to grass" is growing rather long, so I have tried to index them, to
make them easier to use. (There are now 165 problems here, though some are
duplicates and some have been solved.) At the same time I have integrated my
collections of permutation group problems into the main list. Comments welcome!
The notation (S) means that the problem has been solved;
the text includes either a reference to the solution, or a sketch of how
it is done. Of course, even a solved problem might be worth generalising!
Some problems appear in more than one class.
Index
In this index, numbers (Hn) refer to problems taken from my homepage;
numbers (Bn) refer to problems from my article "Permutations" in the
Budapest conference Paul Erdős and his Mathematics;
numbers (Pn) are other problems on permutations and permutation groups;
and numbers (BCCm.n) to problems I have presented at the
British Combinatorial Conference. The problems live in separate files:
homepage problems,
problems from "Permutations",
permutation group problems, and
BCC problems. (Note: the complete listing of
BCC problems is also available.)
The problems are classified as follows.
- Infinite groups
-
- H1: "Original Collatz problem"
- H8: Proportion of derangements
- H10: Orbits on pairs
- H28: Exponential constants for orbit counts
- H32: N-free graphs and denominator
identities
- H40(S): Cycle index of product
- H58: Pointwise product of orbit-counting
sequences
- H60: Automorphism groups of Henson's graphs
- H70: A conjugacy class representation of
the random graph?
- H84:Countable B-groups
- H107: the random graph and highly
transitive groups
- P2(part S): An integral domain from a
permutation group
- B28: Abelian automorphism
groups of generic n-tuples of orders
- Finite groups
-
- H20(S): Squares outside corefree subgroup
- H22(S): Groups of type {k}
- H23(S): Groups with all elements outside a
normal subgroup having prime order
- H25: Partitions and permutations
(see also B30)
- H27(S): q-analogues of fixed points
and cycles
- H30: Automorphisms inverting k
elements
- H31: Automorphism group transitive on
non-commuting pairs
- H34: Tutte polynomial and cycle index for
IBIS groups
- H36: Antichain in subgroup lattice
- H37: Embedding Boolean lattice in subgroup
lattice
- H48(S): Matrix algebra from Frobenius group
- H52: Base size and separation number
- H54: Bijective proof of Dixon's theorem
- H64: Covers of symmetric groups (see
also BCC21.13)
- H65: A near coincidence in symmetric groups
- H68, P26:
Rank and subrank of primitive permutation groups
- H77: Derangements as short words (see also
P27)
- H80: Universal families of permutation
groups
- H81: Does "spreading" imply QI?
- H100: Generating a group by coset representatives
- P1(S?): Isbell's problem
- P4: Semiregular elements in 2-closed groups
- P5: Matroids from IBIS groups
- P6: Finding small generating sets
- P7(S): Base size in almost simple primitive
groups
- P8: Permutation groups and association
schemes
- P9: A derangement problem
- P10: Graphs with prescribed automorphism
group (see also B25 and
B26)
- P11: Parker vectors
- B1: Mixing time for the
"Burnside process"
- B4: A derangement problem
- B7: Derangements of prime order
- B15: Sharp groups
- B19: Pyber's conjecture on
base size
- B20: Greedy base size
- B22: Groups meeting the strong
Maillet bound
- B23: Groups with greedy bases
of constant size
- B27(S?): Hypergraphs with
prescribed automorphism group
- Sets
-
- H41: Covering radius for sets of
permutations (see also B29 and
BCC19.12)
- H43: Sets with constant distance in
PSL(2,q)
- B9: Invariant set of random
permutation
- B12,
B13: Permutations with
prescribed distances
- B14: Sharply
s-transitive sets
- B17: "Geometric sets" of
permutations
- BCC13.19: Permutations with few
distances
- Semigroups
-
- H102: Random synchronization
- H106: Synchronizing non-uniform maps
- Miscellaneous
-
- H75: Multipermutation solutions of the
Yang--Baxter equation
- Designs
-
- H11: "Anti-biplanes"
- H14: Designs and partitions
- H15: Random Latin squares
- H21(S): Symmetric graph designs
- H57(S): Balanced Sudoku
- H78(S): Optimality and Tutte polynomial
- H79: A very weak Hadamard conjecture
- H86: The strength of the Gray map image of
a Z4-code
- H87: Intricacy of Latin squares
- H97: Covering a design with blocks
- B10,
B11: Random Latin squares
- BCC13.17: A generalisation of affine
designs
- BCC14.8: The rows of a Latin square
- BCC14.13: Block-transitive designs
- BCC16.19: Semi-Latin squares which
are partial linear spaces
- BCC17.4: An extremal problem related
to biplanes
- BCC18.9: A Markov chain for Steiner
triple systems
- Finite geometry
-
- H24: Separation in inversive planes
- H38: Derangements in affine planes
- BCC12.4: Generalised quadrangles
- BCC13.12: Permutations of projective
space
- BCC18.5: Projective space analogues
of Steiner systems
- Association schemes
-
- H33: Jordan schemes
- H48(S): Matrix algebra from Frobenius group
- P8: Permutation groups and association
schemes
- BCC16.16: Abnormal strongly regular
graphs
- Matroids
-
- H34: Tutte polynomial and cycle index for
IBIS groups
- P5: Matroids from IBIS groups
- B23: Groups with greedy bases
of constant size
- BCC16.23: Representing orthogonal
matroids
- BCC17.19(S): Covering radius and
Tutte polynomial
- Enumerative
-
- H2(S): Trees of height k
- H3,
H5: Probability of connectedness (see also
BCC15.8)
- H59: Orbital chromatic roots (see also
BCC21.12)
- H72: Orbital flow roots
- H103: Graphs with few subgraphs
- P10: Graphs with prescribed automorphism
group (see also B25 and
B26)
- BCC12.5: Edge-density of infinite
graphs
- BCC15.8: Counting classes of graphs
- Structural
-
- H9(S): "Orthogonal" edge-colourings
(see also BCC16.15(S))
- H26(S): Pigeonhole property
- H46: Homomorphism-homogeneous graphs
- H49: Positive and negative eigenvalues
- H50(S): Semiregular automorphisms (see
also BCC17.12)
- H60: Automorphism groups of Henson's graphs
- H67: Circular altitude of a graph
- H69: Core-transitive graphs
- H70: A conjugacy class representation of
the random graph?
- H73: Algebraic properties of chromatic
roots
- H85(S): The power graph of a finite group
- H91(S): Infinite hulls
- H92: The power graph of a finite magma
- B27(S?): Hypergraphs with
prescribed automorphism group
- BCC21.2: The row space of an
adjacency matrix
- H101: Chromatic number of power graph
- Number theory
-
- H16: Sums of two prime powers
- H17: Sums of consecutive primes
- H18: Fibonacci matters
- H19: An iteration on primes
- H29: Sums of reciprocals
- H35,
H42(S): Primitive lambda-roots
- H45: Sequences realisable by fixed points
of powers
- H53: Determinants of Legendre symbols
- H71: Orders of finite simple groups
- H83: Decomposing the group of units by
arithmetic progressions
- H90(S): A lim inf problem
- H93: A universal sequence from the primes?
- H105: Subgroups of the multiplicative group
- H108(S): A Diophantine approximation problem
- H109: More on Problem 19
- BCC12.3: Two Diophantine equations
- BCC12.7: Forbidding divisibility
- BCC20.10: A determinant problem
- Combinatorics
-
- H4(S): Necklaces and polynomials
- H6(S): Rapidly increasing sequences
- H12(S): Central binomial coefficients
- H13(S): Coprime polynomials
- H39: Sum-free sets in the square and cube
- H41: Covering radius for sets of
permutations (see also B29 and
BCC19.12)
- H66(S): Generalised parking numbers
- H76(S): VC-dimension and strength of Gray
map images
- BCC12.6(S): Intersecting families
- BCC13.14: Cyclic shifts of binary
words
- BCC13.24(S): Sum-free sets
containing 2
- BCC14.10(S): Even and odd permutations
- BCC14.11(S): How many sum-free sets?
- Algebra
-
- H88: Linearity of order-preserving maps
- H89: Endomorphisms and partial isomorphisms
of groups
- Other
-
- H7(S): Rolling triangular prism
- H27(S): q-analogues of fixed points
and cycles
- H32: N-free graphs and denominator
identities
- H44: Extending partial permutations
- H47: Growth of Stirling transforms
- H51: Möbius number of polyhedral
groups and connection number of root lattices (see also
BCC20.16)
- H54: Bijective proof of Dixon's theorem
- H55: Shadows of permutations and score
sequences of tournaments
- H56(S): Easy Sudoku
- H57(S): Balanced Sudoku
- H61(S): Measure-preserving transformations
of [0,1]
- H62(S): Computational complexity of
generalised Sudoku
- H63: Hilbert series of an algebra related
to multiplicative functions
- H74: Network flow where channels silt up
- H82(S): Bulgarian solitaire
- H94: Engeler–Ryll-Nardzewski–Svenonius for monoids?
- B9: Invariant set of random
permutation
- H98: closed abelian groups of isometries
of Urysohn space
- H99: synchronization properties of random
transformations
- H104: determinants of Hadamard-like and
conference-like matrices
- H44: Extending partial permutations
- H56(S): Easy Sudoku
- H62(S): Computational complexity of
generalised Sudoku
- H95: An undecidable random graph?
- H96: Optimisation where you pay for
computer time
- P6: Finding small generating sets
(see also B24)
Peter J. Cameron
p.j.cameron(AT)qmul.ac.uk
26 December 2012