Oleg Pikhurko: Research Papers

Here is the list of my published and submitted papers in the anti-chronological order. Full text (pre-publication versions) is available on-line. Some restrictions on copying/etc may apply; please check with the publisher if in doubt.

Submitted

(with M.Kang, O.Ravsky, M.Schacht and O.Verbitsky) Obfuscated Drawings of Planar Graphs, submitted to Discr Comput Geometry, 16pp.
(with K.Litwak and S.Pongnumkul) How to Play Dundee, submitted to Annals of Combinatorics, 21pp.
(with T.Bohman, A.Frieze and D.Mubayi) Hypergraphs with independent neighborhoods, submitted to Combinatorica, 12pp.
(with J.Verstraete) The Maximum Size of Hypergraphs without Generalized 4-Cycles, submitted to J Comb Th (A), 18pp.
Finding an Unknown Acyclic Orientation of a Given Graph, submitted to SIAM J Comput, 12pp.
(with T.Jiang) Anti-Ramsey numbers of doubly edge-critical graphs, submitted to J Graph Th, 9pp.
(with A.Beveridge, T.Bohman, A.Frieze) Memoryless Rules for Achlioptas Processes, submitted to SIAM J Discr Math, 17pp.

Accepted

(with A.Beveridge, T.Bohman, A.Frieze) Game Chromatic Index of Graphs with Given Restrictions on Degrees, to appear in Theoret Computer Sci, 16pp
Perfect Matchings and K_4^3-Tilings in Hypergraphs of Large Codegree, to appear in Graphs & Comb, 13pp.
(with Z.Furedi and D.Mubayi) Quadruple Systems with Independent Neighborhoods, J Comb Th (A), 10pp.
(with T.Bohman, A.Frieze, and C.Smyth) Anti-Ramsey Properties of Random Graphs, to appear in J Comb Th (B), 20pp.
(with D.Mubayi) Constructions of Non-Principal Families in Extremal Hypergraph Theory, to appear in Discr Math, 11pp.
Exact Computation of the Hypergraph Turan Function for Expanded Complete 2-Graphs, 9pp, accepted by J Comb Th (B), publication suspended for an indefinite time, see http://www.math.cmu.edu/~pikhurko/Copyright.html

2008

(with A.Beveridge) The Connectivity of Extremal Ramsey Graphs, Autralasian J Comb, 41 (2008) 57-62.
An Exact Turan Result for the Generalized Triangle, Combinatorica, 28 (2008) 187-208.
(with M.Bednarska) Odd and Even Cycles in Maker-Breaker Games, Europ J Comb, 29 (2008) 742-745.
(with J.Schmitt) A Note on Minimum K_{2,3}-Saturated Graphs, Australasian J Comb, 40 (2008) 211-215.
(with P.Haxell and A.Thomason) Maximum Acyclic and Fragmented Sets in Regular Graphs, J Graph Th, 57 (2008) 149-156.

2007

