Search

The interval count problem, a classical question in the study of interval orders, was introduced by Ronald Graham in the 1980s. This problem asks: given an interval order $P$, what is the minimum number of distinct interval lengths required to construct an interval representation of $P$? Interval orders that can be represented with just one interval length are known as semiorders, and their characterizations are well known. However, the characterization of interval orders that require at most $k$ interval lengths -- termed $k$-count interval orders -- remains an open and challenging problem for $k\geq 2$. Our investigation into $2$-count interval orders led us naturally to consider a related problem, interval representations of permutations, which we introduce in this paper. Specifically, we characterize permutations that have a $2$-count interval representation. We prove that a permutation admits a $2$-count interval representation if and only if its longest decreasing subsequences have length at most $2$. For larger values of $k$, however, a similar characterization does not hold. There are permutations that do not permit a $3$-count interval representation despite having decreasing subsequences of length at most $3$. Characterizing $k$-count permutations remains open for $k \geq 3$. The $k$-count permutation representation problem appears to capture essential aspects of the broader problem of characterizing $k$-count interval orders. To support this connection, we apply our findings on interval representations of permutations to demonstrate that a height-$3$ interval order is $2$-count if and only if it has depth at most $2$, where the depth of an interval order refers to the length of the longest nested chain of intervals required in any interval representation of the order.

The length polyhedron $Q_P$ of an interval order $P$ is the convex hull of integral vectors representing the interval lengths in interval representations of $P$. This polyhedron has been studied by various authors, including Fishburn and Isaak. Notably, $Q_P$ forms a pointed affine cone, a property inherited from being a projection of the representation polyhedron, a structure explored also by Doignon and Pauwels. The apex of the length polyhedron corresponds to Greenough's minimal endpoint representation, which is, in fact, the length vector of the canonical interval representation -- an interval representation that minimizes the sum of the interval lengths. Building on a combinatorial perspective of canonical representations, we refine Isaak's graph-theoretical model by introducing a new and simpler directed graph. From directed cycles of this key digraph, we extract a linear system of inequalities that precisely characterizes the length polyhedron $Q_P$. This combinatorial approach also reveals the unique Hilbert basis of the polyhedron. We prove that the intersection graph of the sets corresponding to these binary rays are Berge graphs; therefore they are perfect graphs. As a result, for interval orders with bounded width, the length polyhedron has a polynomial-sized Hilbert basis, which can be computed in polynomial time. We also provide an example of interval orders with a Hilbert basis of exponential size. In a companion paper we determine the Schrijver system for the length polyhedron. We conclude with open problems.

Consider a $3$-uniform hypergraph of order $n$ with clique number $k$ such that the intersection of all its $k$-cliques is empty. Szemer\'edi and Petruska proved $n\leq 8m^2+3m$, for fixed $m=n-k$, and they conjectured the sharp bound $n \leq {m+2 \choose 2}$. This problem is known to be equivalent to determining the maximum order of a $\tau$-critical $3$-uniform hypergraph with transversal number $m$ (details may also be found in a companion paper: arXiv:2204.02859). The best known bound, $n\leq \frac{3}{4}m^2+m+1$, was obtained by Tuza using the machinery of $\tau$-critical hypergraphs. Here we propose an alternative approach, a combination of the iterative decomposition process introduced by Szemer\'edi and Petruska with the skew version of Bollob\'as's theorem on set pair systems. The new approach improves the bound to $n\leq {m+2 \choose 2} + O(m^{{5}/{3}})$, resolving the conjecture asymptotically., Comment: 23 pages, no figures. Completes project begun in "On a conjecture of Szemer\'edi and Petruska", arXiv:1904.04921v2

Recently we asymptotically resolved the long-standing Szemer\'edi and Petruska conjecture. Several decades ago Gy\'arf\'as et al. observed, via a straightforward but unpublished argument, that this conjecture is equivalent to the problem of determining the maximum order of a $3$-uniform $\tau$-critical hypergraph. Consequently, an asymptotically tight upper bound for the maximum order of a $3$-uniform $\tau$-critical hypergraph follows from our recent work, reawakening interest in this equivalence. In this companion paper we supply a simple proof of this equivalence. We also present related background with open problems, and mention combinatorial geometry applications of the Szemer\'edi and Petruska conjecture.

Let H be a 3-uniform hypergraph of order n with clique number k such that the intersection of all maximum cliques of H is empty. For fixed m=n-k, Szemer\'edi and Petruska conjectured the sharp bound $n\leq {m+2\choose 2}$. In this note the conjecture is verified for m=2,3 and 4.

