BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Ilia Ponomarenko contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
The WL-dimension of a graph X is the smallest positive integer m such that the m-dimensional Weisfeiler-Leman algorithm correctly tests the isomorphism between X and any other graph. It is proved that the WL-dimension of any circulant graph of prime power order is at most 3, and this bound cannot be reduced. The proof is based on using theories of coherent configurations and Cayley schemes over a cyclic group.
The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a representing tree, and the leafage of a chordal graph is defined to be the minimum number of leaves in a representing tree for it. We prove that chordal graph isomorphism is fixed parameter tractable with leafage as parameter. In the process we introduce the problem of isomorphism testing for higher-order hypergraphs and show that finding the automorphism group of order-$k$ hypergraphs with vertex color classes of size $b$ is fixed parameter tractable for any constant $k$ and $b$ as fixed parameter.
Recent classification of $\frac{3}{2}$-transitive permutation groups leaves us with three infinite families of groups which are neither $2$-transitive, nor Frobenius, nor one-dimensional affine. The groups of the first two families correspond to special actions of ${\mathrm{PSL}}(2,q)$ and ${\mathrm{PΓL}}(2,q),$ whereas those of the third family are the affine solvable subgroups of ${\mathrm{AGL}}(2,q)$ found by D. Passman in 1967. The association schemes of the groups in each of these families are known to be pseudocyclic. It is proved that apart from three particular cases, each of these exceptional pseudocyclic schemes is characterized up to isomorphism by the tensor of its $3$-dimensional intersection numbers.
It is proved that with finitely many possible exceptions, each cyclotomic scheme over finite field is determined up to isomorphism by the tensor of 2-dimensional intersection numbers; for infinitely many schemes, this result cannot be improved. As a consequence, the Weisfeiler-Leman dimension of a Paley graph or tournament is at most 3 with possible exception of several small graphs.
The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of $k$-WL to recognition of graph properties. Let $G$ be an input graph with $n$ vertices. We show that, if $n$ is prime, then vertex-transitivity of $G$ can be seen in a straightforward way from the output of 2-WL on $G$ and on the vertex-individualized copies of $G$. However, if $n$ is divisible by 16, then $k$-WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with $n$ vertices as long as $k=o(\sqrt n)$. Similar results are obtained for recognition of arc-transitivity.
A graph is said to be distance-hereditary if the distance function in every connected induced subgraph is the same as in the graph itself. We prove that the ordinary Weisfeiler-Leman algorithm correctly tests the isomorphism of any two graphs if one of them is distance-hereditary; more precisely, the Weisfeiler-Leman dimension of the class of finite distance-hereditary graphs is equal to $2$. The previously best known upper bound for the dimension was $7$.