Characterization of Product Anti-Magic Graphs of Large Order, Graphs & Comb, 23 (2007) 681-689.
(with J.Spencer and O.Verbitsky) Decomposable graphs and definitions with no quantifier alternation, Europ J Comb, 28 (2007) 2264-2283. (Conference version (EuroComb'05), Discr Math and Theoretical Comput Sci, AE (2005) 25-30.)
(with F.Lazebnik and A.Woldar) Maximum Number of Colorings of (2k,k^2)-Graphs, J Graph Th, 56 (2007) 135-148.
(with T.Sousa) Minimum H-Decompositions of Graphs, J Comb Th (B), 97 (2007) 1041-1055.
(with A.Beveridge, T.Bohman, A.Frieze) Product Rule Wins a Competitive Game, Proc Amer Math Soc, 135 (2007) 3061-3071.
(with T.Schoen) Integer Sets Having the Maximum Number of Distinct Differences, Integers, 7 (2007) 9pp.
(with D.Mubayi) A new generalization of Mantel's theorem to k-graphs, J Comb Th (B), 97 (2007) 669-678.
(with T.Bohman, A.Frieze, T.Luczak, C.Smyth, J.Spencer, and O.Verbitsky) First Order Definability of Trees and Sparse Random Graphs, Comb, Prob & Comput, 16, (2007) 375-400.
Trees Are Almost Prime, Discr Math, 307 (2007) 1455-1462.

2006

(with J.Wojciechowski) Edge-Bandwidth of Grids and Tori, Theoret Computer Sci, 369 (2006) 35-43.
(with Z.Furedi and M.Simonovits) 4-Books of Three Pages, J Comb Th (A), 113 (2006) 882-891.
(with J.Spencer and O.Verbitsky) Succinct Definitions in the First Order Theory of Graphs, Annals Pure Appl Logic, 139 (2006) 74-109.
(with H.Veith and O.Verbitsky) The First Order Definability of Graphs: Upper Bounds for Quantifier Rank, Discr Appl Math, 154 (2006) 2511-2529.
Dense Edge-Magic Graphs and Thin Additive Bases, Discr Math, 306 (2006) 2097-2107.

2005

(with A.Taraz) Degree Sequences of F-Free Graphs, Electronic J Comb, 12 (2005) 12pp.
(with M.Kang) Maximum K_{r+1}-Free Graphs Which Are Not r-Partite, Mat Studii, 24 (2005) 12-20.
Minimizing the Number of Partial Matchings in Bipartite Graphs, Bulletin of ICA, 43 (2005) 13-18.
(with Z.Furedi and M.Simonovits) On Triple Systems with Independent Neighborhoods, Comb, Prob & Comput, 14 (2005) 795-813.
(with B.Bollobas) Integer Sets with Prescribed Pairwise Differences Being Distinct, Europ J Comb, 26 (2005) 607-616.
(with O.Verbitsky) Descriptive Complexity of Finite Structures: Saving the Quantifier Rank, J Symb Logic, 70 (2005) 419-450.
(with J.H.Kim, J.Spencer and O.Verbitsky) How Complex are Random Graphs in First Order Logic?, Random Struc Alg, 26 (2005) 119-145.
(with C.Greenhill) Bounds on the Generalised Acyclic Chromatic Numbers of Bounded Degree Graphs, Graphs & Comb, 21 (2005) 407-419.
(with A.Frieze, M.Krivelevich and T.Szabo) The Game of JumbleG, Comb, Prob & Comp, 14 (2005) 783-793.
Generating Edge-Labeled Trees, American Math. Monthly, 112 (2005) 919-921.
(with M.Bednarska) Biased Positional Games on Matroids, Europ J Comb, 26 (2005) 271-285.

2004

Results and Open Problems on Minimum Saturated Graphs, Ars Comb, 72 (2004) 111-127.

2003

(with Z.Furedi and M.Simonovits) The Turan Density of the Hypergraph {abc,ade,bde,cde}, Electronic J Comb, 10 (2003) 7pp.
Breaking Symmetry on Complete Bipartite Graphs of Odd Size, Integers, 3 (2003) 9pp.
(with R.Diestel) On the Cofinality of Infinite Partially Ordered Sets: Factoring a Poset into Lean Essential Subsets, Order, 20 (2003) 53-66.
Further Asymptotic Size Ramsey Results Obtained via Linear Programming, Discr Math, 273 (2003) 193-202.
(with A.Kovacec, J.Merikoski and A.Virtanen) Optimizers for Sub-Sums Subjected to a Sum- and a Schur Convex Constraint with Applications to the Estimation of Eigenvalues, Math Inequalities & Applications, 6 (2003) 745-763.
Remarks on a Paper by H. Bielak on Size Ramsey Numbers, Periodica Math Hung, 47 (2003) 195-200.
Size Ramsey Numbers of Stars versus 4-Chromatic Graphs, J Graph Th, 42 (2003) 220-233.
Asymptotic Size Ramsey Results for Bipartite Graphs, SIAM J Discr Math, 16 (2003) 99-113.

2002

Every Tree with at Most 34 Vertices is Prime, Utilitas Math, 62 (2002) 185-190.
(with A.Thomason) Disjoint Subgraphs of Large Maximum Degree, Discr Math, 248 (2002) 125-141.

2001

Lattice Points in Lattice Polytopes, Mathematika, 48 (2001) 15-24.
Constructing Designs Straightforwardly: Worst Arising Cases, J Comb Designs, 9 (2001) 100-106.
Size Ramsey Numbers of Stars versus 3-Chromatic Graphs, Combinatorica, 21 (2001) 403-412.
Uniform Families and Count Matroids, Graphs & Comb, 17 (2001) 729-740.
Weakly Saturated Hypergraphs and Exterior Algebra, Comb, Prob & Comp, 10 (2001) 435-451.

2000

Asymptotic Evaluation of the sat-Function for r-Stars, Discr Math, 214 (2000) 275-278.
On Envy-Free Cake Division, American Math Monthly, 107 (2000) 736-738.

1999

The Minimum Size of Saturated Hypergraphs, Comb, Prob & Comp, 8 (1999) 483-492.
On Edge Decompositions of Posets, Order, 16 (1999) 231-244.
Enumeration of Labelled (k,m)-Trees, J Comb Th (A), 86 (1999) 197-199.

1997

(with T.Banakh) On Linear Functorial Operators Extending Pseudometrics, Comment. Math. Univ. Carolinae, 38 (1997) 343-348.

1994

Extending Metrics in Compact Pairs, Mat Studii, 3 (1994) 103-106.
Operators Extending (Pseudo-)Metrics, in Proc. All-Ukrainian Conf. Young Researchers (Math), 1994, N 1302 YK-94, Part 1, pages 10-16.

1992

(with M.Zarichnyi) On Lifting of Functors at Categories of Eilenberg-Moore of the Triple Generated by CpCp, Ukrainian Math J, 44 (1992) 1289-1291.

PhD thesis

Here I include my PhD thesis "Extremal Hypergraphs" (written under supervision of Andrew Thomason), xii+150pp. (Oct'99), in postscript (1.2Mb) or in gzip+dvi (250Kb) format.

Various manuscripts

Borsuk's Conjecture Fails in Dimensions 321 and 322, arXiv:math.CO/0202112, 3pp.