Some of my research is reflected on my webpage. Namely,
I am the author and a coauthor of many sequences in the OEIS. I have a separate web page with the list of my sequences.
(with Matthew Babbitt and Jesse Geneson) On k-visibility graphs. Combinatorics arXiv 1305.0505.
We examine several types of visibility graphs in which sightlines can pass through k objects. For k ≥ 1 we improve the upper bound on the maximum thickness of bar k-visibility graphs from 2k(9k−1) to 6k, and prove that the maximum thickness must be at least k+1. We also show that the maximum thickness of semi-bar k-visibility graphs is between the ceiling of 2(k+1)/3 and 2k. Moreover we bound the maximum thickness of rectangle k-visibility graphs. We also bound the maximum number of edges and the chromatic number of arc and circle k-visibility graphs. Furthermore we give a method for finding the number of edges in semi-bar k-visibility graphs based on skyscraper puzzles.
(with Joel Brewster Lewis) Skyscraper Numbers. Combinatorics arXiv 1304.6445.
We introduce numbers depending on three parameters which we call skyscraper numbers. We discuss properties of these numbers and their relationship with Stirling numbers of the first kind, and we also introduce a skyscraper sequence.
(with Dai Yang) Connected Components of Underlying Graphs of Halving Lines. Combinatorics arXiv 1304.5658.
In this paper we discuss the connected components of underlying graphs of halving lines' configurations. We show how to create a configuration whose underlying graph is the union of two given underlying graphs. We also prove that every connected component of the underlying graph is itself an underlying graph.
(with Ziv Scully) Efficient Calculation of Determinants of Symbolic Matrices with Many Variables. CS Symbolic Computation arXiv 1304.4691.
Efficient matrix determinant calculations have been studied since the 19th century. Computers expand the range of determinants that are practically calculable to include matrices with symbolic entries. However, the fastest determinant algorithms for numerical matrices are often not the fastest for symbolic matrices with many variables. We compare the performance of two algorithms, fraction-free Gaussian elimination and minor expansion, on symbolic matrices with many variables. We show that, under a simplified theoretical model, minor expansion is faster in most situations. We then propose optimizations for minor expansion and demonstrate their effectiveness with empirical data.
My IQ. A copy of my blog essay My IQ: Published in Hacker Monthly Vol. 34, (2013), p. 34.
Conway's Wizards. History and Overview arXiv 1210.5460. Published in The Mathematical Intelligencer (2013).
I present and discuss a puzzle about wizards invented by John H. Conway.
(with Dai Yang) Halving Lines and Their Underlying Graphs. Combinatorics arXiv 1210.4959.
In this paper we study underlying graphs corresponding to a set of halving lines. We establish many properties of such graphs. In addition, we tighten the upper bound for the number of halving lines.
(with Richard K. Guy, Julian Salazar) Conway's subprime Fibonacci sequences. Number Theory arXiv 1207.5099.
It's the age-old recurrence with a twist: sum the last two terms and if the result is composite, divide by its smallest prime divisor to get the next term (e.g., 0, 1, 1, 2, 3, 5, 4, 3, 7, ...). These sequences exhibit pseudo-random behaviour and generally terminate in a handful of cycles, properties reminiscent of 3x+1 and related sequences. We examine the elementary properties of these 'subprime' Fibonacci sequences.
Tricky Arithmetic. History and Overview arXiv 1204.3112.
This article is an expanded version of my talk at the Gathering for Gardner, 2012.
(with Andrew Buchanan, Alex Ryba) Saturated Domino Coverings. Combinatorics arXiv 1112.2115.
A domino covering of a board is saturated if no domino is redundant. We introduce the concept of a fragment tiling and show that a minimal fragment tiling always corresponds to a maximal saturated domino covering. The size of a minimal fragment tiling is the domination number of the board. We define a class of regular boards and show that for these boards the domination number gives the size of a minimal X-pentomino covering. Natural sequences that count maximal saturated domino coverings of square and rectangular boards are obtained. These include the new sequences A193764, A193765, A193766, A193767, and A193768 of OEIS.
(with Alexey Radul) Jewish Problems. History and Overview arXiv 1110.1556. Published in The American Matheamtical Monthly Vol. 119, No. 10 (2012), pp815-82.
This is a special collection of problems that were given to select applicants during oral entrance exams to the math department of Moscow State University. These problems were designed to prevent Jews and other undesirables from getting a passing grade. Among problems that were used by the department to blackball unwanted candidate students, these problems are distinguished by having a simple solution that is difficult to find. Using problems with a simple solution protected the administration from extra complaints and appeals. This collection therefore has mathematical as well as historical value.
(with Christina Chen, Daniel A. Klain) Volume bounds for shadow covering. Metric Geometry arXiv 1109.1619.
For n ≥ 2 a construction is given for a large family of compact convex sets K and L in n-dimensional Euclidean space such that the orthogonal projection Lu onto the subspace u⊥ contains a translate of the corresponding projection Ku for every direction u, while the volumes of K and L satisfy Vn(K) > Vn(L).
It is subsequently shown that, if the orthogonal projection Lu onto the subspace u⊥ contains a translate of Ku for every direction u, then the set (n/(n-1))L contains a translate of K. If follows that Vn(K) ≤ (n/(n-1))n Vn(L). In particular, we derive a universal constant bound Vn(K) ≤ 2.942 Vn(L), independent of the dimension n of the ambient space.
Related results are obtained for projections onto subspaces of some fixed intermediate co-dimension. Open questions and conjectures are also posed.
(with Sergei Konyagin) Sequences of Integers with Missing Quotients and Dense Points Without Neighbors. Combinatorics arXiv 1104.0441. Published in Discrete Mathematics 312 (2012), pp 1776-1787.
Let A be a pre-defined set of rational numbers. We say a set of natural numbers S is an A-quotient-free set if no ratio of two elements in S belongs to A. We find the maximal asymptotic density and the maximal upper asymptotic density of A-quotient-free sets when A belongs to a particular class. It is known that in the case A = {p, q}, where p, q are coprime integers greater than one, the latest problem is reduced to evaluation of the largest number of lattice non-adjacent points in a triangle whose legs lie on coordinate axis. We prove that this number is achieved by choosing points of the same color in the checkerboard coloring.
Martin Gardner's Mistake. Probability arXiv 1102.0173. Published in The College Mathematics Journal Vol 43, No. 1 (2012), pp. 20-24.
When Martin Gardner first presented the Two-Children problem, he made a mistake in its solution. Later he corrected the mistake in another publication, but unfortunately his incorrect solution is more widely known than his correction. In fact, a Tuesday-Child variation of this problem went viral in 2010, and the same flaw keeps reappearing in solutions for that problem as well. In this article, I would like to popularize Martin Gardner's correction and conduct a detailed discussion of the new problem.
(with Joel Brewster Lewis) Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle. Combinatorics arXiv 1006.4135. Published in the Electronic Journal of Combinatorics, v.18 P37, (2011).
We investigate a coin-weighing puzzle that appeared in the Moscow Math Olympiad in 1991. We generalize the puzzle by varying the number of participating coins, and deduce an upper bound on the number of weighings needed to solve the puzzle that is noticeably better than the trivial upper bound. In particular, we show that logarithmically-many weighings on a balance suffice.
Odd One Out. History and Overview arXiv 1005.2700. To be published in the proceedings of G4G9.
This article covers my second talk at the Gathering for Gardner in March, 2010. It is about an Odd One Out puzzle I invented, after having been inspired by Martin Gardner. I do not like Odd One Out questions; that is why I invented one.
(with Konstantin Knop and Alexey Radul) Baron Munchhausen's Sequence. Combinatorics arXiv 1003.3406. Published in the Journal of Integer Sequences, v.13 (2010).
We investigate a coin-weighing puzzle that appeared in the all-Russian math Olympiad in 2000. We liked the puzzle because the methods of analysis differ from classical coin-weighing puzzles. We generalize the puzzle by varying the number of participating coins, and deduce a complete solution, perhaps surprisingly, the objective can be achieved in no more than two weighings regardless of the number of coins involved.
Clifford Algebras and Graphs. Combinatorics arXiv 0810.3322. Published in Geombinatorics v.XX, pp. 56-76, (2010)
I show how to associate a Clifford algebra to a graph. I describe the structure of these Clifford graph algebras and provide many examples and pictures. I describe which graphs correspond to isomorphic Clifford algebras and also discuss other related sets of graphs. This construction can be used to build models of representations of simply-laced compact Lie groups.
Jamming as Information: a Geometric Approach. History and Overview arXiv 0809.0011. Published in the Journal of Recreational Mathematics, v.35, n.2, 99-111 (2006)
In this paper I discuss the kinds of information that can be extracted by our enemy if our jamming is too precise. I show geometric solutions for reconstructing linear routes given certain information about them, such as the shortest distance to a point or the times of entering and exiting a circle.
Number Gossip. Combinatorics arXiv 0804.2277. Published in Proceedings of G4G8.
This article covers my talk at the Gathering for Gardner 2008, with some additions. It is related to my pet project Number Gossip.
Autobiographical Numbers. Combinatorics arXiv 0803.0270. Published as "A Story of Storytelling Numbers" in Math Horizons, v.17, n.1, 14-17 (2009).
I introduce autobiographical numbers as defined in A046043 (see Online Encyclopedia of Integer Sequences). I continue by defining and analyzing biographies, curricula vitae and complete life stories of numbers. I end with the definition of mutually-praising number pairs.
9 Divides no Odd Fibonacci. Combinatorics arXiv 0712.3509.
I discuss numbers that divide no odd Fibonacci. The number 9 plays a special role among such numbers.
How to Create a New Integer Sequence. Combinatorics arXiv 0712.2244.
There are several standard procedures used to create new sequences from a given sequence or from a given pair of sequences. In this paper I discuss the most popular of these procedures. For each procedure, I give a definition and provide examples based on three famous sequences: the natural numbers, the prime numbers and the Fibonacci numbers. I also add my thoughts on what makes a sequence interesting. My goal is to help my readers invent new sequences, differentiate interesting sequences from boring ones, and better understand sequences they encounter.
Unique Tournaments and Radar Tracking. Combinatorics arXiv 0712.1621.
The sequence counting the number of unique tournaments with n people is the same as the sequence counting non-tracking binary strings corresponding to n-2 radar observations with the tracking rule "3 out of 5 with loss 2." This fact allows us to build a bijection between unique tournaments and non-tracking binary strings.
(with M. Curry and M. Flint) Decentralized Control Using Global Optimization (DCGO). AIAA Infotech@Aerospace 2007 Conference Proceedings (2007).
Global-scope plans for the team are generated and distributed using the principle of emergent leadership to provide efficient plan generation and execution with minimal performance degradation compared to a centralized controller under delayed communications.
(with Ingrid Daubechies and Konstantinos Drakakis) A Detailed Study of the Attachment Strategies of New Autonomous Systems in the AS Connectivity Graph. Internet Mathematics, v.2, n2, 185-246 (2005).
In the first part of this paper, we use real BGP data to study some properties of the AS connectivity graph and its evolution in time. In the second part, we build a simple model that is inspired by observations made in the first part, and we discuss simulations of this model.
(with J. Bernstein) Quantum groups and representations with highest weight. Quantum Algebra and Topology arXiv q-alg/9704007.
We connect quantum groups to minimal objects in the category of representations with highest weight λ: they correspond to irreducible representations.
On quantum group GLp,q(2). Quantum Algebra and Topology arXiv q-alg/9701033.
In the Hopf algebra GLp,q(2) the determinant is central iff p=q. In this case we put determinant to be equal to 1 to get SLq(2). In this paper I consider the case when p/q is a root of unity; and, consequently, a power of the determinant is central.
(with J.Bernstein) On Quantum Group SLq(2). Comm. Math. Phys., v.117, n3, 691-708 (1996).
We show how to construct the quantum group SLq(2), starting from the Hopf algebra of regular functions on the torus, adding some natural conditions. Our approach allows us to construct metaplectic quantum groups of the SL(2)-type.
Tetramodules over Hopf Algebra of Regular Functions on a Torus. IMRN, No.7, 275-284 (1994).
Discussion of the definition of "tetramodule," (a special kind of bimodule and bicomodule), its properties, and its applications.
Sturm-Liouville Operators Connected with Superanalogs of Virasoro algebra. Reports of Department of Mathematics, University of Stockholm, Sweden, 1988, No.5, 67-76.
We describe different ways of superizing the Sturm-Liouville operator.
(with O. Ovsienko) Superversion of Miura Transformations. Reports of Department of Mathematics, University of Stockholm, Sweden, 1988, No.5, 60-66.
The Miura transformation of the Korteveg-de Vries equation can be described in terms of the Virasoro algebra. We construct the analog of the Miura transformation for the Lie superalgebras of the Neveu-Schwarz type.
The Korteweg-de Vries Superequation Related to the Lie Superalgebra of Neveu-Schwarz-2 String Theory. Teor. Mat. Fiz., 72, No.2, 899-904 (1987).
The short version of the next paper.
Superization of the Korteveg-de Vries Equation Related with the Neveu-Schwarz Superalgebra NS(2). Reports of Department of Mathematics, University of Stockholm, Sweden, 1986, No.21, 58-73.
We construct the integrable Korteveg-de Vries type super-equation related to the Neveu-Schwarz superalgebra NS(2) by means of the hamiltonian reduction method from the Kac-Moody algebra $\widehat {sl(2,1)}$.
Lie Superalgebra Structure on Eigenfunctions and Jets of Resolvent's Kernel, near the Diagonal of an n-th Order Ordinary Differential Operator. in 'Integrable and Superintegrable Systems' ed. B.A.Kupershmidt. World Scientific 1990, p.321-335.
An n-th order ordinary differential operator can be regarded as a point in the dual space of the Lie superalgebra $\widehat {gl(n,1)}$. The stabilizer of this point in the coadjoint action inherits the structure of the Lie superalgebra and can be described as the direct sum of the jets of the kernel of the resolvent of, and the eigenfunctions of, the given differential operator.
Structure of Lie Superalgebras on Eigenfunctions and Jets of the Kernel of the Resolvent near the Diagonal for an n-th-order Differential Operator. Funkts. Anal. Prilozhen., 20, No.2, 162-164 (1986).
The short version of the previous one.
Lie Superalgebra osp(1,2), Neveu-Schwarz Superalgebra and Superization of Korteweg-de Vries equation. Group Theoretical Methods in Physics. Proceedings of the third seminar: Yurmala 1985. Utreht, Netherlands, VNU Science Press, 1986, v.1, 307-315.
The description of the super Korteveg-de Vries equation and the Neveu-Schwarz superalgebra as the Hamiltonian reduction of the Lie superalgebra $\widetilde{osp(1,2)}$.
The Gel'fand-Dikii Algebras and the Virasoro Algebra. Funkts. Anal. Prilozhen. 20, No.4, 332-334 (1986).
An investigation of the Gelfand-Dikii algebras as the generalizations the of Virasoro algebra.
Representation Models and Generalized Clifford Algebras. Funkts. Anal. Prilozhen., 16, No.4, 322-323 (1982).
For every simply-laced Dynkin diagram Δ of a Lie algebra G, we construct a generalization of the Clifford algebra, CΔ. The involutive subalgebra of G can be imbedded into CΔ. Using the induced representation of the involutive subalgebra in CΔ we construct the model representation of G - the direct sum of irreducible representations taken once each.
Send mail to: Tanya Khovanova
tanyakh@yahoo.comRevised August 2008