We develop a simple 3-dimensional iterative map model to forecast the global spread of the coronavirus disease. Our model contains at most two fitting parameters, which we determine from the data supplied by the world health organisation for the total number of cases and new cases each day. We find that our model provides a surprisingly good fit to the currently-available data, which exhibits a cross-over from exponential to power-law growth, as lock-down measures begin to take effect. Before these measures, our model predicts exponential growth from day 30 to 69, starting from the date on which the world health organisation provided the first `Situation report' (21 January 2020 $-$ day 1). Based on this initial data the disease may be expected to infect approximately 23% of the global population, i.e. about 1.76 billion people, taking approximately 83 million lives. Under this scenario, the global number of new cases is predicted to peak on day 133 (about the middle of May 2020), with an estimated 60 million new cases per day. If current lock-down measures can be maintained, our model predicts power law growth from day 69 onward. Such growth is comparatively slow and would have to continue for several decades before a sufficient number of people (at least 23% of the global population) have developed immunity to the disease through being infected. Lock-down measures appear to be very effective in postponing the unimaginably large peak in the daily number of new cases that would occur in the absence of any interventions. However, should these measure be relaxed, the spread of the disease will most likely revert back to its original exponential growth pattern. As such, the duration and severity of the lock-down measures should be carefully timed against their potentially devastating impact on the world economy., Comment: 9 pages, 3 figures, 2 tables, full article

Given $2k-1$ convex sets in $R^2$ such that no point of the plane is covered by more than $k$ of the sets, is it true that there are two among the convex sets whose union contains all $k$-covered points of the plane? This question due to Gy. Petruska has an obvious affirmative answer for $k=1,2,3$; we show here that the claim is also true for $k=4$, and we present a counterexample for $k=5$. We explain how Petruska's geometry question fits into the classical hypergraph extremal problems, called arrow problems, proposed by P. Erd\H{o}s., Comment: 13 pages

We studied, by scanning tunneling microscopy, the morphology of nanopits of monolayer depth created at graphite surfaces by hydrogen plasma etching under various conditions such as H$_2$ pressure, temperature, etching time, and RF power of the plasma generation. In addition to the known pressure-induced transition of the nanopit morphology, we found a sharp temperature-induced transition from many small rather round nanopits of ~150 nm size to few large hexagonal ones of 300-600 nm within a narrow temperature range. The remote and direct plasma modes switching mechanism, which was proposed to explain the pressure-induced transition, is not directly applicable to this newly found transition. Scanning tunneling spectroscopy (STS) measurements of edges of the hexagonal nanopits fabricated at graphite surfaces by this method show clear signatures of the peculiar electronic state localized at the zigzag edge (edge state), i.e., a prominent peak near the Fermi energy accompanied by suppressions on either side in the local density of states. These observations indicate that the hexagonal nanopits consist of a high density of zigzag edges. The STS data also revealed a domain structure of the edge state in which the electronic state varies over a length scale of ~3 nm along the edge. The present study will pave the way for microscopic understanding of the anisotropic etching mechanism and of spin polarization in zigzag nanoribbons which are promising key elements for future graphene nanoelectronics., Comment: 10 pages, 7 figures

Consider a $3$-uniform hypergraph of order $n$ with clique number $k$ such that the intersection of all its $k$-cliques is empty. Szemer\'edi and Petruska proved $n\leq 8m^2+3m$, for fixed $m=n-k$, and they conjectured the sharp bound $n\leq{m+2\choose 2}$. Tuza proved the best known bound, $n\leq \frac{3}{4}m^2+m+1$, using the machinery of $\tau$-critical hypergraphs. Here we propose an alternative approach, combining a decomposition process introduced by Szemer\'edi and Petruska with the skew version of Bollob\'as's theorem to prove $n\leq m^2 + 6m + 2$. While the bound obtained here is weaker than Tuza's bound, it is a proof-of-concept for a different approach and a call to apply dimension bounds from linear algebra., Comment: 9 pages, no figures: Version 2 reflects new information about the best known upper bound. We are very grateful to Zsolt Tuza for alerting us to the best known upper bound, $\frac{3}{4}m^2+m+1$, for the maximum order of a $\tau$-critical $3$-uniform hypergraph with transversal number $m$

Monolayer graphene epitaxially grown on SiC(0001) was etched by H-plasma and studied by scanning tunneling microscopy and spectroscopy. The etching created partly hexagonal nanopits of monatomic depth as well as elevated regions with a height of about 0.12 nm which are stable at $T$ = 78 K. The symmetric tunnel spectrum about the Femi energy and the absence of a $6\times6$ corrugation on the elevated regions suggest that in these regions the carbon buffer layer is decoupled from the SiC substrate and quasi-free-standing bilayer graphene appears at originally monolayer graphene on the buffer layer. This is a result of passivation of the SiC substrate by intercalated hydrogen as in previous reports for graphene on SiC(0001) heat treated in atomic hydrogen., Comment: 6 pages, 5 figures, ACSIN-14 and ICSPM-26 proceedings

A graph is an apex graph if it contains a vertex whose deletion leaves a planar graph. The family of apex graphs is minor-closed and so it is characterized by a finite list of minor-minimal non-members. The long-standing problem of determining this finite list of apex obstructions remains open. This paper determines the 133 minor-minimal, non-apex graphs that have connectivity two., Comment: 57 pages, 62 figures, 1 appendix Near final published version. Note that archive LaTeX processing creates g6 data contain apostrophe error ' should be `

Let $G$ be the Cartesian product of two finite paths, called a grid, and let $T$ be the set of eight distinct vertices of $G$, called terminals. Assume that $T$ is partitioned into four terminal pairs $\{s_i,t_i\}$, $1\leq i\leq 4$, to be linked in $G$ by using edge disjoint paths. To prove that such a linkage always exists we need a sequence of technical lemmas making possible for some terminals to `escape' from a $3\times 3$ corner of $Q\subset G$, called a `quadrant'. Here we state those lemmas, and give a proof for the cases when $Q$ contains at most $4$ terminals.

Let $Q$ be a finite subgraph of the integer grid $G$ in the plane, and let $T$ be a set of pairs of distinct vertices in $G$, called `terminal pairs'. Escaping a subset $X\subset T\cap Q$ from $Q$ means finding edge disjoint paths from the terminals in $X$ into distinct vertices of a set $L$ in the boundary of $Q$. Here we prove several lemmas for the cases where $Q$ is a $3\times 3$ grid, $L$ is the union of a vertical and horizontal boundary line of $Q$, furthermore, $T$ is a set of four terminal pairs in $G$ such that $|T\cap Q|\geq 5$. These lemmas are applied in [4] and complete the proof that the Cartesian product of two (one way) infinite paths has path-pairability number four.

Let $G=P_6\Box P_6$ be the $6\times 6$ grid, the Cartesian product of two paths of six vertices. Let $T$ be the set of eight distinct vertices of $G$, called terminals, and assume that $T$ is partitioned into four terminal pairs $\{s_i,t_i\}$, $1\leq i\leq 4$. We prove that $G$ is $4$-path-pairable, that is, for every $T$ there exist in $G$ pairwise edge disjoint $s_i,t_i$-paths, $1\leq i\leq 4$.

We introduce a Bayesian multiple regression tree model to characterize relationships between physico-chemical properties of nanoparticles and their in-vitro toxicity over multiple doses and times of exposure. Unlike conventional models that rely on data summaries, our model solves the low sample size issue and avoids arbitrary loss of information by combining all measurements from a general exposure experiment across doses, times of exposure, and replicates. The proposed technique integrates Bayesian trees for modeling threshold effects and interactions, and penalized B-splines for dose- and time-response surface smoothing. The resulting posterior distribution is sampled by Markov Chain Monte Carlo. This method allows for inference on a number of quantities of potential interest to substantive nanotoxicology, such as the importance of physico-chemical properties and their marginal effect on toxicity. We illustrate the application of our method to the analysis of a library of 24 nano metal oxides., Comment: Published at http://dx.doi.org/10.1214/14-AOAS797 in the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Locomotion and gross morphology have been important phenotypes for C. elegans genetics since the inception of the field and remain relevant. In parallel with developments in genome sequencing and editing, phenotyping methods have become more automated and quantitative, making it possible to detect subtle differences between mutants and wild-type animals. In this chapter, we describe how to calibrate a single worm tracker consisting of a USB microscope mounted on a motorized stage and how to record and analyze movies of worms crawling on food. The resulting quantitative phenotypic fingerprint can sensitively identify differences between mutant and wild type worms., Comment: 14 pages, 6 figures

In this work we analyse Colour-Magnitude Diagrams (CMDs) of catalogued star clusters located in the Large Magellanic Cloud (LMC), from a YJKs photometric data set obtained by the Visible and Infrared Survey Telescope for Astronomy (VISTA) survey of the Magellanic Clouds system (VMC). We studied a total of 98 objects of small angular size, typically ~ 11.6 pc in diameter projected towards both uncrowded tile LMC 8_8 and crowded tile LMC 5_5. They populate relatively crowded LMC fields with significant fluctuations in the stellar density, the luminosity function, and the colour distribution as well as uncrowded fields. This cluster sample is aimed at actually probing our performance in reaching the CMD features of clusters with different ages in crowded/uncrowded fields. We applied a subtraction procedure to statistically clean the cluster CMDs from field star contamination. We then matched theoretical isochrones to the background-subtracted CMDs to determine the ages and metallicities of the clusters. We estimated the ages of 65 clusters, which resulted to be in the age range 7.3 < log(t/yr) < 9.55. We also classified as chance grouping of stars 19 previoulsy catalogued clusters, two possible cluster-like asterisms, and one unresolved cluster. For other 8 objects, we could not find a clear star concentration in the Ks images either, so we quoted them as cluster-like asterisms. Finally, we found two previously catalogued single star clusters to be unresolved background galaxies (KMHK747, OGLE366), and one to be a triple cluster system (BSDL 2144)., Comment: Astronomy & Astrophysics, accepted

New generation in vitro high-throughput screening (HTS) assays for the assessment of engineered nanomaterials provide an opportunity to learn how these particles interact at the cellular level, particularly in relation to injury pathways. These types of assays are often characterized by small sample sizes, high measurement error and high dimensionality, as multiple cytotoxicity outcomes are measured across an array of doses and durations of exposure. In this paper we propose a probability model for the toxicity profiling of engineered nanomaterials. A hierarchical structure is used to account for the multivariate nature of the data by modeling dependence between outcomes and thereby combining information across cytotoxicity pathways. In this framework we are able to provide a flexible surface-response model that provides inference and generalizations of various classical risk assessment parameters. We discuss applications of this model to data on eight nanoparticles evaluated in relation to four cytotoxicity parameters., Comment: Published in at http://dx.doi.org/10.1214/12-AOAS563 the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Rapid advances in genetics, genomics, and imaging have given insight into the molecular and cellular basis of behaviour in a variety of model organisms with unprecedented detail and scope. It is increasingly routine to isolate behavioural mutants, clone and characterise mutant genes, and discern the molecular and neural basis for a behavioural phenotype. Conversely, reverse genetic approaches have made it possible to straightforwardly identify genes of interest in whole-genome sequences and generate mutants that can be subjected to phenotypic analysis. In this latter approach, it is the phenotyping that presents the major bottleneck; when it comes to connecting phenotype to genotype in freely behaving animals, analysis of behaviour itself remains superficial and time consuming. However, many proof-of-principle studies of automated behavioural analysis over the last decade have poised the field on the verge of exciting developments that promise to begin closing this gap. In the broadest sense, our goal in this chapter is to explore what we can learn about the genes involved in neural function by carefully observing behaviour. This approach is rooted in model organism genetics but shares ideas with ethology and neuroscience, as well as computer vision and bioinformatics. After introducing C. elegans as a model, we will survey the research that has led to the current state of the art in worm behavioural phenotyping and present current research that is transforming our approach to behavioural genetics., Comment: Accepted for publication in "Linking Phenotypes and Genotypes - How to Infer Genetic Architecture from Perturbation Studies", edited by Florian Markowetz (Cambridge) and Michael Boutros (Heidelberg), Cambridge University Press. 28 pages, 6 figures

Myosin-II's rod-like tail drives filament assembly with a head arrangement that should generate equal and opposite contractile forces on actin--if one assumes that the filament is a symmetric bipole. Self-assembled myosin filaments are shown here to be asymmetric in physiological buffer based on cross-correlated images from both atomic force microscopy (AFM) and total internal reflection fluorescence (TIRF). Quantitative cross-correlation of these orthogonal methods produces structural information unavailable to either method alone in showing that fluorescence intensity along the filament length is proportional to height. This implies that myosin heads form a shell around the filament axis, consistent with F-actin binding. A motor density of ~50 - 100 heads/micron is further estimated but with an average of 32% more motors on one half of any given filament compared to the other, regardless of length. A purely entropic pyramidal lattice model is developed that qualitatively captures this lack of length dependence and the distribution of filament asymmetries. Such strongly asymmetric bipoles are likely to produce an imbalanced contractile force in cells and in actin-myosin gels, and thereby contribute to motility as well as cytoskeletal tension., Comment: 25 pages, 8 figures. Accepted in Biophysical Journal

We study the role of microtubule movement in bidirectional organelle transport in Drosophila S2 cells and show that EGFP-tagged peroxisomes in cells serve as sensitive probes of motor induced, noisy cytoskeletal motions. Multiple peroxisomes move in unison over large time windows and show correlations with microtubule tip positions, indicating rapid microtubule fluctuations in the longitudinal direction. We report the first high-resolution measurement of longitudinal microtubule fluctuations performed by tracing such pairs of co-moving peroxisomes. The resulting picture shows that motor-dependent longitudinal microtubule oscillations contribute significantly to cargo movement along microtubules. Thus, contrary to the conventional view, organelle transport cannot be described solely in terms of cargo movement along stationary microtubule tracks, but instead includes a strong contribution from the movement of the tracks., Comment: 24 pages, 5 figures